Incremental GC with Tri-Color Marking

The Problem With Stop-the-World Marking

The mark-and-sweep collector from two lessons ago marks everything in one uninterrupted pass. For a small heap that's fine, but as the live object graph grows, that pause — during which the entire program is frozen — grows with it. Tri-color marking restructures the mark phase so it can be done incrementally, a little at a time, interleaved with the running program, without ever leaving the heap in an inconsistent state.

Three Colors, One Invariant

Instead of a boolean marked flag, every object gets one of three colors:

• White — not yet visited. At the end of collection, white means garbage.
• Gray — visited (definitely reachable) but its own outgoing references haven't been scanned yet. Gray objects live on a worklist.
• Black — visited and fully scanned; every reference it holds has already been pushed onto the gray worklist (or was already gray/black).

The entire algorithm reduces to maintaining one invariant:

No black object may point directly to a white object.

As long as that holds, sweep can safely free every white object once the gray worklist is empty — anything a black object needs is guaranteed to be gray or black, never about-to-be-freed white.

Incremental Marking, One Step at a Time

Each call to step() processes exactly one gray object. A collect() that calls step() in a loop until the worklist is empty behaves identically to the old stop-the-world mark. But because step() is a discrete, resumable unit of work, a real VM can call it a bounded number of times between bytecode instructions — spreading GC pauses into many tiny slices instead of one long freeze. That's the entire payoff of tri-color: it turns "mark everything" into "mark a little, resumably."

Why the Mutator Breaks the Invariant

The catch: between marking steps, the program (the "mutator," in GC terminology) keeps running — and it can allocate new objects and store references. If the mutator takes a reference to a brand-new white object and stores it into a field of an already-black object, you've just violated the invariant: a black object now points to white. Sweep would free that white object even though the black object — which sweep will never re-scan, since it's already "done" — still needs it. That's a correctness bug, not a performance one: a live object gets collected.

The Write Barrier

The fix is a write barrier: a small check inserted at every place the program stores one heap reference into another.

This is the forward (Dijkstra-style) barrier: whenever a black object gains a reference to a white one, immediately gray the white target so it's guaranteed to be scanned before sweep runs. (A backward, Steele-style barrier instead re-grays the black src itself — different tradeoff, same goal: never let sweep observe a black→white edge.)

What to build

Implement alloc (white), insert_ref (with the write barrier above), step (process one gray object), and collect (seed roots as gray, then step() to completion, then sweep white objects). Verify the tri-color invariant explicitly: after any sequence of REF and STEP commands, no black object in your heap should have a white object in its refs list.