In the last room you learned the discipline of the free list: every cell you take from AVAIL, you promise to give back. It is a gentleman's agreement with the machine, and like all such agreements it depends on nobody ever forgetting. But programs forget. A pointer is overwritten, a local variable goes out of scope, a thread of the list is dropped — and somewhere in memory a node still sits, fully allocated, holding its data, connected to nothing. You can no longer reach it, so you can no longer free it. It is not destroyed and it is not usable. It simply haunts the heap.
This is the specter of forgetting, and for a while it seemed to be the price of dynamic memory. Then, in 1959, John McCarthy hit a wall building LISP — a language whose every operation cons-es new cells into being — and asked a question that reframed the whole problem. Instead of trusting the programmer to remember which cells are dead, why not let the machine discover it? An object is worth keeping if and only if the running program can still reach it. Everything else, however it came to be, is garbage. Reclaiming it automatically he called garbage collection.
"Nothing in the heap is alive or dead in itself. A cell is alive precisely when the program can still find its way to it — liveness is reachability, and nothing more." — after J. McCarthy (1960) & D. E. Knuth, §2.3.5
I · Roots & ReachabilityWhat it means to be alive
The running program touches memory through a small, known set of handles: the machine registers, the variables on the stack, the global cells. Knuth calls these the roots. Anything the program can ever use, it must be able to reach by starting at a root and following pointers. So define an object to be live if it is reachable from some root, and garbage otherwise. This definition is exact, it is decidable, and — crucially — it does not care how a cell became unreachable. A forgotten node and a deliberately discarded one look identical to the collector: neither can be reached, so both may be reclaimed.
In the instrument below, the six boxes along the top are the roots. Each allocation drops a new object into the heap and wires it into the reachable structure. Then drop a root, or cut a link, and watch objects go dark — still occupying memory, but severed from every root. Keep allocating and the heap fills with the living and the forgotten alike, until it chokes. Then trigger the collector.
Mark-and-sweep runs in two phases over the whole heap. Mark: a trace from the roots paints every reachable cell gold. Sweep: a linear pass reclaims every cell the trace never reached — the forgotten — and clears the marks for next time. Cost is proportional to the heap, and the world stops while it runs.
II · Mark, then SweepThe two-phase exorcism
McCarthy's collector, refined by Knuth in §2.3.5, is disarmingly simple. Mark: give every cell a spare mark bit, initially clear. Starting from the roots, trace the pointer graph — depth-first or breadth-first — and set the mark bit of every cell you visit. When the trace is exhausted, every live cell is marked and every garbage cell is not. Sweep: walk the entire heap linearly from one end to the other; every marked cell you clear (ready for next time) and keep; every unmarked cell you return to the free list. Two passes, and the specter is banished.
The genius is in the accounting: the collector never has to know why a cell died. Unreachable is unreachable. It reclaims the deliberate discard and the honest mistake with the same indifferent sweep.
The bill comes in two forms. The sweep touches the whole heap, so a collection costs time proportional to all of memory, not just the garbage — and while the collector traces and sweeps, the mutator (your program) must hold still, lest the pointer graph shift underfoot. This is the dreaded stop-the-world pause. For McCarthy's interactive LISP it meant an unpredictable hitch mid-computation; for a modern web browser it is the difference between a smooth animation and a stutter. Half a century of research on garbage collection is, in one sentence, the war against that pause.
III · The Long LineageEverything after the sweep
Mark-and-sweep was the first answer, not the last. Reference counting (George Collins, 1960) takes the opposite tack: give each cell a tally of how many pointers aim at it, adjust the tally on every assignment, and free a cell the instant its count hits zero — no pause, but a fatal blind spot, for a cycle of cells that point only at each other keeps every count above zero and never dies. Copying collectors (Marvin Minsky, then Cheney's elegant 1970 algorithm) evacuate the live objects to a fresh region and abandon the old one wholesale, compacting the heap for free. Generational collectors exploit a deep empirical truth — most objects die young — by collecting the nursery often and the elders rarely. Tri-color marking makes the trace concurrent, shrinking the pause toward zero.
"An algorithm must be seen to be believed." — D. E. Knuth
Every managed runtime you have ever used — the JVM, the .NET CLR, Go, Python, and the JavaScript engine interpreting this very page — is running a descendant of McCarthy's idea, tracing liveness from roots so that you never have to remember to free a thing. The gentleman's agreement of the AVAIL list has been quietly automated away. The specter of forgetting still stalks the heap; we have simply built a machine to walk the corridors, lantern in hand, and lay to rest whatever the program can no longer find.