Scalable Garbage Collection via Remembered Set Summarization and Refinement

My thesis: Regional garbage collection with summarization, waveoff, and snapshot refinement, provides mutator-independent worst-case bounds on pause times and minimum mutator utilization, and provides competitive throughput while maintaining a worst-case bound on overall memory usage.

My dissertation: klock11-diss.pdf. My comprehensive exam had slides that may provide a quicker read: compexamp-slides.pdf


Regional garbage collection offers a useful compromise between real-time and generational collection. Regional collectors resemble generational collectors, but are scalable. A scalable collector guarantees a positive lower bound, independent of mutator and live storage, for the theoretical worstcase minimum mutator utilization (MMU).

Standard generational collectors are not scalable. Some real-time collectors are scalable, while others assume a well-behaved mutator or provide no worst-case guarantees at all.

This dissertation presents regional garbage collection, coupled with a theorem establishing that it is scalable in the sense above, as well as establishing upper bounds for its worst-case space usage and collection pauses.

Regional collectors separate summarization and refinement from the task of object reclamation. They resolve “popularity” problems via two novel technologies: summarization wave-off, and region fame. Regional collectors cannot compete with hard real-time collectors at millisecond resolutions, but offer efficiency comparable to contemporary generational collectors combined with improved latency and MMU at resolutions on the order of hundreds of milliseconds to a few seconds.

A prototype regional collector performs acceptably on a wide range of benchmarks: It is comparable to a tuned generational collector on a set of fifty-eight non-collection-intensive benchmarks, and achieves acceptable throughput without violating its bounds on a set of thirteen collection-intensive benchmarks.

Valid XHTML 1.0!