CoCo: Sound and adaptive replacement of Java collections

Abstract. Inefficient use of Java containers is an important source of run-time inefficiencies in large applications. This paper presents an application-level dy-namic optimization technique called CoCo, that exploits algorithmic advantages of Java collections to improve performance. CoCo dynamically identifies opti-mal Java collection objects and safely performs run-time collection replacement, both using pure Java code. At the heart of this technique is a framework that ab-stracts container elements to achieve efficiency and that concretizes abstractions to achieve soundness. We have implemented part of the Java collection frame-work as instances of this framework, and developed a static CoCo compiler to generate Java code that performs optimizations. This work is the first step to-wards achieving the ultimate goal of automatically optimizing away semantic inefficiencies.