Mark-sweep garbage collection

Deep dive

How it works

In: root set + heap of objects with pointer fields · Out: every unreachable object returned to the free list · State: a mark bit per object (or bitmap), a mark stack, a free list · Cost: mark O(live + edges), sweep O(heap)

1. Colour all objects white (mark bits clear). A cycle starts from this state.
2. Shade each root gray: set its mark bit and push it on the explicit mark stack.
3. Pop a gray object, shade each unmarked child gray, and the popped object is black. No recursion, so a 100,000-long list needs only stack memory on the heap, not the machine stack.
4. When the stack is empty, every reachable object is black and every white object is garbage (the tri-color invariant held throughout).
5. Sweep the heap linearly: a marked object has its bit cleared; an unmarked one is linked into a free list (or its block is released).
6. Allocation pops the free list; when it is empty, collect or grow the heap.

Roots. Precise collectors know which stack slots and registers hold pointers (stack maps, tagged values); a conservative one (Boehm GC) treats any word that looks like a pointer into the heap as one, so it needs no compiler support but may retain garbage and cannot move objects.

Mark bits. In the header the bit costs no extra lookup but writing it dirties the object's cache line, which hurts copy-on-write sharing after fork. A side bitmap (1 bit per granule, e.g. per 8 or 16 bytes) packs 64 objects per word, makes sweeping a bitmap scan, and keeps heap pages clean.

Lazy sweeping. Sweep one block when the allocator needs memory, not the whole heap after mark: the pause shrinks to the mark phase.

Incremental and concurrent marking. Slicing step 3 lets the mutator run between slices, so it can store a white pointer into a black object and hide a live object. Two barrier families keep the invariant:

• Dijkstra insertion barrier: on black.f = white, shade the new target gray. Preserves "no black to white"; stacks need a final rescan because they are not barriered.
• Yuasa snapshot-at-the-beginning (deletion) barrier: on overwrite, shade the old value. Everything reachable at the start of marking survives (floating garbage is retained until the next cycle); no rescan is needed.

New objects are allocated black (or gray) during marking.

Code

Arena heap: objects are slots in a Vec, edges are indices, freed slots are reused through a free list.

#[derive(Clone)]
struct Obj {
    live: bool,        // slot in use (false = on the free list)
    marked: bool,      // mark bit (header bit; swap polarity each cycle in real GCs)
    next_free: usize,  // free-list link, valid when !live
    children: Vec<usize>,
}

const NIL: usize = usize::MAX;

struct Heap {
    objs: Vec<Obj>,
    free_head: usize,
    stack: Vec<usize>, // explicit mark stack = the gray set
}

impl Heap {
    fn new() -> Self {
        Heap { objs: Vec::new(), free_head: NIL, stack: Vec::new() }
    }

    fn alloc(&mut self, children: Vec<usize>) -> usize {
        if self.free_head != NIL {
            let i = self.free_head;
            self.free_head = self.objs[i].next_free;
            self.objs[i] = Obj { live: true, marked: false, next_free: NIL, children };
            i
        } else {
            self.objs.push(Obj { live: true, marked: false, next_free: NIL, children });
            self.objs.len() - 1
        }
    }

    fn mark(&mut self, roots: &[usize]) {
        for &r in roots {
            self.shade(r);
        }
        while let Some(i) = self.stack.pop() {
            for k in 0..self.objs[i].children.len() {
                let c = self.objs[i].children[k];
                self.shade(c);
            }
        }
    }

    fn shade(&mut self, i: usize) {
        let o = &mut self.objs[i];
        if o.live && !o.marked {
            o.marked = true; // white -> gray
            self.stack.push(i);
        }
    }

    fn sweep(&mut self) -> usize {
        let mut freed = 0;
        for i in 0..self.objs.len() {
            let o = &mut self.objs[i];
            if !o.live {
                continue;
            }
            if o.marked {
                o.marked = false;
            } else {
                o.live = false;
                o.children = Vec::new();
                o.next_free = self.free_head;
                self.free_head = i;
                freed += 1;
            }
        }
        freed
    }

    fn collect(&mut self, roots: &[usize]) -> usize {
        self.mark(roots);
        self.sweep()
    }
}

fn main() {
    let mut h = Heap::new();
    let a = h.alloc(vec![]);
    let b = h.alloc(vec![a]);
    // unreachable cycle x <-> y
    let x = h.alloc(vec![]);
    let y = h.alloc(vec![x]);
    h.objs[x].children.push(y);
    // 100_000-long chain: a recursive marker would overflow
    let mut head = h.alloc(vec![]);
    for _ in 0..100_000 {
        head = h.alloc(vec![head]);
    }
    let roots = [b, head];
    let freed = h.collect(&roots);
    assert_eq!(freed, 2);
    assert!(h.objs[a].live && h.objs[b].live && !h.objs[x].live && !h.objs[y].live);
    let n = h.objs.len();
    let z = h.alloc(vec![]); // reuses a freed slot
    assert!(z == x || z == y);
    assert_eq!(h.objs.len(), n);
    let freed = h.collect(&[b, z]);
    assert_eq!(freed, 100_001);
    println!("ok");
}

Complexity and constants

• Mark: O(live objects + pointer fields); each object is pushed once because the mark bit is set at push time.
• Sweep: O(slots) regardless of live size; touches every slot header, or every bitmap word with a side bitmap.
• Mark stack: worst case O(live objects) pointers (8 bytes each). Real collectors chunk the stack.
• Cost drivers: cache misses (each popped object is a random access, order of one DRAM miss unless prefetched), bytes swept, pause length; fixes are bitmaps, prefetching, lazy sweep, concurrency.
• Trigger: collect at a multiple of the last live size (Go: target heap = live heap + (live heap + roots) * GOGC/100, default 100, per the Go GC guide); this bounds GC work to about the allocation rate.

Efficiency

• Cost: each live object costs one pointer-chase (cache miss), its mark-bit write and a scan of its pointer fields; each dead object costs a sweep step. Bound: memory latency for mark, memory bandwidth for sweep. Measure on your own heap.
• Levers:
  • Side mark bitmap — 64 objects per word, sweep becomes a word scan, no writes to object pages (design reason) — when objects are small and the heap is big.
  • Prefetch on push — hides the miss on the object popped later; the mark stack gives the lookahead the recursion lacks — when marking is latency-bound (large pointer-rich heaps).
  • Lazy sweep — moves sweep out of the pause and into allocation — when most blocks are mostly free anyway.
  • Concurrent marking on spare cores — V8 reports pauses in heavy WebGL games cut by up to 50% from concurrent marking and sweeping (V8 blog "Trash talk") — when cores are idle and a write barrier is affordable.
  • Pacing the trigger (GOGC) — doubling GOGC doubles heap overhead and cuts GC frequency (Go GC guide) — when RAM is available.
• Naive → standard → state of the art:
  • Recursive mark, header bit, full sweep in one stop-the-world pause · pause proportional to heap, risk of stack overflow.
  • Explicit mark stack, side bitmap, lazy sweep · pause proportional to live data and the roots.
  • Concurrent tri-color mark with hybrid or SATB barrier, parallel helpers, pacing, optional page compaction · pauses of the order of a root rescan; cost shifts to background CPU and barrier overhead.

Implementation notes

• Set the mark bit when pushing, not when popping, or an object reachable from many parents is pushed many times.
• Alternate the meaning of the mark bit each cycle (black = 1, then black = 0) so the sweep need not clear it.
• Size-segregated blocks (see slab allocator) give an object's size without a header.
• A side bitmap needs an address-to-block map: align blocks to a power of two and mask the pointer.

Pitfalls

• Forgetting that new objects during concurrent marking must start black, so the sweep frees them.
• Roots missed: a pointer only in a register, native handle or suspended thread's stack.
• Conservative scanning retains garbage via integers that look like pointers.
• Fragmentation: a free list full of small holes cannot satisfy a big allocation even if total free space is large.

Variants and alternatives

In production

• Go — concurrent, non-moving, non-generational mark-sweep (Go GC guide); tri-color marking with a write barrier and a hybrid Yuasa/Dijkstra barrier since Go 1.8 (both from memory, not re-checked).
• Lua 5.4 — incremental mode and an optional generational mode (Lua manual §2.5); tri-color incremental marking is from memory.
• Ruby (MRI) — mark-and-sweep with an immediate_sweep option (GC module docs); lazy sweeping, incremental marking and generational mode are from memory.
• Boehm-Demers-Weiser GC — conservative collector for C and C++; offers incremental and generational operation (project page).
• V8 old space — mark-sweep-compact: concurrent marking with write barriers, free lists in sweep, compaction of fragmented pages only (V8 blog "Trash talk").
• Content stores — Docker/OCI registries run a mark-and-sweep garbage collection over blobs and manifests (docs); Git removes unreachable objects with git gc and git prune (git-gc); Nix deletes store paths no GC root reaches (manual).

Implementations

Sources

• Jones, Hosking, Moss, The Garbage Collection Handbook, CRC Press, 2nd ed. 2023.
• Dijkstra, Lamport, Martin, Scholten, Steffens, On-the-Fly Garbage Collection: An Exercise in Cooperation, CACM 21(11), 1978 (DOI link returns 403 to bots, citation only).
• Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software 11(3), 1990. paper
• A Guide to the Go Garbage Collector
• Lua 5.4 reference manual, Garbage Collection
• Boehm-Demers-Weiser GC
• V8: Trash talk, the Orinoco garbage collector
• Ruby GC module