Garbage collection: from unacceptable to default in forty years

1960McCarthy, on the language he was building

Automatic reclamation of memory is as old as the second high-level language. The paper introducing the list-processing language describes it directly: when free storage runs out, the system finds everything still reachable from the program and reclaims the rest.

So the idea did not have to be invented later. What took forty years was making it acceptable.

1960s to 1990sThe objection, stated fairly

Three complaints, all legitimate at the time. Collection stops the program at moments the programmer cannot predict, which is intolerable for anything with a deadline. Tracing every reachable object costs time proportional to live data. And the collectors that were fastest needed roughly twice the memory, because they copied surviving objects into a second space.

On a machine where memory was the scarcest resource and pauses were measured in seconds, that is not a preference. It is a disqualification.

1980sThe observation that changed the arithmetic

The thing that made collection affordable was not a faster algorithm. It was noticing a property of real programs: the overwhelming majority of allocated objects become unreachable almost immediately, and the few that survive their first moments tend to survive for a long time.

If that holds, the collector does not need to examine everything. It can examine only the region holding recent allocations, which is small and mostly garbage, and visit the rest rarely.

What that buys

The cost of a collection stops being proportional to how much memory is in use and becomes proportional to how much recent data survived, which is usually very little.

That single change turned a pause proportional to the heap into one proportional to a fraction of it, and it is the reason collection became usable in interactive software rather than only in batch work.

1990s onwardsThe other half of the argument

Meanwhile the cost of the alternative became visible. Manual memory management produces a specific family of defects: use after release, release twice, and never release at all.

Those are not ordinary bugs. The first two are frequently exploitable, they fail far from their cause, and they resist testing because they depend on timing and allocation order. Once security became a dominant concern, the comparison stopped being pauses against speed and became pauses against a category of vulnerability.

What it still does not solve

A collector manages memory and nothing else. Open files, locks, sockets and handles are not reclaimed by reachability, because the right moment to release them is when the program is finished with them, not when the memory happens to be needed.

Which is why every language with a collector has a second, separate mechanism for releasing everything that is not memory, and why the commonest resource leak in collected languages is a file that was never closed.

2010sThe third answer

The argument was never only between manual release and tracing. A third position states ownership in the type system: the compiler knows which part of the program is responsible for each value and inserts the release, so reclamation is automatic without anything tracing at runtime.

It removes the pause and the memory overhead, and it charges for them at the point where the programmer must express ownership. That is a real cost, paid in a different currency, and it is why the question is still open rather than closed.

1960 onwardsReference counting, and why it is not the same thing

The obvious alternative to tracing is to keep a count of references on each object and release it when the count reaches zero. It is simple, it releases promptly, and its cost is spread evenly rather than arriving in a pause.

It also cannot reclaim a cycle. Two objects referring to each other keep each other alive forever, and cycles are ordinary in real data: a parent holding children that hold the parent, a graph, a cache with back-references. Systems that rely on counting therefore ship either a tracing collector for the cycles or a discipline requiring the programmer to break them by hand.

2000s onwardsWhat the pause became

The pause did not disappear; it was subdivided. Modern collectors do most of their work while the program runs, stopping it only for short phases, and the engineering effort behind that is enormous and almost entirely invisible to the people who benefit.

What has not changed is the shape of the guarantee. These are bounds that usually hold rather than limits that always do, which is why the remaining holdout domains remain holdouts.

present dayWhere it did not win

Operating system kernels, device firmware, hard real-time control and the tightest parts of games still avoid tracing collection, for the original reason: an unpredictable pause is not a performance characteristic there, it is a fault.

The victory is therefore partial and correctly so. Collection won everywhere the pause is affordable, which turned out to be almost all software, and lost everywhere it is not, which is a small and important remainder.

What we cannot verify

The original description and the later collector designs are published and checkable. The generational observation is supported by measurements across many systems, but the specific proportions vary enormously by workload and any single figure quoted for them is misleading. Comparisons of collected against manual performance depend on allocation patterns to a degree that makes general claims unsupportable.