Model the heap as a table of objects addressed by integer ids so tracing, marking, sweeping, and copying all return exact ids you can assert against - no real pointers, no host GC to fight. Every lesson is one concrete spec with exact surviving and reclaimed id sets: tracing the reachable set from the roots, a reachable cycle that survives while an unreachable cycle is reclaimed (the case reference counting cannot collect), the tri-color mark loop with no black object pointing to a white one, sweep reclaiming exactly the white set, allocation that collects and retries or returns out of memory, and a copying collector that copies a shared object exactly once and compacts the survivors.
Over 32 lessons you build a working tracing garbage collector from scratch, modelled over a simulated heap: a table of objects where every object is addressed by an integer object id (a Ref) and holds a small set of fields that are themselves Refs, plus an explicit root set. Because you cannot intercept a host language's real pointers, this simulated heap makes every collection fully deterministic and exactly testable - you can assert precisely which ids survive, which are reclaimed, and the exact free space and new addresses. It is the same simulated-heap discipline as the companion Build a Memory Allocator project, one level up: there you handed out memory, here you reclaim it automatically.
You start with the object model - allocating objects, wiring their reference fields into a graph, and the root set - then compute reachability by tracing from the roots, handling shared objects and cycles (a cycle reachable from a root survives; an unreachable cycle is garbage, the exact case reference counting cannot collect). On that foundation you build a full tri-color mark-sweep collector: greying the roots, blackening the reachable set, sweeping every still-white object into a free list, and allocation that triggers a collection and retries or fails cleanly with out of memory. Then you build a second collector - a copying semispace collector using Cheney's algorithm - that copies each reachable object to a fresh space leaving a forwarding pointer, updates every reference, copies a doubly-referenced object exactly once, and compacts the survivors as a side effect. The capstone runs both collectors over one graph with a shared node, a root-reachable cycle, and an unreachable cycle and asserts the exact surviving and reclaimed ids.
This is a teaching-grade tracing garbage collector built as a library: a managed heap plus mark-sweep and copying collectors you import and drive through a small API. It is honest about what it stops short of - it collects only when you call it or when allocation runs out (it is stop-the-world, not concurrent or incremental), it introduces write barriers and a remembered set as a sketch rather than a full generational collector, and it has no finalizers or weak references - which is exactly the honest core that production collectors extend with concurrency, generations, and compaction refinements.
A garbage collector manages a heap of objects, so first we need a heap. Ours is a simulated one - a fixed table of object slots - so that every object has a plain integer id and every collection is fully deterministic and testable. Today you build that heap and report its capacity.
Create a heap with a fixed number of object slots and report how many it holds.
A real garbage collector runs inside a language’s runtime and manages memory the operating system handed it, chasing real pointers. That is impossible to test with exact values and different in every language, so we do the honest teaching version: a simulated heap. The heap is a fixed table of slots, one per object, and every object is identified by an integer id - the index of its slot. No real pointers, no runtime magic, and every result is a number you can assert.
Today is deliberately tiny: a heap of a chosen number of slots that reports its capacity and how many slots are live (in use). That capacity is the total number of objects our collector will ever hold at once - it never grows - so knowing it precisely is where everything starts. Every later lesson fills, traces, and reclaims these same slots.
// the whole collector will manage objects inside this one table of slotstype Heap struct {slots []*object // one slot per object; nil means the slot is free}func NewHeap(capacity int) *Heap { return &Heap{slots: make([]*object, capacity)} }func (h *Heap) Capacity() int { return len(h.slots) }func (h *Heap) Live() int { /* count non-nil slots */ }
The core tracing GC (mark-sweep and copying, with roots, cycles, a write barrier, and a remembered-set sketch) is complete and robust to bad input, but generational collection, incrementality, heap growth, and a real pointer/memory model are intentionally left as future work.
The definitive modern reference. Chapters on mark-sweep, copying collection, reference counting, and generational and incremental collection map directly onto this project - read it for the tri-color abstraction and Cheney's algorithm in full rigour.
The 1970 paper that introduced the copying collector this project builds in Chapter 4 - two semispaces, forwarding pointers, and a breadth-first scan that needs no recursion or extra stack. Two pages, still the clearest statement of the idea.
The classic survey (IWMM 1992) that maps the whole design space - mark-sweep, copying, generational, and incremental collection and the tradeoffs between them. The best single orientation to where the collectors here sit among the alternatives.
The 1978 paper that introduced the white/gray/black tri-color abstraction and the invariant this project leans on. The source for why a write barrier is needed once the program can run during marking.
A short, readable mark-sweep collector built in a single sitting - roots, reachability, the mark phase, and the sweep. The gentlest possible on-ramp to the core this project formalizes.
A tri-color mark-sweep collector inside a working language, with a tricolor worklist, the roots, and the write-barrier-adjacent gotchas explained clearly - the practical companion to the tri-color chapter here.