Implement Generational Garbage Collection

Topic Overview

Generational Hypothesis

Most objects die young. Split heap into young (nursery) and old generations. Minor collections copy survivors with copying GC; promote long-lived objects to old gen. Major collections run rarely. HotSpot's G1 and .NET GC extend this model.

Minor vs Major

Allocate in nursery until full. Minor GC copies survivors to survivor space or promotes. Old gen collected less often with mark-sweep or mark-compact.

cCopy
Loading…

• Write barriers record old->young pointers
• Promotion threshold: survive N minor collections
• Card tables summarize dirty old-gen cards
• Tuning nursery size trades frequency vs pause

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement generational garbage collection with nursery and old generation. This exercise requires a fast minor collection, promotion policy, and write barriers for cross-generation pointers.

Your Task

Implement a generational collector: new objects live in a small nursery that is collected often and cheaply (minor GCs); objects that survive long enough are promoted to the old generation, which is collected rarely (major GCs). A remembered set of old→young pointers lets a minor GC skip scanning the old generation entirely.

Input

Rules

• Write barrier: link A B with A old and B young adds A to the remembered set.
• Minor GC: mark young objects reachable from (a) the roots and (b) the objects in the remembered set, following pointers only through young objects (old objects are never scanned: except remembered ones, whose pointers are followed). Unmarked young objects are freed. Each survivor's age increases by 1; a survivor whose age reaches AGE is promoted to old. Then rebuild the remembered set: every old object (in allocation order) that still points to a young object.
• Major GC: ordinary mark-and-sweep over both generations from the roots; nothing is promoted; the remembered set is rebuilt as above.
• After a minor GC, if the old generation holds more than oldlimit bytes, a major GC runs automatically.

Output

cCopy
Loading…

Minor and major GCs are numbered separately. Lists are in allocation order and print none when empty. At the end: young: NAME(age) ... and old: NAME ... (or none).

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Per object: generation, age, size, pointers; a remembered set of old objects.
2. The minor GC must never traverse an old object that isn't in the remembered set.

Hidden tests cover floating garbage (a dead old object keeping a young one alive until a major GC), an allocation that triggers a minor GC, the old-generation limit triggering a major GC, and unrooted young objects freed by a minor GC.