Improving locality with parallel hierarchical copying GC

This paper shows how to reduce cache and TLB misses by changing the order in which a parallel garbage collector copies heap objects. Reducing cache and TLB misses improves program run time. Parallel garbage collection improves scaling on multi-processor machines. Technology trends indicate that both memory locality and multi-processor scaling increase in importance. Our new algorithm is based on the earlier single-threaded "hierarchical decomposition" algorithm by Wilson, Lam, and Moher. This paper presents a thorough evaluation of parallel hierarchical copying, showing that it improves spatial locality, reduces cache and TLB misses, and speeds up 14 out of 26 benchmarks. Copyright © 2006 ACM.