Generational GC

The generational hypothesis is the most important empirical observation in garbage collection: most objects die young. A string created as a temporary in an expression is typically garbage by the next statement. Generational GC exploits this by focusing collection effort on young objects.

Two Generations

We split the heap into two regions:

• Young generation (nursery): newly allocated objects go here. Small, collected frequently.
• Old generation (tenured): objects that survive multiple young collections are promoted here. Large, collected rarely.

Minor Collection (Young Gen Only)

A minor collection only scans the young generation:

1. Mark roots
2. Trace references — but ONLY follow references within the young generation
3. Sweep unmarked young objects
4. Promote surviving objects to the old generation

Since the young generation is small, minor collections are fast — typically sub-millisecond.

Major Collection (Full)

Occasionally, we do a full collection (both generations):

1. Mark roots
2. Trace all references in both generations
3. Sweep unmarked objects from both generations

Major collections are slower but happen much less frequently.

The Remembered Set Problem

When an old object references a young object, the minor collector must know about it — otherwise it might free the young object. The remembered set tracks these cross-generational references:

writeBarrier(oldObj, newRef):
    if isOld(oldObj) and isYoung(newRef):
        rememberedSet.add(oldObj)

During minor collection, the remembered set acts as additional roots.

Promotion Policy

Objects are promoted after surviving N minor collections (the tenuring threshold). Common values:

• V8: promoted after surviving 2 minor collections
• JVM (G1): configurable, default varies by implementation
• Our implementation: promote after surviving 1 collection (simplest)

How V8 Does It

V8's garbage collector (Orinoco) uses a generational approach with:

• Scavenger: copies surviving young objects (semi-space copying collector for the young generation)
• Mark-Compact: for the old generation (mark-sweep plus compaction to reduce fragmentation)
• Concurrent marking: marking runs on a separate thread alongside JavaScript
• Incremental marking: marking is split into small chunks interleaved with execution

Trade-offs

Generational GC is faster in the common case (short-lived objects) but adds complexity:

• Write barriers on every pointer store
• Remembered set maintenance
• Promotion decisions
• More complex sweeping logic

Your Task

Implement a two-generation GC with minor/major collections, a remembered set for tracking cross-generational references, and object promotion.