Generational garbage collection

Deep dive

How it works

Parts:

• Nursery — young region with a bump pointer; from-space plus to-space, or eden plus survivor spaces.
• Old generation — promotion target, collected by mark-sweep (often compacting).
• Age — header bits, or position in a survivor space: minor GCs survived.
• Write barrier — on src.f = v: if src is old and v is young, record it.
• Remembered set — recorded old-to-young edges as a card table (one dirty flag per fixed chunk of the old generation), a slot list, or both.

1. Allocate by bumping the pointer; at the limit, run a minor GC.
2. Evacuate what the roots reference: copy each young object once, leave a forwarding pointer, return the new address on later visits.
3. Treat each dirty card as roots: scan its objects and evacuate their young targets.
4. Scan copied objects in a Cheney loop. An object whose age reaches the threshold goes to the old generation, not to-space.
5. Swap spaces, reset the bump pointer. Everything left behind was garbage and cost nothing.
6. Rebuild cards: a card stays dirty only while it still points into the young generation; cards that received promoted objects are rescanned.
7. When the old generation passes its occupancy limit, run a major GC over the whole heap (see concurrent GC).

 roots ──▶ nursery [from-space ■■□■□□ → bump][to-space]
              ▲                │ survivors, age < N: stay young
  dirty card ─┘                ▼ age ≥ N: promote
  old generation [card0][card1][card2] …   old.f = young ⇒ barrier dirties card

Ungar (1984) and Lieberman and Hewitt (1983) built on the skewed lifetimes; a tenuring threshold above 1 lets mid-lived objects die in the nursery.

Code

Arena heap: a nursery with a to-space, an old generation, a card table and a minor GC that promotes after two survivals. It asserts that an object reachable only through an old-to-young edge survives and that unreachable ones die.

#[derive(Clone, Copy, PartialEq, Debug)]
enum R { Young(usize), Old(usize) }

#[derive(Default)]
struct Obj { children: Vec<R>, age: u8, fwd: Option<R> }

const CARD: usize = 4;   // old-generation slots per card
const TENURE: u8 = 2;    // survivals before promotion

struct Heap {
    young: Vec<Obj>, to: Vec<Obj>, old: Vec<Obj>,
    cap: usize,          // nursery size in objects
    cards: Vec<bool>,    // dirty = may hold an old->young pointer
    work: Vec<R>,        // Cheney-style scan list
}

impl Heap {
    fn new(cap: usize) -> Self {
        Heap { young: vec![], to: vec![], old: vec![], cap, cards: vec![], work: vec![] }
    }
    fn full(&self) -> bool { self.young.len() >= self.cap }
    fn alloc(&mut self, children: Vec<R>) -> R {          // bump allocation
        assert!(!self.full(), "run minor() first");
        self.young.push(Obj { children, ..Default::default() });
        R::Young(self.young.len() - 1)
    }
    fn alloc_old(&mut self, children: Vec<R>) -> R {
        let i = self.old.len();
        if self.cards.len() <= i / CARD { self.cards.resize(i / CARD + 1, false); }
        if children.iter().any(|c| matches!(c, R::Young(_))) { self.cards[i / CARD] = true; }
        self.old.push(Obj { children, ..Default::default() });
        R::Old(i)
    }
    /// Write barrier: every pointer store goes through here.
    fn write(&mut self, src: R, k: usize, val: R) {
        match src {
            R::Old(i) => {
                if matches!(val, R::Young(_)) { self.cards[i / CARD] = true; }
                self.old[i].children[k] = val;
            }
            R::Young(i) => self.young[i].children[k] = val,
        }
    }
    fn evac(&mut self, r: R) -> R {
        let i = match r { R::Old(_) => return r, R::Young(i) => i };
        if let Some(f) = self.young[i].fwd { return f; }  // already copied
        let mut o = std::mem::take(&mut self.young[i]);
        o.age += 1;
        let new = if o.age >= TENURE {
            self.old.push(o);
            R::Old(self.old.len() - 1)
        } else {
            self.to.push(o);
            R::Young(self.to.len() - 1)
        };
        self.young[i].fwd = Some(new);
        self.work.push(new);
        new
    }
    fn obj(&mut self, r: R) -> &mut Obj {
        match r { R::Young(i) => &mut self.to[i], R::Old(i) => &mut self.old[i] }
    }
    /// Minor GC: roots + dirty cards are the only entry points into the nursery.
    fn minor(&mut self, roots: &mut [R]) {
        let old_len = self.old.len();
        self.cards.resize(old_len.div_ceil(CARD) + 1, false);
        for r in roots.iter_mut() { *r = self.evac(*r); }
        let dirty: Vec<usize> = (0..self.cards.len()).filter(|&c| self.cards[c]).collect();
        for &c in &dirty {
            for s in c * CARD..((c + 1) * CARD).min(old_len) {
                for k in 0..self.old[s].children.len() {
                    let ch = self.old[s].children[k];
                    self.old[s].children[k] = self.evac(ch);
                }
            }
        }
        while let Some(r) = self.work.pop() {
            for k in 0..self.obj(r).children.len() {
                let ch = self.obj(r).children[k];
                let n = self.evac(ch);
                self.obj(r).children[k] = n;
            }
        }
        std::mem::swap(&mut self.young, &mut self.to);
        self.to.clear();
        // re-derive dirtiness for cards we touched or that received promoted objects
        self.cards.resize(self.old.len().div_ceil(CARD) + 1, false);
        let mut touched = dirty;
        touched.extend(old_len / CARD..self.old.len().div_ceil(CARD));
        for c in touched {
            let hi = ((c + 1) * CARD).min(self.old.len());
            self.cards[c] = (c * CARD..hi)
                .any(|s| self.old[s].children.iter().any(|x| matches!(x, R::Young(_))));
        }
    }
}

fn main() {
    let mut h = Heap::new(8);
    let o = h.alloc_old(vec![R::Old(0)]);        // old, not a root: minors never free old
    let y = h.alloc(vec![]);
    let y2 = h.alloc(vec![y]);                   // reachable only via o -> y2 -> y
    let _dead = h.alloc(vec![]);                 // unreachable
    let live = h.alloc(vec![]);                  // rooted
    h.write(o, 0, y2);                           // barrier dirties o's card
    assert!(h.cards[0]);
    let mut roots = [live];
    h.minor(&mut roots);
    assert_eq!(h.young.len(), 3);                // y2, y, live survive; _dead died
    let R::Young(i) = h.old[0].children[0] else { panic!() };
    let R::Young(j) = h.young[i].children[0] else { panic!() };
    assert!(h.young[j].children.is_empty());
    assert!(h.cards[0]);                         // still points young: stays dirty
    h.minor(&mut roots);                         // age 2 >= TENURE: promoted
    assert_eq!(h.young.len(), 0);
    assert_eq!(h.old.len(), 4);
    assert!(matches!(roots[0], R::Old(_)));
    assert!(!h.cards[0] && !h.cards.iter().any(|&c| c)); // old->old only: clean
    println!("ok");
}

Complexity and constants

• Allocation: O(1), a pointer bump and limit check, no free-list search.
• Minor GC: O(live young + objects in dirty cards); independent of old-generation size and of dead young objects.
• Barrier: O(1) per pointer store, a filter plus a one-byte card write when it fires.

Efficiency

• Cost: a minor GC touches survivors and dirty cards only; it is bound by memory bandwidth and cache misses on the survivors. Measure your own with GC logs.
• Levers:
  • Nursery larger than the allocation burst between GCs — fewer GCs, lower survivor fraction (design reason) — when RAM allows.
  • Parallel scavenging — V8 cut main-thread young GC time by about 20%-50% depending on workload (V8 blog "Trash talk") — when cores are idle.
  • Tenuring threshold above 1 — mid-lived objects die in survivor space, not old (design reason) — when mid-lived objects are common.
  • Big objects straight into old — .NET large object heap, G1 humongous objects (Microsoft docs, Oracle G1 guide) — avoids copying them.
  • Pretenuring by allocation site — sites whose objects always survive allocate in old (Blackburn et al. 2001) — when profiling shows it.
• Naive → standard → state of the art:
  • Full-heap trace every cycle · cost of the whole live heap each time.
  • Two generations, semispace nursery, card-marking barrier, stop-the-world minor GC · pause proportional to survivors.
  • Parallel and concurrent young collection, regions, adaptive sizing, store barriers (Generational ZGC, JEP 439) · ZGC pauses measured in microseconds (JEP 439).

Implementation notes

• One byte per card makes the barrier a plain store; filter first (skip if the value is not young or the source is young).
• Cost drivers: bytes copied, cards scanned, barrier executions, promoted bytes.
• Cover every pointer-writing path: array stores, bulk copies, native code.

Pitfalls

• A missed barrier frees a live young object: the worst bug here.
• Premature promotion: a too-small nursery lets short-lived objects survive by chance and rot in old until the next major GC.
• Nepotism: a dead old object keeps its young children alive through its card.
• Workloads that break the hypothesis (caches, session stores, build-then-drop batches, medium-lived queues): survivors are copied, then die in old; minors cost more and majors run often.

Variants and alternatives

In production

• V8 (browsers, Node.js) — nursery and intermediate sub-generations plus old; parallel semi-space Scavenger; promotion on a second survival; write barriers keep the old-to-new list (V8 blog).
• HotSpot G1 (JVM servers) — region-based: eden and survivor regions are young, the rest old (Oracle G1 guide). Generational ZGC arrived in JDK 21 with store barriers (JEP 439) and became the default ZGC mode (JEP 474).
• .NET (services) — generations 0, 1, 2; survivors promoted a generation; large objects in the LOH (Microsoft docs).
• Android ART (mobile) — concurrent copying collector, generational on Android 10+; picks young or full GC by measured throughput (Android docs).
• CPython (scripting) — refcounting plus a generational cycle collector with three generations (gc docs). 3.14.0-3.14.4 shipped an incremental collector, reverted to the generational one from 3.14.5 (3.14 what's new).

Implementations

Sources

• Ungar, Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm, SDE 1, 1984. paper
• Lieberman, Hewitt, A Real-Time Garbage Collector Based on the Lifetimes of Objects, CACM 26(6), 1983. paper
• Blackburn, Singhai, Hertz, McKinley, Moss, Pretenuring for Java, OOPSLA 2001. paper
• V8: Trash talk, the Orinoco garbage collector
• JEP 439: Generational ZGC
• Oracle: G1 collector, JDK 21 GC tuning guide
• Microsoft: Fundamentals of garbage collection
• Android: Debug ART garbage collection
• Python gc module · What's new in Python 3.14