A Unified Theory of Garbage Collection
📜 Abstract
Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved — that they seem to share some deep structure. We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or “matter”, while reference counting operates on dead objects, or “anti-matter”. For every operation performed by the tracing collector, there is a precisely corresponding anti-operation performed by the reference counting collector. Using this framework, we show that all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of tracing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the expected properties of the target application.
✨ Summary
The paper develops a unified mathematical and algorithmic framework for garbage collection. Its central result is that tracing and reference counting can be understood as dual processes: tracing tracks reachable objects, whereas reference counting tracks objects becoming unreachable. The paper formalizes this relationship using graph traversal, fixed-point semantics, and corresponding work-list algorithms.
It further argues that practical high-performance collectors are hybrids of the two approaches. Deferred reference counting, generational collection, and multi-heap collectors are analyzed as different assignments of tracing and reference-counting responsibilities across roots, heap regions, and inter-region references. A common cost model is introduced to compare time and space overheads and to guide collector selection for different workloads.
The framework has continued to serve as a reference point in garbage-collection research and education. The Garbage Collection Handbook includes a dedicated treatment of the unified theory, and later instructional material explicitly uses the paper’s duality and fixed-point formulation to explain tracing, reference counting, and hybrid collectors. (gchandbook.org) A recent research paper on concurrent partial tracing explicitly identifies Bacon, Cheng, and Rajan as the source of the partial-tracing formulation and revisits that design for safe, concurrent memory reclamation. (jhyeon.kim) The search found clear research and educational influence, but no publicly documented production system whose design is directly attributed to this paper. The paper’s bibliographic record and abstract were verified against IBM Research metadata and the paper text. (research.ibm.com)