The free (fast but perilous) and automatic memory (safe but with
its own costs).
The simplest heap gives the programmer two operations: allocate(size) hands back a block
of free memory, and free(block) returns it. The manager keeps a free list
of available blocks and, on each request, must find one big enough (first-fit, best-fit, and so on).
The trouble is fragmentation. External fragmentation is free memory scattered
into many small blocks: you may have a megabyte free in total yet be unable to satisfy a request for a
contiguous kilobyte. Internal fragmentation is space wasted inside a block that was
rounded up to a convenient size. Both waste memory that the bookkeeping says is "free".
Worse, manual free is a minefield: free too early and you get a dangling pointer;
forget to free and you get a memory leak; free twice and you corrupt the allocator. Automatic
garbage collection exists to take this hazardous decision out of the programmer's hands.
A collector cannot know the programmer's intentions, so it uses a computable proxy for "will never be used again": reachability. Start from the roots — the pointers the program can access directly, namely the local variables and parameters in the active stack frames, plus the global/static variables and machine registers. Any object reachable by following pointers from a root is live. Everything else is garbage, provably unreachable, and safe to reclaim.
Reachability is a graph problem. Model the heap as a directed graph — objects are nodes, pointers are edges — and garbage collection becomes "find every node reachable from the roots; free the rest." Reveal a mark step by step:
Notice the two islands on the right: an unreachable pair, and an unreachable cycle. Neither is reachable from the root, so both are garbage — even though the objects in the cycle still point at each other. That cycle is the exact case that defeats reference counting, as we will see.
The oldest tracing collector is mark-and-sweep. Phase one (mark) does a graph traversal from the roots, setting a "mark" bit on every reachable object. Phase two (sweep) walks the entire heap and frees every object whose mark bit is not set (clearing the bits for next time). This tiny implementation reports exactly which nodes it reclaims:
The cycle F ↔ G is collected without trouble: a tracing collector asks "reachable from a
root?", and the cycle is not, so both go. The marked check is also what stops the traversal
from looping forever on that cycle.
Mark-and-sweep is one point in a rich design space. The main algorithms trade throughput, pause time, memory overhead, and fragmentation against each other:
| Algorithm | Pros | Cons |
|---|---|---|
| Reference counting | immediate reclamation; incremental; simple; no global pause | cannot collect cycles; per-pointer-write overhead |
| Mark-and-sweep | collects cycles; no object movement | stop-the-world pause; sweep touches whole heap; leaves fragmentation |
| Copying (Cheney's) | compacts (no fragmentation); allocation is a pointer bump; cost ∝ live data only | needs two semispaces (½ heap wasted); moves objects (must update pointers) |
| Generational | fast, frequent minor collections; exploits that most objects die young | needs a write barrier to track old→young pointers; occasional full collection |
Reference counting keeps a count of incoming pointers in each object; when it hits zero the object is freed at once. Cheney's copying collector divides the heap into two semispaces and, on collection, copies every live object from "from-space" to "to-space" in a single breadth-first pass — compacting them and leaving from-space entirely empty. Generational collectors segregate objects by age and collect the young generation often and cheaply.
Generational collection rests on an empirical observation so reliable it has a name:
If that is true, then concentrating collection effort on the youngest objects gives the biggest payoff for the least work. A generational collector puts new objects in a small nursery and collects it frequently (a cheap minor collection touching only young objects); the few survivors are promoted to an older generation that is collected rarely (an expensive major collection). Because minor collections scan only a small, mostly-dead region, they are fast and their pauses are short — which is why generational GC underpins the JVM, .NET, and V8.
There is a catch that a write barrier handles: a minor collection scanning only the nursery would miss a live young object that is referenced only from an old object. The write barrier is a small piece of code on every pointer store that records such old→young references in a remembered set, so they can be treated as extra roots for the nursery.
A stop-the-world collector halts the application ("mutator") completely while it collects, then resumes it. Simple and correct, but it introduces pauses — unacceptable for a game, an animation, or a trading system. Incremental and concurrent collectors interleave collection with the running program, doing a little work at a time (or on another thread) to keep pauses short. The price is coordination: because the program keeps mutating the graph while it is being traced, the collector needs barriers to avoid missing an object that the mutator moves behind the collector's back — the celebrated tri-colour invariant. It is throughput traded for latency.
Because the cost of a tracing collection is dominated by the live data it must copy or mark, not the garbage it reclaims — garbage is free to ignore. A full collection must trace every live object in the entire heap, including the long-lived ones that were live last time and will be live next time too; you re-do that work for nothing. A minor collection touches only the nursery, where almost everything is already dead, so it does a tiny amount of tracing to reclaim a lot of space. The generational trick is not that young objects are special to collect — it is that old objects are expensive to keep re-scanning, so you scan them as rarely as you can get away with.
Two traps. First, reference counting cannot reclaim cycles. If object
F points to G and G points back to F, each keeps
the other's count at one even after the program has dropped all outside references — the count never
reaches zero, and the pair leaks forever. This is the reason pure reference counting is
usually paired with a backup tracing collector (or weak references) to catch cycles. A tracing
collector has no such problem: an unreachable cycle is simply unreachable.
Second, conservative vs precise. A precise collector knows exactly which words are pointers (the compiler emits maps), so it can move objects and never errs. A conservative collector (used when you cannot get that type information, e.g. collecting C) must treat any word that looks like a pointer as one — so an integer that happens to equal a heap address will pin a dead object alive, and no object can safely be moved, since you dare not overwrite a value that might really be an integer. Conservative GC is a pragmatic guess; precise GC is the real thing.