Tricolor marking is usually explained like this: white means not found, grey means queued, black means scanned. All correct, and about equally useless, because the real question never gets asked: why three colors at all, when graph traversal needs exactly two — visited and not visited?

Here is why. The third color exists for one reason only: the program does not stop while the collection runs. This post is about what follows from that. At the end there is an interactive sandbox where you can switch the write barrier off and watch the GC eat a live object.

Why a third color

A naive collector does mark & sweep in one STW pause: stop the world, walk the graph from the roots, free everything you did not reach. Correct, simple — and the pause is linear in the size of the live heap. With 10 GB of live data that is seconds, not microseconds.

Go took a different route back in 1.5: marking runs concurrently with the program (Go 1.5 GC: prioritizing low latency and simplicity). The world stops twice and briefly — to turn the barrier on and scan the roots, and to terminate marking. Since Go 1.8 those pauses are “usually under 100 microseconds and often as low as 10” (Go 1.8 release notes) — and, crucially, they no longer scale with heap size.

But concurrency creates a problem that simply does not exist in an STW collector. While the collector walks the graph, the mutator (the term comes from Dijkstra et al., 1978 — the program that mutates the object graph during traversal) rewrites pointers. And two colors are no longer enough.

Picture this: the collector has fully scanned object B — read all its fields, it will never come back to it. At that moment a goroutine runs B.next = W, where W is a white object that has not been found yet, and simultaneously clears the only other reference to W. Formally W is alive: it is reachable from the roots through B. In practice the collector will never find it — it has already been inside B.

That is the classic lost object. Three colors exist to catch it: “scanned” (black) and “found but not scanned” (grey) are fundamentally different states, and the correctness rule is stated in terms of exactly that difference.

1 · marker has scanned BBblackXWwhite2 · mutator: *B = W; X = nilBXWwhite behind black3 · sweepBWfreed · still live
The marker never revisits black objects — so a pointer that appears inside a black object after it was scanned has to be caught separately

The invariant and the barrier

The rule that holds the whole construction together comes in two flavors.

Strong invariant: a black object never holds a pointer to a white one. Weak invariant: a black object may point to a white one, but only if that white object is also reachable through a chain from some grey object. The weak form admits more states and is therefore cheaper to maintain — and it is the one Go relies on.

The invariant has to be enforced at the moment it can be broken, which is when a pointer is written into the heap. Hence the write barrier — a small piece of code the compiler injects before every such write. In the textbook (Dijkstra) form it does exactly one thing: if the value being written is white, shade it grey, i.e. push it onto the marker’s queue. A white object hidden behind a black one immediately stops being white.

Real Go has used a hybrid barrier since 1.8 — a combination of Yuasa’s deletion barrier and Dijkstra’s insertion barrier (proposal 17503, Clements & Hudson). The pseudocode comes straight from the comment in runtime/mbarrier.go:

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

That first line is the difference from the textbook version: it shades the old value of the slot, not just the new one. The point is to give the collector a snapshot of the graph as of the start of the cycle — a pointer the mutator tears down still ends up in the queue. This is what let Go drop the final stack re-scan under STW, the nastiest pause in the pre-1.8 design, which grew linearly with the number of goroutines.

The barrier costs something on every pointer write, which is why Go only enables it for the duration of a cycle — outside marking it is off and the code takes the fast path.

Two consequences follow that textbooks tend to mention in passing, and that are exactly what makes the scheme work in practice.

Objects allocated during a cycle are born black. Not grey — black. The logic is simple: the object was just created, there is nothing inside it to scan yet, and shading it grey would have the marker forever chasing an allocating goroutine. The price is that such objects are guaranteed to survive to the next cycle even if they are garbage. That is a deliberate trade: floating garbage in exchange for termination.

Mark assist. A goroutine that allocates must itself do marking work proportional to what it allocated. Without it, a single allocating goroutine easily outruns the background markers, the heap grows faster than it is scanned, and the cycle never converges. Assist is backpressure built into the allocator; the proportions live in the pacer, rewritten in Go 1.18.

This is why “the GC is eating CPU” often shows up in practice as “allocating goroutines got slow”: the time is spent in assists, not in background workers.

STWbarrier on,rootsconcurrent markgrey → black · program keeps running · barrier catches writes · mark assistSTWterminationconcurrent sweepwhatever stayed white is garbage

block widths are illustrative: STW pauses are tens of microseconds, marking is milliseconds and up

One GC cycle in Go: the world stops twice and briefly, all the heavy lifting runs alongside the program

One more property worth stating out loud: tricolor marking happily collects garbage cycles. An A → B → A pair unreachable from the roots stays white and gets freed — no special-case code required. That is the fundamental advantage over reference counting, where a cyclic pair lives forever.

The sandbox

Below is an interactive model of a single marking cycle. On the left, the root set: goroutine stacks and globals. On the right, the heap: objects with references you can drag, link and unlink.

Click two objects to link them; click an arrow to drop the pointerOpen the sandbox in a new tab ↗

What to try, in order:

  1. Hit “Step” and watch the “Grey set” panel. That is the marker’s queue. Each step: pop an object, read its pointers, shade white targets grey, turn the object itself black. The cycle ends when the queue is empty.
  2. Switch the mutator on. Now pointer writes and allocations happen alongside marking. Notice that new objects show up black right away — that is allocate-black — and watch the log for barrier hits.
  3. Switch the write barrier off and press “Experiment: lose an object”. The mutator moves a white object behind a black one and clears the original reference. The marker does not revisit black — and on the sweep phase a live object gets freed. Exactly the bug the barrier prevents.
  4. Switch the barrier back on and repeat the experiment. The write shades the white object grey, a [barrier] line appears in the log, and the object survives the cycle.
  5. Run the first cycle to completion and find the F ⇄ G pair — a garbage cycle that gets freed with no special-case code.

One honest caveat about the model: the barrier in the sandbox is the classic Dijkstra insertion barrier, “black got a pointer to white → shade the white grey”. Real Go, as noted above, uses the hybrid barrier and also shades the slot’s old value. For seeing why a barrier is needed at all, the insertion variant is plenty; for reading mbarrier.go, it is not.

What changed with Green Tea

Everything above — the invariant and the barrier — still holds, but the heap traversal itself works differently in recent Go. Go 1.25 shipped the experimental Green Tea collector (issue #73581), and in Go 1.26 it is on by default; the old design lives behind GOEXPERIMENT=nogreenteagc and is expected to be removed in 1.27.

The idea: the classic marker chases individual pointers scattered across memory, and on small objects that destroys cache locality — every queue step is a near-guaranteed miss. Green Tea works with pages rather than individual objects: what turns grey is a span, and the marker processes it whole, sequentially in memory. The quoted win is a 10–40% reduction in GC overhead on real programs, plus roughly another 10% on recent amd64 (Ice Lake / Zen 4 and newer) thanks to vector instructions over the page bitmaps.

What matters for this article: the unit of marking work changed, not the protocol. Three colors, the invariant and the write barrier are all still there — it is still concurrent tricolor marking, the queue just holds pages now instead of objects.

References