ANU Computer Science Technical Reports

TR-CS-09-02

Daniel Frampton, Stephen M Blackburn, Luke N Quinane, and John N Zigman.
Efficient Concurrent Mark-Sweep Cycle Collection.
October 2009.

[POSTSCRIPT (251110 bytes)] [PDF (252020 bytes)]

Abstract: Since 1960, reference counting has been a popular means of garbage collection. Reference counters achieve low pause times by using local data to determine liveness, but the use of this local data leaves the collector unable to collect cyclic garbage. Recent advances such as the use of coalescing and generations have dramatically improved the throughput of reference counting collectors. However, the efficient collection of cyclic garbage remains a stumbling block. This paper responds to this shortcoming with MSCD, a concurrent tracing algorithm that takes advantage of information available within a reference counted environment. MSCD outperforms alternatives such as trial deletion and backup tracing by up to a factor of two. This advantage is the result of three insights: 1) objects subject to races during concurrent tracing are trivially identified using data already established by the reference counter, 2) the trace performed by the mark phase of the collector can safely omit objects statically identified as inherently acyclic, and 3) the sweep phase of the collector can be reduced to just those objects which are potentially cyclic garbage. We show that MSCD works with state of the art reference counting collectors - which allow large numbers of heap mutations to be ignored - without affecting the correctness or completeness of the algorithm. We provide detailed performance comparisons of concurrent and non-concurrent versions of our cycle collector, a simple mark-sweep cycle detector, and a high-performance implementation of trial deletion.

Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>

Last modified: Tue May 31 12:56:01 EST 2011