Placement optimization using data context collected during garbage collection

We present a study on data context for object-oriented programs. We first introduce several data structures related to data context that can properly organize object fields, object types and the access sequence in a compact manner. Our approach combines the collection of data context with commonly used garbage collectors in a virtual machine environment. The garbage collector maintains extra runtime data for the building of data contexts with minimal overhead. To save memory space and also the time spent on retrieving data, a shorter representation is proposed which sacrifices a small amount of accuracy. To further demonstrate the usefulness of data context for dynamic optimizations, we implemented a placement optimization that captures data accesses that frequently miss, and places relevant objects to reduce data cache misses and improve performance. The proposed scheme was measured with several benchmarks and in various experimental setups. We demonstrate that building the data context for program understanding and optimization is valuable in a virtual machine environment by using a garbage collector, while adding less than 1% extra overhead. Copyright © 2009 ACM.