ANU Computer Science Technical Reports
TR-CS-07-04
Stephen M. Blackburn and Kathryn S. McKinley.
Immix Garbage Collection: Fast Collection, Space
Efficiency, and Mutator Locality.
August 2007.
[POSTSCRIPT (421010 bytes)] [PDF (431425 bytes)]
Abstract: No current garbage collector combines space
efficiency, low collector times, and mutator (application) locality for
contemporaneously allocated objects. For example, free-list allocation
coupled with mark-sweep collection achieves space efficiency, but poor
mutator locality. On the other hand, contiguous (bump-pointer) allocation
with copying collection provides mutator locality but poor space efficiency
since it requires reserving half the heap for copying in case all objects
survive. This paper presents an algorithm that obtains space efficiency, low
collection times, and mutator locality in a single regime. We call this
garbage collector immix, which means to intimately commingle. The
immix heap is organized hierarchically into blocks of contiguous
memory, each consisting of N fixed size lines. Immix tracks memory
use at a line granularity. Immix bump-allocates objects into one or more
contiguous free lines to attain mutator locality. To attain space efficiency,
immix uses mark-sweep collection to identify free lines. When needed to
eliminate fragmentation, immix mixes copying and mark-sweep collection in a
unique way to implement opportunistic single pass compaction. We
demonstrate immix as a whole heap collector, as a component of a generational
collector, and as a mostly non-moving collector. Our experimental results
demonstrate that immix comprehensively and uniformly outperforms
state-of-the-art whole heap mark-sweep, mark-compact, and semi-space
collectors on a range of heap sizes on multiple architectures. Immix is the
first collector to attain simultaneously space efficiency, low garbage
collection times, and mutator locality.
Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>
Last modified: Tue May 31 12:56:01 EST 2011