Garbage Collection: The Next Generation

Garbage Collection: The Next Generation

Abstract

The increasing reliance on garbage collected languages requires collectors that perform well. In this talk, we present a number of new garbage collection algorithms that exploit object lifetime and pointer updates behavior in new ways to improve performance and pause times. In particular, we introduce a new copying garbage collection framework, called Beltway, and a new hybrid copying and reference counting collector.

The Beltway garbage collection framework significantly generalizes existing copying collectors by exploiting and separating object age and incrementality. It groups objects in one or more increments on queues called belts, collects belts independently, and collects increments on a belt in first-in-first-out order. We show that Beltway configurations, selected by command line options, act and perform the same as semi-space, generational, and older-first collectors, and encompass all previous copying collectors of which we are aware. We use the generality of Beltway to design a new family of copying collectors that are robust to variations in heap size and improve total execution time over the best generational copying collectors of which we are aware by up to 40%, and on average by 5 to 10%, for small to moderate heap sizes.

These and other general purpose collectors still are not able to combine short pause times with fast throughput. Reference counting collectors often attain short pause times, but with significant performance penalties. We present a new hybrid, which combines copying nursery collection and reference counting the older generation to achieve both goals. Key to our algorithm is a generalization of deferred reference counting of nursery objects. RC-hybrid safely ignores mutations to nursery objects and thus restricts copying and reference counting to the objects for which they perform well. We compare RC-hybrid with pure reference counting, a state-of-the-art copying and mark-sweep hybrid, and a number of other collectors. We show that RC-hybrid combines fast throughput, and low average and maximum pause times.