1. 21

  2. 7

    Fascinating! Here’s the abstract:

    Tracing and reference counting are uniformly viewed as being fun- damentally 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 count- ing operates on dead objects, or “anti-matter”. For every operation performed by the tracing collector, there is a precisely correspond- ing anti-operation performed by the reference counting collector.

    Using this framework, we show that all high-performance col- lectors (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 trac- ing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the ex- pected properties of the target application.

    1. 7

      This is one of my favourite papers. I was a PhD student when it came out and it changed how I think about automatic memory management. Definitely worth a read!