Generational Garbage Collection

The one observation that makes GC fast

Tracing the entire heap to find garbage is expensive — a full mark-and-sweep does work proportional to every live object you own, which in a long-running server can be tens of gigabytes. You do not want to pay that cost on every allocation pause. Generational GC sidesteps the problem with a single, empirically-grounded bet: most objects die young.

This is the weak generational hypothesis, and decades of heap profiling back it up. The temporary string you concatenated, the iterator you allocated inside a loop, the boxed integer returned from a method — the overwhelming majority of objects become unreachable within a few hundred kilobytes of allocation. Measured "infant mortality" runs from roughly 80% in well-tuned long-lived applications up to 98% in allocation-heavy workloads. David Ungar formalized the idea in 1984 with Generation Scavenging, and essentially every production managed runtime — the JVM, .NET CLR, V8, Ruby, Go's earlier collectors — has shipped a generational design since.

The trick: split the heap into a small young generation (the nursery, or Eden) where new objects are born, and a larger old generation (tenured space) for survivors. Collect the nursery constantly — it's tiny and almost everything in it is already dead. Collect the old generation only rarely, because objects that have survived this long tend to keep surviving.

The mechanism: minor GC, promotion, and survivors

Allocation is a bump-the-pointer operation in the nursery: increment a free pointer, and you have your object. No free list, no search. When the nursery fills, a minor GC fires.

The young generation is collected with a copying collector (Cheney's semispace algorithm). A copying collector does work proportional to the live objects — it walks reachable objects and copies them to a new space, then declares the entire old space free in one stroke. The dead objects are never even visited. Because the generational hypothesis guarantees the survivor set is small, a minor GC copies a handful of objects and reclaims the rest essentially for free:

minor GC cost = O(live young objects)   ← tiny, by the hypothesis
full GC cost  = O(entire live heap)     ← huge, and you avoid it

HotSpot refines the young generation into three spaces: Eden and two equal survivor spaces, S0 and S1 (default SurvivorRatio=8, so Eden is 8× one survivor). New objects go in Eden. Each minor GC copies live objects out of Eden and the occupied survivor space into the empty one, then swaps them — so one survivor space is always empty, ready to receive. Each object carries an age: the number of minor GCs it has survived. Once age crosses the tenuring threshold (HotSpot default MaxTenuringThreshold=15, lowered dynamically when survivor space is tight), the object is promoted to the old generation and stops paying the per-minor-GC copying tax.

The hard part: old objects pointing at young ones

A minor GC scans only the young generation. But what if an old object holds a reference into the nursery? Consider oldList.add(newItem): the long-lived list (old gen) now points at a freshly allocated element (young gen). If the collector traces only from the program's roots and the young generation, it will never see that old-gen pointer — and will wrongly reclaim a live object.

Scanning the whole old generation to find such pointers would defeat the entire purpose; the old generation is exactly the thing you're trying not to touch. The fix is to record these inter-generational pointers the moment they're created, using a write barrier: a tiny snippet of code the compiler injects after every reference-storing assignment.

// Conceptual write barrier on `obj.field = value`
store(obj, field, value)
if in_old_gen(obj) and in_young_gen(value):
    remember(obj)        // add to remembered set / dirty the card

The recorded slots form the remembered set. Most production collectors implement it as a card table: the old generation is divided into fixed-size "cards" (512 bytes in HotSpot), and the barrier just marks one byte in a side array — far cheaper than maintaining an exact set. On a minor GC, the collector scans only the dirty cards for old-to-young pointers and treats them as additional roots. The card table is the quiet workhorse that makes the whole scheme correct.

When generational GC wins — and when it doesn't

• High allocation rates with short-lived objects. Web request handlers, parsers, functional pipelines, anything that churns temporary objects — the nursery soaks up the garbage and minor GCs stay cheap. This is the sweet spot.
• Latency-sensitive services where you can tolerate frequent sub-millisecond minor pauses but want to push the rare big pause as far away as possible.
• Mixed object lifetimes, which is virtually every real program — a stable working set of long-lived objects plus a flood of transients.

It works against you when the hypothesis fails. A workload that allocates many objects which all survive a while — large caches being warmed, a big batch load, object pools that intentionally retain everything — sees objects copied repeatedly through survivor spaces before finally promoting, plus a write-barrier tax on every pointer store with little payoff. This is the classic "nepotism" / premature-promotion pathology: the nursery fills with survivors, tenuring threshold collapses, and you pay copying costs without the dead-object reclaim that justifies them.

Generational vs other collection strategies

	Generational copying	Mark-sweep (non-gen)	Mark-compact	Reference counting	Stop-and-copy (semispace)
Work per collection	O(young survivors) minor / O(live) full	O(live) mark + O(heap) sweep	O(live) twice (mark + move)	O(1) amortized per pointer op	O(live)
Common-case pause	Very short (minor only)	Full-heap every cycle	Full-heap every cycle	None (incremental)	Full live set every cycle
Fragmentation	None in young (copying compacts)	High — free list fragments	None — compacts	High	None
Memory overhead	Survivor reserve + card table	Mark bits + free lists	Mark bits	1 counter / object	2× heap (two semispaces)
Handles cycles?	Yes (tracing)	Yes	Yes	No — leaks reference cycles	Yes
Extra bookkeeping	Write barrier on every store	None	None	Inc/dec barrier on every store	None
Real-world use	JVM, .NET CLR, V8, Ruby RGenGC	Early Lisp, simple runtimes	HotSpot old-gen, Serial GC	CPython, Swift ARC, Perl	ML/Scheme runtimes

The key insight in this table: generational GC isn't a competitor to mark-sweep or mark-compact — it's a layering on top of them. The young generation uses copying; the old generation is typically collected with mark-sweep or mark-compact when the rare full GC finally fires. Generational is a partitioning strategy, not a tracing algorithm.

What the numbers actually say

• Minor GC is roughly 10–100× cheaper than a full GC. A minor GC on a 256 MB young generation that survives 2% of its objects copies ~5 MB and completes in single-digit milliseconds; a full GC of an 8 GB live heap can take hundreds of milliseconds to multiple seconds in a non-concurrent collector.
• Copying cost is paid only by survivors. If 98% of the nursery is dead, you copy 2% and reclaim 98% with a single pointer reset. The dead 98% costs literally zero CPU — the collector never touches it.
• The card table is cheap. A 512-byte card needs 1 byte of side table — about 0.2% memory overhead — and the write barrier is typically 2–3 instructions (compute card index, store a byte). HotSpot's barrier is unconditional precisely because branching would cost more than the redundant byte store.
• Tenuring threshold matters. Promoting too early bloats the old generation and triggers full GCs sooner; promoting too late wastes copying effort. HotSpot adapts the threshold (1–15) per collection based on survivor-space occupancy, targeting TargetSurvivorRatio=50%.

JavaScript implementation

A faithful two-generation copying collector with a remembered set, on a simplified object model. minorGC() copies young survivors via a Cheney-style scan; objects that age out are promoted; the remembered set supplies extra roots for old-to-young pointers.

const TENURE_AGE = 3;

class GenGC {
  constructor() {
    this.young = new Map();   // id -> { refs:[ids], age, gen:'young' }
    this.old   = new Map();   // id -> { refs:[ids], gen:'old' }
    this.roots = new Set();   // ids reachable from the stack/globals
    this.remembered = new Set(); // old-gen ids that point into young
    this.nextId = 1;
    this.allObjects = new Map(); // id -> object (the universe)
  }

  alloc(refs = []) {
    const id = this.nextId++;
    const obj = { id, refs: [...refs], age: 0, gen: 'young' };
    this.young.set(id, obj);
    this.allObjects.set(id, obj);
    return id;
  }

  // The write barrier: runs on every `obj.refs` mutation.
  writeRef(srcId, dstId) {
    const src = this.allObjects.get(srcId);
    src.refs.push(dstId);
    const dst = this.allObjects.get(dstId);
    if (src.gen === 'old' && dst.gen === 'young') {
      this.remembered.add(srcId);   // record inter-generational pointer
    }
  }

  // Minor GC: copy young survivors, reclaim the rest, promote old-enough ones.
  minorGC() {
    const survivors = new Map();
    const queue = [];
    const seen = new Set();

    // Roots = stack roots in young + remembered-set slots (old->young).
    const enqueue = (id) => {
      const o = this.allObjects.get(id);
      if (o && o.gen === 'young' && !seen.has(id)) { seen.add(id); queue.push(id); }
    };
    for (const r of this.roots) enqueue(r);
    for (const oldId of this.remembered)
      for (const ref of this.allObjects.get(oldId).refs) enqueue(ref);

    // Cheney scan: trace reachable young objects.
    while (queue.length) {
      const id = queue.shift();
      const o = this.young.get(id);
      o.age++;
      if (o.age >= TENURE_AGE) {           // promote
        o.gen = 'old';
        this.old.set(id, o);
      } else {
        survivors.set(id, o);
      }
      for (const ref of o.refs) enqueue(ref);
    }

    const reclaimed = this.young.size - seen.size;
    // Anything not reached is dead — drop it in one stroke.
    for (const [id] of this.young)
      if (!seen.has(id)) this.allObjects.delete(id);
    this.young = survivors;
    // Promoted objects no longer dangle from the remembered set.
    this.remembered.clear();
    return { copied: survivors.size, reclaimed };
  }
}

Two details worth flagging. First, the dead objects are never enqueued — the loop only ever touches reachable nodes, which is what makes the cost proportional to survivors. Second, the remembered set is consulted as a root source; without it, an old object's reference to a young object would be invisible and that young object would be wrongly collected.

Python implementation

The same algorithm in Python. CPython itself is reference-counted with a generational cyclic collector bolted on (three generations, thresholds default (700, 10, 10)) — but here we model the pure tracing-generational scheme for clarity.

TENURE_AGE = 3

class Obj:
    __slots__ = ('id', 'refs', 'age', 'gen')
    def __init__(self, oid, refs):
        self.id, self.refs, self.age, self.gen = oid, list(refs), 0, 'young'

class GenGC:
    def __init__(self):
        self.young, self.old = {}, {}
        self.roots = set()
        self.remembered = set()      # old ids holding young pointers
        self.universe = {}
        self._next = 1

    def alloc(self, refs=()):
        oid = self._next; self._next += 1
        o = Obj(oid, refs)
        self.young[oid] = o
        self.universe[oid] = o
        return oid

    def write_ref(self, src_id, dst_id):     # the write barrier
        src = self.universe[src_id]
        src.refs.append(dst_id)
        if src.gen == 'old' and self.universe[dst_id].gen == 'young':
            self.remembered.add(src_id)

    def minor_gc(self):
        seen, queue, survivors = set(), [], {}

        def enqueue(oid):
            o = self.universe.get(oid)
            if o and o.gen == 'young' and oid not in seen:
                seen.add(oid); queue.append(oid)

        for r in self.roots: enqueue(r)
        for old_id in self.remembered:                 # extra roots
            for ref in self.universe[old_id].refs: enqueue(ref)

        while queue:                                   # Cheney-style scan
            o = self.young[queue.pop(0)]
            o.age += 1
            if o.age >= TENURE_AGE:                     # promote / tenure
                o.gen = 'old'; self.old[o.id] = o
            else:
                survivors[o.id] = o
            for ref in o.refs: enqueue(ref)

        reclaimed = len(self.young) - len(seen)
        for oid in list(self.young):                   # drop the dead
            if oid not in seen: del self.universe[oid]
        self.young = survivors
        self.remembered.clear()
        return survivors, reclaimed

Note the structural symmetry with the JavaScript version: the only "magic" is that enqueue ignores anything not in the young generation, so old objects are never traced during a minor GC. The remembered set is what reconnects the two worlds without scanning the old generation.

Variants worth knowing

Number of generations. Two is the most common, but .NET uses three (gen0, gen1, gen2) and HotSpot historically used the metaspace/permgen as a quasi-generation for class metadata. CPython's cyclic collector also uses three. More generations let you tier promotion, but each boundary needs its own remembered set and barrier handling.

Eden + survivor spaces vs flat nursery. The HotSpot Eden/S0/S1 design ages objects through copying inside the young generation so that only genuine survivors promote. A simpler design promotes every minor-GC survivor immediately, which over-promotes transient-but-not-instant garbage.

Concurrent and region-based collectors. G1 (the JVM default since Java 9) abandons fixed Eden/old boundaries for a grid of fixed-size regions, dynamically labeling some as young; it still collects young regions every pause but does old-region work concurrently and incrementally. ZGC and Shenandoah go further with concurrent compaction and load/store barriers, keeping pauses under ~1 ms even on multi-terabyte heaps — and both gained a generational mode (ZGC's became default in JDK 23) because the hypothesis still pays off.

Reference counting + generational tracing. CPython and Swift use reference counting as the primary scheme and add a tracing pass only to break cycles, which pure refcounting can't reclaim. CPython's cycle detector is itself generational.

Train algorithm / mature object space. An incremental old-generation collector (Hudson & Moss) that partitions tenured space into "cars" and "trains" to bound pause time and eventually collect old-old cycles. Influential in the literature, rarely shipped verbatim.

Common bugs and edge cases

• Forgetting the write barrier. The single most catastrophic bug: drop the barrier on one store path and an old-to-young pointer goes unrecorded, so a minor GC frees a live object and you get heap corruption that surfaces far from the cause.
• Premature promotion (nepotism). A dead old object that still references a young object keeps that young object alive through the remembered set until the next full GC. Tune the young generation large enough that genuine garbage dies before promotion.
• Survivor space too small. If survivors overflow S0/S1, they spill straight to the old generation regardless of age, defeating the aging mechanism and accelerating full GCs. Watch TargetSurvivorRatio.
• Allocation rate vs nursery size. A nursery too small fires minor GCs constantly (high overhead); too large and each minor GC has more survivors to copy and the rare full GC stalls longer. It's a throughput-vs-latency dial.
• Humongous / large objects. Objects bigger than the nursery (or a G1 region) bypass it entirely and allocate in the old generation, escaping the cheap path — a surprise source of old-gen pressure.
• Assuming generational fixes all pauses. It only makes the common pause cheap. A full GC of a large old generation still stops the world in non-concurrent collectors; reach for G1/ZGC/Shenandoah if old-gen pauses hurt.