ANU Computer Science Technical Reports
TR-CS-02-06
Stephen M Blackburn and Kathryn S McKinley.
Fast garbage collection without a long wait.
November 2002.
[POSTSCRIPT (169379 bytes)] [PDF (176182 bytes)] [EPrints archive]
Abstract: General purpose garbage collectors have yet
to combine short pause times with fast throughput. Collectors such as
reference counting attain short pause times with significant performance
penalties. Pure and hybrid generational collectors can achieve high
throughput and have modest average pause times, but occasionally collect the
whole heap and consequently incur long pauses. This paper introduces
RC-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 which allows RC-hybrid to
safely ignore mutations to nursery objects. RC-hybrid thus restricts copying
and reference counting to the objects for which they perform well. Copying
collectors' bump pointer allocation is extremely fast, and collection time is
proportional to the live objects whose survival rates are low and bounded in
a fixed size nursery. Reference counting time is proportional to object
mutations and the number of dead objects, both of which are typically low for
older objects. We further bound time spent reference counting with collection
triggers and buffering. 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.
Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>
Last modified: Tue May 31 12:56:01 EST 2011