Technical Program
  Invited Speakers
  Technical Papers
  Practitioner Reports
Educators' Symposium
Doctoral Symposium
Student Research Comp.
Turing Lecture
Social Events
Week at a Glance
Final Program (1.5M .pdf)

Find in Program


view, help

"A Unified Theory of Garbage Collection"
Object-Oriented Programming, Systems, Languages and Applications
Home    Program    Housing & Transportation    Registration    Submissions    Wiki    Maps
  > Technical Program > Technical Papers > Garbage Collection

 : Tuesday

A Unified Theory of Garbage Collection

Meeting Rooms 1-3
Tuesday, 10:30, 30 minutes


David F. Bacon, IBM T.J. Watson Research Center
Perry Cheng, IBM T.J. Watson Research Center
V.T. Rajan, IBM T.J. Watson Research Center

Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that posess 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 tradeoffs 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.