Garbage collection pauses

Why does a program that frees its own memory sometimes freeze at the worst moment?

A service runs happily for hours, then stalls for two hundred milliseconds. No request was unusual; no lock was held. The runtime simply stopped every thread and did some housekeeping.

The folk explanation is that the program had made a lot of garbage and clearing it took a while. It is a natural inference and it gets the causality backwards. Ask what a collector actually does to a dead object, and the answer is: nothing. It never visits it, never reads it, never writes to it. Dead objects are cheap to dispose of precisely because they are unreachable — the collector could not find them if it tried. So if disposing of garbage costs nothing, what is the runtime doing for two hundred milliseconds?

It is answering a much harder question: which objects are still alive. And "alive" is not a property stored anywhere. It means reachable by some chain of references from a root — a local variable, a register, a static field — so establishing it requires walking the object graph and marking whatever is found. The cost of that walk is proportional to the live data, not to the garbage.

That single inversion explains most of what is surprising. A program allocating enormous quantities of short-lived rubbish can be cheap to collect, because almost nothing survives the walk. A program holding a large in-memory cache is expensive even when it produces no garbage at all, because the same live graph must be traced again and again.

Now, why stop the world? Because the program is editing the graph while the collector is reading it. If a thread moves the only reference to an object from a place the collector has already visited to one it has already passed, the collector concludes the object is dead and reclaims memory still in use. Concurrent collectors solve this only by making the program help: every reference write, or every read, goes through a barrier that reports the change. The pause has not vanished; it has become a tax on ordinary work.

Which brings us to the worst moment, and this is the part worth dwelling on, because it is not bad luck. Consider a generational collector, betting that most objects die young. Under light load that bet pays: by the time the nursery fills, nearly everything in it is dead. Now double the traffic. The nursery fills twice as fast, so each object has had half as long to become garbage — and objects still in flight for a request are, by definition, live. Survival rates rise, more objects get promoted into the older region, the older region fills, and the expensive full collection is triggered by exactly the traffic peak you least wanted it during.

The same correlation shows up in concurrent collectors. They reclaim memory at some rate alongside the program; if the program allocates faster than that, the runtime either makes the allocating thread do collection work itself — so throughput sags rather than stopping — or falls back to a stop-the-world collection. Both failure modes are load-triggered.

One contributor is easy to miss: before any collection begins, every thread must reach a safepoint where its state is inspectable. A thread inside a long loop with no safepoint check, or one that has just been descheduled or is faulting a page back in, holds up all the others. Some pauses attributed to collection are almost entirely the wait to begin collecting.

Three refinements.

First, "pause" and "cost" are different quantities and the tuning literature conflates them. A collector that never pauses can still consume a large share of your CPU and slow every reference write with a barrier. Modern low-latency collectors target sub-millisecond pauses largely independent of heap size, by moving nearly all the work concurrently and paying for it in throughput and memory headroom.

Second, headroom is the cheapest lever there is, and the least intuitive. Work per collection is set by the live set, while memory recovered is the heap minus the live set. So the amortised cost per byte allocated falls as the heap grows relative to what is live — a memory-hungry program can often be made faster simply by giving it more memory than it needs. Trading space for time is the defining property of the family.

Third, and honestly: none of this makes the alternative obviously better. Manual freeing spreads the cost thin and predictable across the program, at the price of a class of bugs — use-after-free, double-free, leaks — that tracing eliminates by construction. Reference counting frees promptly without a global trace, but pays on every pointer assignment, cannot reclaim cycles unaided, and can stall when dropping the last reference to a large structure cascades. No arrangement is short-pausing, high-throughput, and memory-frugal at once, which is why runtimes ship several collectors and ask you to choose.

• How write barriers and coloured pointers let a collector move objects while the program is still reading them.
• Why compaction matters even when memory is plentiful, and how fragmentation causes allocation failures in a mostly empty heap.

Every term the collection defines is gathered in the glossary.