OOPSLA '04

Program
Technical Program
  Invited Speakers
  Technical Papers
  Onward!
  Panels
  Practitioner Reports
  Tutorials
Workshops
DesignFest
Educators' Symposium
Demonstrations
Posters
Doctoral Symposium
Exhibits
Student Research Comp.
FlashBoF
 
Turing Lecture
 
Social Events
 
Week at a Glance
 
Final Program (1.5M .pdf)

Find in Program
 

Page
Printer-friendly

Basket
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
 


 
7·8·9·10·11·12·13·14·15·16·17·18·19·20·21

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.