Generational Garbage Collection

The Generational Hypothesis

Empirically, across almost every language runtime ever measured, most objects die young. A temporary string built for concatenation, a loop-local record, an intermediate list comprehension result — these are allocated and become garbage within microseconds. A much smaller set of objects (the global environment, long-lived data structures) survive for the whole program. A full mark-and-sweep pass, even the incremental tri-color version, still has to walk every long-lived object on every collection just to re-confirm what was already known: that it's still alive. Generational GC exploits this skew directly.

Splitting the Heap

The heap is divided into two (or more) generations:

• Young generation ("nursery") — where every new object is allocated. Collected frequently; since most young objects are already garbage by the time collection runs, minor collections are fast and reclaim a lot.
• Old generation — objects that have proven they're long-lived get promoted here after surviving a threshold number of minor collections. Collected rarely, because scanning it is expensive relative to how much garbage it typically contains.

Minor Collection: Scan Only the Nursery

A minor collection marks and sweeps only the young generation. That's the entire performance win — if young objects vastly outnumber old ones and die quickly, you get most of your reclaimed memory back for a fraction of the cost of a full heap scan.

The Missing Piece: Old-to-Young References

Here's the subtlety that makes generational GC more than "just GC a smaller heap": if an old object holds a reference to a young object (e.g., a long-lived global list that just had a fresh element appended), that old object is a root for the young generation's reachability — but minor collection, by design, doesn't scan the old generation to discover that. If you ignore this, the young object looks unreachable and gets collected even though the old object still points to it: a use-after-free.

The fix is a remembered set, populated by a write barrier exactly like the one from tri-color marking:

Every time the mutator stores a young reference into an old object, the barrier records that old object in the remembered set. Minor collection then treats the (small) remembered set as additional roots, so it never has to scan the entire old generation — just the old objects that have actually been observed pointing at young ones.

Major Collection

A major collection scans the whole heap — both generations — exactly like the plain mark-and-sweep collector from earlier. This runs rarely (e.g., when old-gen memory pressure crosses its own threshold), because it's the only way to reclaim old objects that have genuinely become garbage (which minor collections, by construction, never even look at).

What to build

Implement alloc (young), add_ref with the write barrier populating remembered, minor (scan young + remembered set, sweep, age-and-promote survivors), and major (full scan of young + old). Verify: an object promoted after PROMOTE_AFTER minor collections moves to old; a young object referenced only from an old object survives a minor collection because of the remembered set; removing that reference lets it die on the next minor collection.