Incremental and concurrent garbage collection

Deep dive

How it works

Parts:

• Colours — white: unreached; grey: reached, children pending; black: scanned. Mark bits plus a work list.
• Marker — takes grey objects from the work list, shades their white children, then turns them black.
• Write barrier — code on every pointer store that preserves a tri-colour invariant.
• Pacer — decides how much marking each step or each allocation must pay for.
• Load barrier — only in collectors that move objects concurrently.

Invariants. The strong invariant: no black object points to a white one. The weak invariant: every white object pointed to by a black one is also reachable from a grey one through white objects. Either lets marking end with the work list empty and all remaining white objects truly dead.

1. Pause briefly, shade the roots grey, turn the barrier on, resume.
2. The marker repeatedly pops k grey objects, shades their white children and blackens them. The mutator runs between steps (incremental) or at the same time (concurrent).
3. Every pointer store src.f = val runs the barrier. Dijkstra insertion: shade val. Yuasa deletion: shade the old src.f.
4. Objects allocated during marking are born black, so they are never swept in this cycle.
5. Pacing: start early enough, and make a fast-allocating thread do some marking itself (an assist).
6. Mark termination: a short pause confirms no grey objects remain (Dijkstra designs rescan roots here), then the barrier goes off.
7. Sweep the white objects, concurrently or lazily, and reset colours.

 white ──shade──▶ grey ──scan children──▶ black
   ▲                                        │
   └──── forbidden: black ──▶ white ◀───────┘   (strong invariant)
 mutator: a.f = b  ──barrier──▶ shade(b) (Dijkstra) or shade(old a.f) (Yuasa)

Go hybrid barrier. Dijkstra's barrier needs the stacks rescanned at the end, since stack stores carry no barrier; that was a large pause in Go. Go combines both barriers: shade the overwritten value, and if the current goroutine's stack is still grey, also shade the new value. Stacks then never need rescanning (Go proposal 17503).

Concurrent compaction. After relocation every reference to the old copy must be fixed before the program uses it. A load barrier on reference reads checks whether the target moved and fixes the pointer on the spot. ZGC keeps its state in coloured pointer bits and uses load barriers, so relocation runs while threads continue (JEP 333). Shenandoah gives every object an indirection pointer so GC threads compact the heap concurrently, with pauses independent of heap size (JEP 189). C4 (Azul) is a concurrent compacting collector (Tene et al. 2011).

Code

An arena heap marked in steps of k objects. The scenario hides a white object behind a black one while a grey object still holds it. Both barriers keep it alive; with no barrier it is freed.

#[derive(Clone, Copy, PartialEq)]
enum Color { White, Grey, Black }
#[derive(Clone, Copy, PartialEq)]
enum Barrier { None, Dijkstra, Yuasa }

struct Obj { kids: Vec<usize>, color: Color, free: bool }
struct Heap { objs: Vec<Obj>, roots: Vec<usize>, grey: Vec<usize>, marking: bool, barrier: Barrier }

impl Heap {
    fn alloc(&mut self, kids: Vec<usize>) -> usize {
        // born black while marking, so a new object is never swept this cycle
        let color = if self.marking { Color::Black } else { Color::White };
        self.objs.push(Obj { kids, color, free: false });
        self.objs.len() - 1
    }
    fn shade(&mut self, i: usize) {
        if self.objs[i].color == Color::White {
            self.objs[i].color = Color::Grey;
            self.grey.push(i);
        }
    }
    fn start(&mut self) {
        self.marking = true;
        for r in self.roots.clone() { self.shade(r); }
    }
    /// Mark at most k objects; true when no grey object is left.
    fn step(&mut self, k: usize) -> bool {
        for _ in 0..k {
            let Some(i) = self.grey.pop() else { return true };
            for c in self.objs[i].kids.clone() { self.shade(c); }
            self.objs[i].color = Color::Black;
        }
        self.grey.is_empty()
    }
    /// Pointer store `src.kids[k] = val`, with the write barrier.
    fn write(&mut self, src: usize, k: usize, val: usize) {
        if self.marking {
            match self.barrier {
                Barrier::Dijkstra => self.shade(val),                 // new target
                Barrier::Yuasa => { let old = self.objs[src].kids[k]; self.shade(old) } // overwritten
                Barrier::None => {}
            }
        }
        self.objs[src].kids[k] = val;
    }
    /// Termination: drain the grey set, then free every white object.
    fn finish(&mut self) {
        while !self.step(usize::MAX) {}
        for o in self.objs.iter_mut() {
            if o.color == Color::White { o.free = true; } else { o.color = Color::White; }
        }
        self.marking = false;
    }
    fn reachable(&self) -> Vec<usize> {
        let (mut seen, mut st) = (vec![false; self.objs.len()], self.roots.clone());
        while let Some(i) = st.pop() {
            if !seen[i] { seen[i] = true; st.extend(&self.objs[i].kids); }
        }
        (0..seen.len()).filter(|&i| seen[i]).collect()
    }
}

fn run(barrier: Barrier) -> Heap {
    let mut h = Heap { objs: vec![], roots: vec![], grey: vec![], marking: false, barrier };
    let d = h.alloc(vec![]);
    let b = h.alloc(vec![]);
    let c = h.alloc(vec![b]);
    let a = h.alloc(vec![d]);
    let root = h.alloc(vec![c, a]);
    h.roots.push(root);
    h.start();
    h.step(2);             // root and a black; c grey; b white
    h.write(a, 0, b);      // black a now points at white b
    h.write(c, 0, d);      // the only grey path to b is cut
    h.finish();
    h
}

fn main() {
    for barrier in [Barrier::Dijkstra, Barrier::Yuasa] {
        let h = run(barrier);
        for i in h.reachable() { assert!(!h.objs[i].free, "live object freed"); }
    }
    let h = run(Barrier::None);
    let lost: Vec<_> = h.reachable().into_iter().filter(|&i| h.objs[i].free).collect();
    assert_eq!(lost, vec![1]);   // b freed while reachable: the missing barrier
    println!("ok");
}

Complexity and constants

• Marking is O(live objects + pointers) in total; each step is O(k), so a pause is bounded by k, not by the heap.
• Barrier: O(1) per pointer store; outside a cycle it is one flag test.
• Cost drivers: barrier executions, work-list pushes, cache misses while chasing pointers, floating garbage (objects shaded and then dead stay until the next cycle).
• Termination pause: proportional to roots, not heap.

Efficiency

• Cost: a mark step is memory-bound, about one cache miss per object. The barrier is a per-store tax while a cycle runs: throughput is traded for pause time.
• Levers:
  • Worker-thread marking — V8 measured 60%-70% less main-thread marking time (V8 blog) — when cores are spare.
  • Idle-time slices — Chrome's scheduler runs small marking steps in idle gaps (V8 blog) — when the UI has idle time.
  • Pace by allocation — assists scale with the allocation rate (Go GC guide) — when allocation rate varies.
  • Filter barriers — test the flag and colour first, push only white targets (V8 barrier code) — always.
  • Hybrid barrier — removes the stack rescan pause (Go proposal 17503) — when stacks are many and large.
• Naive → standard → state of the art:
  • Stop-the-world mark · pause grows with the live heap.
  • Incremental mark, Dijkstra or Yuasa barrier · pause bounded by k and root scanning.
  • Concurrent mark and compaction, load barriers, concurrent stack scanning (JEP 376) · pauses decoupled from heap size.

Implementation notes

• Use per-thread segmented work lists with a shared pool, so threads mark without locks until they run dry.
• Concurrent marking needs atomic field reads and an atomic white-to-grey transition, or two threads push the same object.
• Weak references and finalizers need their own round after strong marking drains.

Pitfalls

• One missing barrier path frees a live object, rarely and under load. Keep a debug mode that re-verifies the heap after each cycle.
• Floating garbage: Yuasa keeps everything alive at cycle start even if it dies at once.
• If allocation outruns marking, assists spike and the program slows, or a stop-the-world fallback runs.
• Dijkstra without stack barriers needs the root rescan; skipping it loses objects held only by a stack slot.

Variants and alternatives

In production

• Go runtime (services) — concurrent tri-colour mark with a hybrid barrier and assists; mark phase reserves 25% of CPU (Go GC guide, Go proposal 17503).
• V8 (browsers, Node.js) — incremental marking with a Dijkstra-style barrier since 2011, concurrent marking in Chrome 64 and Node.js 10 (V8 blog).
• OpenJDK ZGC (JVM services, databases) — load barriers and coloured pointers; concurrent relocation (JEP 333) and concurrent stack processing (JEP 376).
• OpenJDK Shenandoah — concurrent evacuation with pauses independent of heap size (JEP 189).
• Azul C4 (JVM, trading) — continuously concurrent compacting collector (Tene et al. 2011).

Implementations

Sources

• Dijkstra, Lamport, Martin, Scholten, Steffens, On-the-Fly Garbage Collection: An Exercise in Cooperation, CACM 21(11), 1978. paper
• Yuasa, Real-Time Garbage Collection on General-Purpose Machines, Journal of Systems and Software 11(3), 1990. paper
• Tene, Iyengar, Wolf, C4: The Continuously Concurrent Compacting Collector, ISMM 2011. paper
• Go proposal 17503: Eliminate STW stack re-scanning
• A Guide to the Go Garbage Collector
• V8: Concurrent marking
• JEP 333: ZGC · JEP 376: ZGC concurrent thread-stack processing · JEP 189: Shenandoah