A (Grand?) Unified Theory of Storage Reclamation

The two basic forms of automatic storage reclamation, tracing and reference
counting, were invented at the dawn of the high-level language era over 40
years ago. Since then there have been many improvements and optimizations,
but all systems are based on one or the other of these methods, which are
uniformly viewed as being fundamentally different and posessing 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 by the tracing
collector, there is a precisely corresponding anti-operation by the
reference counting collector.

Once viewed in this light, we show that all high-performance collectors are
in fact hybrids of tracing and reference counting (for example, deferred
reference counting and generational collection). We are developing a
uniform cost-model for the collectors to quantify the tradeoffs that result
from choosing different hybridizations of tracing and reference counting.
This will allow the correct scheme to be selected based on system
performance requirements and the expected properties of the target
application.

(joint work with Perry Cheng and V.T. Rajan)

David Bacon is a Research Staff Member at IBM's T.J. Watson Research Center.
He received his A.B. from Columbia University in 1985 and his Ph.D. in
Computer Science from the University of California, Berkeley, in 1997. His
algorithms are included in most compilers and run-time systems for modern
object-oriented languages, and his work on Thin Locks was selected as one of
the most influential contributions in the last 20 years of the Programming
Language Design and Implementation (PLDI) conference. His recent work
focuses on real-time and concurrent garbage collection, embedded systems,
programming language design, and computer architecture. He holds 4 patents
and has served on the program committees of POPL, OOPSLA, and ISMM. He is a
member of the ACM and IEEE.