The CS 6120 Course Blog

Unified Theory of Garbage Collection

by Mark Moeller


This week's paper, A Unified Theory of Garbage Collection (Bacon, Cheng, and Rajan (IBM)), appeared in OOPLSA 2004.

There are two classical algorithms for automatic garbage collection, tracing (also called mark and sweep), and reference counting, which were both first developed in the 1960s. Java's generational garbage collector is a typical example of a tracing collector, and CPython's garbage collector uses reference counting---but as this paper suggests, the reality is that these distinctions are certainly muddier in practice.

The two paradigms are associated important performance tradeoffs. In particular, the mark and sweep approach adds significant pauses to program progress, since in the simplest approach one must pause execution to "trace" all live objects before reclaiming unused space. Reference counting on the other hand does not have long pauses during execution, but rather pays for its overhead incrementally. Reference counting's major drawback is the difficulty presented by cycles appearing the link structure, which prevent objects' reference counts from ever reaching 0.


Bacon et al. begin by presenting the two fundamental garbage collection algorithms, reference counting and tracing, as dual views of the same underlying structure. This should hit you a bit like hearing that butter and I Can't Believe It's Not Butter have the same deep structure.

The deep comparison they make between the two paradigms is developed in a number of ways:

They go on to demonstrate that a whole continuum of hybrid approaches between the two not only make sense in principle but in fact really are already in use in practice. Here is a list of the the garbage collection strategies in rough order from most mark-n-sweepy to most-reference-county:

The paper concludes with a mathematical analysis of the costs of the above collection strategies. The authors point out that the analyses are not big-O, so these costs are actually "real", up to the accuracy of the constants for a particular system. It is not obvious to me that these particular constants even need to be constant on all systems. To the extent that these values might vary, certainly so would the validity of these results.

The analyses focus on computing the formulas for:

The computation of $\phi$ and $\kappa$ are kept separate, presumably because they quanitify the essence of the classic tradeoffs between tracing (large pauses) and reference counting (continuous overhead). Thus, by investigating the $\phi$ and $\kappa$ values of an approach one might be considering on the system one has in mind, one could evaluate where along the spectrum of hybrids the approach lies (on that system).

Merits of the paper

The duality between tracing and reference counting itself is a both mind-bending and extremely well developed. Given that the paper is really just offering this insight about a nice way to categorize existing garbage collection methods, its organization is quite nice. That is, they give the deep comparison abstractly in several different ways, then completely flesh out how existing hybrids combine the two flavors.

The section of the paper that has the most potentional to be practically important is the cost analysis in section 7. Having never constructed a garbage collection system for a whole language, I do not know whether a compiler designer would actually use these formulas to tune a garbage collector (even with knowledge of their particular domain) since they would have to validate any decisions against benchmark performance anyway.

Impact on state of the art

This paper does not technically offer any new approaches to storage reclamation (although to be sure, its authors have certainly done that in other works). On the other hand, it does seem like one of those papers that changes how one thinks about the topic forever. Of course, the extent to which it has done that for people in the field is certainly hard to know. It does seem, at least, that plenty of people spend a lot of time tuning the hybridization of their garbage collectors, so for them this paper gives a really nice framework for thinking about how to do that. (For those curious about more recent developments in this hybrid GC realm, there is Immix and its reference-counting-infused descendant, RCImmix).

They indicate their motivation for the cost analysis was actually to aid in development of dynamic construction of garbage collection algoirthms. That sounds like an interesting avenue for future work!

Discussion Questions

  1. The seminal papers they cite for reference counting and tracing were both from 1960. This one was 2004. Does it seem like this observation took a while? If so, why did it?
  2. This paper doesn't give any new algorithms or approaches for garbage collection. In what ways does the mere observation of this duality have value to the community?
  3. Can you give any situations or domains where using either (relatively) pure tracing or pure reference counting is advantageous over one of these "optimized hybrid approaches"?