Garbage Collection

Garbage collection (GC) is an automatic memory management technique in which a runtime system reclaims memory occupied by objects that are no longer reachable by a program. Unlike C or C++, where programmers manually allocate and free memory, garbage-collected languages like Java, Python, and Haskell delegate this responsibility to the runtime. The trade-off is predictability: garbage collection eliminates use-after-free errors and memory leaks caused by programmer omission, but introduces pause times that can destabilize latency-sensitive systems.

The design space of garbage collectors is vast. Mark-and-Sweep algorithms trace reachable objects; Reference Counting reclaims memory immediately when the last reference disappears; generational collectors exploit the empirical observation that most objects die young. Each strategy embodies a different theory about the lifetime distribution of program data — and each fails catastrophically when that theory does not match the workload.

The Memory Management Contract

Garbage collection redefines the contract between programmer and machine. In manual management, the programmer is responsible for every allocation and deallocation, and the runtime merely provides the raw memory. In garbage collection, the programmer creates objects and the runtime decides when they die. This inversion of responsibility is not merely a convenience. It is a change in the locus of control: the programmer delegates a class of decisions to the runtime, and in exchange receives freedom from a class of errors.

But the contract is not symmetric. The programmer gives up control over deallocation timing, and in return the runtime promises eventual reclamation. This 'eventual' is the source of most garbage collection problems. A garbage collector does not free memory when it becomes unreachable; it frees memory when it runs, which may be arbitrarily later. The gap between unreachability and reclamation is the space in which memory leaks, finalizer bugs, and resource exhaustion live.

The memory management contract also reveals a systems pattern: every delegation of responsibility to the runtime is a trade-off between programmer effort and runtime complexity. Garbage collection eliminates manual deallocation errors at the cost of introducing a new class of errors: pause times, finalizer ordering, weak reference semantics, and the interaction between GC and native code. The programmer is freed from one problem and bound to another.

Collector Architectures and Their Theories

Mark-and-Sweep

The mark-and-sweep collector operates in two phases. First, it traces all reachable objects from a set of roots (global variables, stack frames, registers) and marks them as live. Second, it sweeps the entire heap, freeing any object that was not marked. This is the simplest correct collector, and its simplicity makes it analyzable: you can prove that it reclaims exactly the unreachable memory. But its cost is proportional to the size of the heap, not the size of the live data, which makes it unsuitable for large heaps.

Reference Counting

Reference counting maintains a count of incoming references to each object. When the count reaches zero, the object is immediately freed. This provides deterministic reclamation — no pause times, no background threads — but introduces a catastrophic failure mode: cyclic references. Two objects that reference each other will never have their counts reach zero, even if they are unreachable from the rest of the program. This is not an implementation bug. It is a structural limitation: reference counting cannot reclaim cycles without an auxiliary tracing mechanism.

Generational Collection

Generational collectors exploit the empirical observation that most objects die young. The heap is divided into generations (typically young, old, and permanent), and collection is performed most frequently on the young generation, where the yield is highest. Objects that survive a threshold number of collections are promoted to an older generation. This strategy reduces the amortized cost of collection by concentrating effort where it is most effective.

The generational hypothesis — that object lifetimes are bimodally distributed — is not a law of nature. It is a statistical regularity observed in many programs, particularly those with short-lived temporary objects. Programs that violate this hypothesis — long-running simulations, object pools, persistent data structures — can suffer from generational