How Garbage Collectors Decide What to Free

Garbage collection is not magic. It is a set of trade-offs disguised as convenience. When you allocate an object and let the runtime "handle cleanup", a real algorithm is deciding, on a schedule it chooses, which objects are still alive and which are waste. The decision has a cost. The pause has a physics. And the reason your app stutters every few seconds is usually hiding in the collector's choices, not your code.

The two questions every GC answers

Every garbage collector, from the simplest mark-sweep to the most sophisticated concurrent collector, answers exactly two questions:

1. What is still reachable? — which objects can your program still access through its roots (stack variables, globals, registers)?
2. When can I reclaim the unreachable? — do I stop the world and do it all at once, or do I chip away at it while your code runs?

The answers to these two questions define the entire performance profile of a runtime. Java's G1, Go's tri-color concurrent collector, Python's reference counting — same questions, radically different answers.

The roots: where reachability starts

A garbage collector starts from the roots — the set of objects directly accessible without following any pointer:

roots
├── stack variables        (every live local in every active frame)
├── global/static vars     (anything the program declared at file scope)
├── registers              (the CPU's current working set)
└── interned objects       (string pools, class metadata)

From these roots, the collector walks every pointer — this is the mark phase. Every object it reaches gets tagged as alive. Everything untagged is garbage.

The critical insight: the collector does not know what your program will do next. It can only see what is reachable right now. An object that your program will use again in 1 microsecond looks identical to one that will never be used again. The collector has to guess, and the strategies for guessing well are where the interesting engineering lives.

Generation 0, 1, 2: the generational trick

The single most important optimization in garbage collection is the generational hypothesis:

Most objects die young.

This is empirically true in nearly every program. A function's local variables, temporary strings, intermediate calculations — the vast majority of allocated objects are used once and never again. The collector exploits this by splitting the heap into generations:

┌─────────────────────────────────────────┐
│  Old Generation (tenured)               │  ← objects that survived multiple collections
│  collected infrequently                 │
├─────────────────────────────────────────┤
│  Young Generation (nursery)             │  ← newly allocated objects
│  collected frequently, fast to scan     │
└─────────────────────────────────────────┘

Minor collections scan only the young generation. Since most objects there are dead, the scan finds almost nothing alive, reclaims almost everything, and finishes fast — typically sub-millisecond. The few objects that do survive get promoted to the old generation.

Major collections scan the entire heap. They are expensive, infrequent, and are where long GC pauses come from.

The math works out powerfully: if 95% of objects die in the young generation, a minor collection touches 5% of the surviving objects and reclaims 95% of the allocation. The old generation is scanned rarely, and the pause scales with live objects, not allocated ones.

Mark-sweep: the classic approach

The simplest complete GC algorithm:

1. Mark — start from roots, follow every pointer, tag every reachable object.
2. Sweep — scan the heap, free every untagged object.

Before mark:  [A]→[B]→[C]    [D]→[E]    [F]    [G]→[H]
              alive  alive     garbage   garbage  alive
 
After mark:   [A]→[B]→[C]    ···        ···     [F]→[G]→[H]
              tagged          untagged   untagged  tagged
 
After sweep:  [A]→[B]→[C]    [free]     [free]   [F]→[G]→[H]

The problem: fragmentation. Freeing objects leaves holes in memory. Subsequent allocations must find contiguous holes large enough, and over time the heap becomes Swiss cheese. The allocator must either coalesce adjacent free blocks (expensive) or use a free list (cache- unfriendly).

Moving collectors: the defragmentation answer

A compacting collector solves fragmentation by moving live objects into contiguous memory after marking. The catch: every pointer to a moved object must be updated. This is where object headers earn their keep — the collector leaves a forwarding pointer in the old location, and a second pass updates all references.

The cost is obvious: moving objects and updating pointers takes time proportional to the number of live objects. But the benefit is equally obvious: after compaction, the free space is one large contiguous block, and allocation becomes a simple pointer bump — the fastest possible allocation path.

Generational collectors combine these ideas: minor collections copy surviving objects from nursery to tenured (copying = compaction), and major collections compact the tenured space.

The pause problem

The fundamental tension in GC design:

A stop-the-world collector pauses your program, does all the work, then resumes. Simple, fast, and the reason Java apps have "GC pauses" measured in milliseconds.

A concurrent collector runs alongside your program — marking and sweeping while your code executes. The pause is only for the root scan (a few microseconds), but the concurrent work competes for CPU and cache lines, reducing throughput.

Go's collector is a good example: a concurrent, tri-color, mark-sweep collector that concurrently marks objects using a write barrier (it intercepts pointer writes to track references during the mark phase). The STW pauses are typically under 1ms — but the concurrent mark phase consumes ~25% of one CPU core.

Reference counting: the other model

Python and Swift use reference counting instead of (or alongside) tracing collectors. Every object carries a count of how many pointers reference it. When the count drops to zero, the object is freed immediately.

import sys
 
a = []           # refcount = 1 (a points to it)
b = a            # refcount = 2 (a and b both point to it)
del b            # refcount = 1 (only a points to it)
del a            # refcount = 0 → freed immediately

The advantage: no pauses. Objects are freed the instant they become unreachable. The disadvantage: overhead on every pointer operation. Every assignment, every function call that passes an object, every return must increment or decrement a reference count. And reference counting cannot handle cycles — two objects pointing to each other with no external references. Python solves this with a cycle detector that runs periodically, which is itself a tracing collector.

The performance profile is inverted from tracing: steady, predictable overhead instead of sporadic pauses. Whether that's better depends on your latency requirements.

What this means for your code

The practical consequences:

1. Allocation is cheap, collection is not. Modern allocators (thread-local allocation buffers, bump allocators) make new Object() nearly free. The cost is paid later, by the collector, at a time it chooses.

2. Promotion is the hidden cliff. Objects that survive the nursery get promoted to old generation, where they are scanned less frequently but are more expensive to collect. A long-lived cache that holds references to short-lived objects forces the young generation to be scanned on every minor GC.

3. GC pressure is not allocation rate — it's survival rate. Allocating many objects that die immediately is cheap (the nursery handles it). Allocating objects that survive into old generation is expensive (they must be traced on every major collection, forever).

4. The pause budget is a product decision. A 10ms pause is invisible to a batch job and catastrophic to a real-time trading system. The choice of GC algorithm is not a technical detail — it is a business requirement expressed in microseconds.