Mark-Region and Other Advances in Garbage Collection

Programmers are increasingly choosing managed languages for modern
applications, which rely on garbage collection to manage dynamically
allocated objects. The garbage collector directly determines program
performance by making a classic space-time tradeoff that seeks to
provide space efficiency, fast reclamation, and mutator performance.
The three canonical tracing garbage collectors: semi-space,
mark-sweep, and mark-compact each sacrifice one objective. This talk
describes a collector family, called mark-region and introduces
opportunistic defragmentation, which mixes copying and marking in a
single pass. Combining both, we implement immix, a novel high
performance garbage collector that for the first time achieves all
three performance objectives simultaneously. The key insight is to
allocate and reclaim memory in contiguous regions, at a coarse block
grain when possible and otherwise reclaim in groups of finer grain
lines. We show that immix outperforms existing canonical algorithms,
improving total application performance by 7 to 25% on average across
20 benchmarks. As the mature space in a generational collector, immix
matches or beats a highly tuned generational collector, e.g., it
improves total performance for SPECjbb by 5%. These innovations and
the identification of a new family of collectors open new
opportunities for garbage collector design.