Garbage Collection: Automatic Memory Management

The Problem: Manual Memory Management

A program running on a computer needs memory to hold its data. In the simplest model, the programmer asks the operating system for a block of memory (allocation) and gives it back when finished (deallocation). In languages like C, these are the malloc and free calls. The model is fast and predictable, and it puts the programmer in complete control.

It also produces two of the most persistent classes of bug in the history of software:

• Memory leaks — memory that is allocated but never freed. A long-running program slowly consumes all available memory until it crashes or the machine grinds to a halt.
• Dangling pointers and use-after-free — memory that is freed while some part of the program still holds a reference to it. The reference now points at memory that may be reused for something else, producing corruption that often manifests far from its cause and is notoriously hard to debug. This same class of bug is the root of a large share of security vulnerabilities (see Rust and Memory Safety).

Tony Hoare’s “billion-dollar mistake” — the null reference — is the most famous single example of how memory-handling errors compound (see Tony Hoare and the Science of Programming). Manual memory management makes a programmer responsible for getting every allocation and deallocation exactly right, across every possible path through a program. Humans are bad at this.

McCarthy’s Invention: LISP, 1959

The first garbage collector was built because LISP made manual memory management impractical. LISP programs are built from cons cells — small two-pointer structures that are allocated constantly and linked into lists and trees whose lifetimes are impossible to predict statically. Asking the programmer to free each cell by hand was a non-starter.

John McCarthy, designing LISP at MIT, introduced automatic garbage collection in 1959. The idea: let the program allocate freely, and when memory runs low, pause execution, find all the data that is still reachable from the running program, and reclaim everything else. The programmer never calls free. The system figures out what is garbage.

McCarthy’s original algorithm was mark-and-sweep. Starting from a set of “roots” (the variables the program can currently see), the collector traverses every reachable object and marks it. Then it sweeps the entire heap, freeing anything left unmarked. Everything the program can still reach survives; everything it cannot is, by definition, unreachable and safe to reclaim.

The Core Algorithms

Three families of algorithm have dominated, each addressing the weaknesses of the last.

Reference counting. Each object keeps a count of how many references point to it. When the count drops to zero, the object is freed immediately. Simple, and reclamation is prompt — but it cannot collect cycles (two objects referencing each other but nothing else keeps them both alive at a non-zero count forever), and updating counts on every pointer assignment is expensive. Reference counting powers CPython, Swift (via ARC), and Objective-C.

Mark-and-sweep. McCarthy’s original. No cycle problem, but the classic version requires stopping the program entirely while it runs — the dreaded “stop-the-world” pause — and it fragments memory over time.

Copying / generational collection. The key empirical insight, formalized in the 1980s, is the generational hypothesis: most objects die young. A short-lived temporary variable is far more common than a long-lived one. Generational collectors split the heap into a “young” generation, collected frequently and cheaply, and an “old” generation, collected rarely. New objects are allocated in the young generation; survivors are promoted to the old. This concentrates collection effort where the garbage actually is, and it is the basis of most high-performance collectors today.

The Long Skepticism

For thirty years, garbage collection was treated as a luxury for academic and AI languages — LISP, Smalltalk, Prolog — but unacceptable for “real” systems programming. The objection was performance: GC consumed CPU cycles and memory, and the stop-the-world pauses made it unsuitable for anything with timing requirements. Serious software was written in C and C++, where the programmer controlled every byte.

The skepticism was not unreasonable for the hardware of the era. It became wrong gradually, as memory grew cheap, processors grew fast, and the dominant cost in software shifted decisively from machine time to programmer time and security incidents.

Java and the Mainstream Breakthrough

The turning point was Java (1995). Sun Microsystems shipped garbage collection as a non-negotiable, built-in feature of a language explicitly aimed at mainstream commercial development (see James Gosling and Java and The JVM and Java Ecosystem). Java made the trade openly: you give up manual control, you get a language where an entire category of catastrophic bug simply does not exist. Enterprise developers, who valued reliability and development speed over squeezing the last cycle from the hardware, took the deal en masse.

Java’s success made GC the default expectation. The HotSpot JVM became one of the most heavily engineered garbage-collection platforms ever built, with a succession of collectors — Serial, Parallel, the Concurrent Mark-Sweep collector, G1 (Garbage-First), and later the low-pause ZGC and Shenandoah — each chasing the goal of high throughput with shrinking pause times. JavaScript (V8), C# (.NET CLR), Python, Ruby, Go, and most languages designed since have all assumed garbage collection as a baseline.

The Pause-Time War

Once GC was mainstream, the engineering frontier became latency, not throughput. A stop-the-world pause of a few hundred milliseconds is invisible in a batch job and catastrophic in a trading system, a game, or a web service with a latency budget. The modern history of garbage collection is largely the history of shrinking and hiding pauses:

• Concurrent collectors do most of their work while the application keeps running, stopping it only briefly.
• Incremental collectors break collection into many small steps.
• Region-based collectors like G1 divide the heap into regions and collect a subset at a time, trading completeness for predictable pause times.

By the 2020s, collectors like ZGC and Shenandoah were achieving sub-millisecond pauses on multi-terabyte heaps — a result that would have seemed like fantasy to GC’s early critics.

Dead End: The Pause-Free Dream and Manual’s Comeback

Garbage collection never delivered the fully “free” memory management its early advocates implied. Two limits proved durable.

First, GC trades latency predictability for convenience, and for hard-real-time systems — avionics, engine controllers, high-frequency trading — that trade is unacceptable. These domains still avoid GC or use tightly restricted subsets, because a pause you cannot bound is a pause you cannot ship.

Second, and more interesting, the 2010s saw a partial reversal. Rust demonstrated that memory safety — the actual goal — does not require garbage collection at all. Through its ownership and borrowing system, Rust achieves safety at compile time, with no runtime collector and no pauses (see Rust and Memory Safety). This reframed a debate that had seemed settled: the choice was never “safety vs. speed,” it was “safety via runtime bookkeeping vs. safety via compile-time analysis.” For four decades, garbage collection was the only practical answer to memory safety. Rust proved it was not the only possible one — a reminder that even a “won” argument in computing can be reopened by a better idea.

📚 Sources

• John McCarthy — “Recursive Functions of Symbolic Expressions” (1960)
• Paul Wilson — “Uniprocessor Garbage Collection Techniques” (survey)
• Oracle — HotSpot Virtual Machine Garbage Collection Tuning Guide
• The Garbage Collection Handbook (Jones, Hosking, Moss)
• Rust Documentation — Ownership