Garbage Collection

Tracing GC’s

These are collectors that use reachability to determine liveness. Tracing the transitive closure of the object graph to determine reachability.

There are 3 canonical types of tracing GC.

There’s also reference counting, which is simply where objects keep track of how many things are referring to them, and then, when that counter hits 0, the object is reclaimed. Reference counting is fast, but naive, it can’t cope with circular references, and is often used in conjunction with a tracing collector, for some specific purposes.


Immix is a GC algorithm developed by Steve Blackburn and Kathryn McKinley and presented in the paper Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance at PLDI08.

Immix introduces a fourth type of tracing GC: