Part 8 · 1 chapters · ~8 min

Garbage Collectors

Reachability and roots, reference counting versus tracing, mark-sweep, mark-compact and copying collectors, tri-colour marking, generational collection and write barriers, incremental and concurrent collectors, pause time versus throughput, real collectors (V8 Orinoco, Go, G1 and ZGC), and writing a mark-sweep collector.

A mark-sweep collector in TypeScript

code

type Obj = { marked: boolean; refs: Obj[]; size: number };
class Heap {
  objects: Obj[] = []; roots = new Set<Obj>(); bytes = 0;
  alloc(size: number, refs: Obj[] = []) {
    if (this.bytes + size > 1_000_000) this.collect();
    const o = { marked: false, refs, size }; this.objects.push(o); this.bytes += size; return o;
  }
  collect() {
    const stack = [...this.roots];                            // mark: iterative, no recursion limit
    while (stack.length) { const o = stack.pop()!; if (o.marked) continue; o.marked = true; stack.push(...o.refs); }
    const live = this.objects.filter(o => o.marked);          // sweep
    this.bytes = live.reduce((s, o) => s + o.size, 0);
    for (const o of live) o.marked = false;
    this.objects = live;
  }
}

Write barriers: a generational collector scans only the young space, so it must know about old objects pointing at young ones; every pointer store runs a small barrier that records such references. Concurrent collectors (Go, ZGC) use barriers so marking can run while the program mutates the heap, keeping pauses well under a millisecond.

MARK-SWEEP AND GENERATIONS

find what is reachable, free the rest

swipe the figure sideways, or tap expand for full screen

1/4

roots

Everything the program can still reach starts from roots: local variables on the stack, globals and registers.

start from rootsstack, globals