Garbage Collection
Advanced Memory Management · Memory & Systems track
6 min read
In this module
Automatic Memory Management
In C and C++ the programmer frees every allocation themselves. In languages with garbage collection (Java, Go, Python, JavaScript, C#), the runtime quietly reclaims memory the program can no longer reach. Understanding how a GC works lets you write performant code in those languages — and helps you weigh GC against manual memory management when you have the choice.
A garbage collector reclaims unreachable memory automatically. The trade-off is determinism: you give up precise control over when memory is freed in exchange for not having to free it yourself.
Reference Counting
The simplest GC strategy is reference counting. Every object carries a counter for how many references point to it. Create a reference, counter goes up. Drop a reference, counter goes down. Hit zero and the object is unreachable, so free it immediately.
obj = allocate() # refcount = 1ref2 = obj # refcount = 2ref2 = null # refcount = 1obj = null # refcount = 0 -> free immediatelyWins: deterministic destruction (you know exactly when objects die), no pauses (each operation does a sliver of work), simple implementation.
Losses: can't reclaim cycles (A references B, B references A; both refcounts sit at 1 even when nothing else points at either), overhead on every reference assignment (increment/decrement), and cache-hostility — every reference change pokes the object's refcount.
Here's reference counting done by hand in C, with two objects that point at each other. Predict both refcounts after the program drops its own references, then run it.
Both counts sit at 1 forever, each kept alive only by the other. A tracing collector starting from the roots would never reach them and would free both.
Swift uses reference counting (Automatic Reference Counting, ARC) with a cycle-breaking escape hatch. The programmer marks certain references as weak or unowned to snap cycles. Python uses reference counting as its primary GC and adds a supplementary cycle collector for the leaks reference counting alone leaves behind.
Languages that use reference counting as their primary GC need a supplementary algorithm to detect cycles. Python's cycle collector periodically traces objects that participate in cycles (objects with reference counts greater than zero that reference other objects). It builds a graph of these objects, tentatively decrements reference counts along the graph edges, and collects objects that reach zero - indicating they were only reachable through cycles.
Mark-and-Sweep
Mark-and-sweep is the foundational tracing GC algorithm. It runs in two phases:
- Mark phase: starting from roots (global variables, stack variables, registers), walk all reachable objects by following references. Mark each one as live.
- Sweep phase: scan every allocated object. Anything unmarked is unreachable; free it. Clear the mark bits on the survivors.
Mark-and-sweep handles cycles for free. If A and B reference each other but no root reaches either, the mark phase never touches them, and the sweep phase collects them both.
Here's a small heap at the moment a collection starts. Follow the arrows out from the two roots: everything you can reach gets marked. The rest gets swept.
Config is reachable two ways and gets marked once. A and B point at each other, so reference counting would keep them both alive at a count of 1 each forever. Tracing doesn't care about counts, only reachability, so they're swept along with the orphaned buffer.
The big drawback is the stop-the-world pause. During marking the program has to pause (or at least be heavily restricted) so the object graph doesn't shift mid-collection. For a heap with millions of objects, that pause runs into tens or hundreds of milliseconds. Latency-sensitive applications can't stomach it.
Generational GC
Real-world programs obey the generational hypothesis: most objects die young. Temporary strings, loop variables, intermediate calculation results — born, garbage, gone in short order. Objects that survive several GC cycles tend to stick around a long time. They're probably long-lived data structures.
Generational GC exploits this by carving the heap into generations (typically 2 or 3):
- Young generation (nursery): newly allocated objects land here. Small region, collected often with a fast copying collector.
- Old generation (tenured): objects that survive several young-gen collections get promoted here. Larger region, collected rarely.
Young-gen collection is fast because the nursery is small, most of its objects are dead, and a copying collector only has to relocate the few survivors (no sweeping the bulk dead).
The wrinkle is references from old to young objects. If an old object points at a young one, that young object is live even when no young-gen root reaches it. Write barriers — tiny code sequences inserted before every reference store — catch those cross-generational references and stash them in a remembered set the young-gen collector consults.
Concurrent GC
Modern garbage collectors minimise pauses by running concurrently with the application:
Java's G1 (Garbage First) carves the heap into regions and collects the regions holding the most garbage first (hence the name). Most marking happens concurrently with the application, with brief stop-the-world pauses at the start and end. The copying is a different story: G1 evacuates live objects out of the chosen regions inside stop-the-world pauses, and those young and mixed collections are where most of its pause time goes. You give it a target (200 ms by default) and it picks how many regions to evacuate to stay near it.
Go's GC is a concurrent tri-colour mark-and-sweep collector. Three colours: white (not yet seen), grey (seen but not fully scanned), black (fully scanned). The collector starts by marking roots grey, then drains the grey set — marking their children grey, flipping themselves black — concurrently with the application. A write barrier preserves the invariant that a black object never directly references a white one.
ZGC and Shenandoah (Java) target sub-millisecond pauses regardless of heap size. Both relocate objects concurrently, moving them while the application keeps running. ZGC tracks GC state with coloured pointers (spare bits in 64-bit pointers tag each reference), while Shenandoah relies on forwarding pointers and load barriers that redirect accesses to an object's new copy.
GC Pauses and Their Impact
GC pauses bite latency. When the collector freezes the application, no requests get processed, no frames render, no real-time deadlines hold. The impact depends on the workload:
- Batch processing: pauses barely register. Total throughput is what counts.
- Web servers: pauses spike tail latency. A 50 ms pause shows up at the 99th percentile.
- Real-time systems: any pause can be a deal-breaker. Games target 16 ms frames; a 20 ms GC pause is a visible stutter.
Comparing to Manual Management
Manual memory management (C, C++, Rust) sidesteps GC pauses entirely. The price tag: programmer burden and a bestiary of bugs (use-after-free, double-free, leaks). Domain matters here. Systems programming and real-time applications lean manual; application development and rapid prototyping lean GC. Rust's borrow checker stakes out a third spot: compile-time memory safety without a garbage collector.