Learn Zig Series (#138) - Garbage Collection: Mark and Sweep

scipio(71)

Published in

StemSocial

Words

4490

Reading

20 min

Listen

Play

Learn Zig Series (#138) - Garbage Collection: Mark and Sweep

What will I learn?

What a garbage collector actually is once you strip away the folklore -- a subsystem that answers one question, "which objects can the program still reach?", and frees the rest;
Why mark and sweep is the honest starting point for automatic memory management, and why reference counting -- the obvious alternative -- quietly leaks the moment two objects point at each other;
How to build a working mark-and-sweep collector from scratch in Zig: an intrusive list of every allocation, a mark phase that traces reachability from a set of roots, and a sweep phase that reclaims everything the trace never reached;
How Zig's tagged unions turn "what are this object's children?" into a question the compiler forces you to answer exhaustively, and how error unions keep every allocation visible;
How to test a collector by asserting on what survives and what dies -- and how a second, independent reachability oracle cross-checks the first;
Where the real cost of a stop-the-world collector lives, why recursion is a liability, and how a threshold that grows with the live set keeps GC from dominating your runtime;
How C, Rust and Go each make a completely different bargain with the same problem;
Three exercises that push our collector toward a real language runtime.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
The closures and heap cells from episode 137, and the VM/Chunk machine from episode 136, fresh in mind -- today we clean up after them;
Allocators and the heap from episode 7, pointers from episode 8, and tagged unions from episode 6;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#138) - Garbage Collection: Mark and Sweep

Last episode we gave our little machine closures, and closures allocate. Every Cell we boxed, every environment slice we handed to a closure, every upvalue we closed to the heap -- all of it came out of an allocator, and we dutifully matched each create with a destroy. That worked because we were the ones writing the memory-management code. But think about what a user of our language actually writes: let c = makeCounter();, and then, three functions later, they simply stop using c. They never say "free the counter". They never think about the Cell hiding inside it. So who frees it? Nobody, unless the language itself notices the counter is unreachable and reclaims it. That noticing-and-reclaiming is garbage collection, and today we build the oldest and clearest form of it from scratch.

I want to be honest about the shape of the problem, because it is easy to make GC sound mystical and it is not. A running program has a set of objects it can still get to -- through local variables, through globals, through the operand stack, through the upvalues that closures are holding. Call those the roots. Every object reachable by following pointers from a root is live; the program might still touch it. Everything else is garbage; the program has provably lost all handles to it and can never mention it again. Garbage collection is nothing more than computing that reachable set and freeing the complement. The two classic ways to compute it are reference counting (each object counts its incoming pointers, and dies when the count hits zero) and tracing (start from the roots and walk). We are building the canonical tracing collector: mark and sweep. Here we go!

Solutions to Episode 137 Exercises

Three exercises last time, all pushing our closures toward first-class functions. Full code for each, as always.

Exercise 1 -- A capture-by-value closure. The Cell-based closures all captured by reference, giving the shared-mutable-state behaviour. The task was a Snapshot that captures by value: it copies the integer into its own struct at creation, so later mutations to the original are invisible. No pointer, no heap, no aliasing -- just a copy frozen in time:

const std = @import("std");

const Snapshot = struct {
    captured: i64, // a COPY, taken once at creation time

    fn get(self: Snapshot) i64 {
        return self.captured;
    }
};

fn snapshot(n: i64) Snapshot {
    return .{ .captured = n }; // copy the value in - no reference held
}

test "a by-value capture ignores later mutations to the original" {
    var original: i64 = 10;
    const snap = snapshot(original);

    original = 999; // change the source AFTER capturing
    try std.testing.expectEqual(@as(i64, 10), snap.get()); // snapshot still says 10
}

Which behaviour do you want? A makeAdder(5) wants by-value -- the 5 should never change out from under it. A counter wants by-reference -- the whole point is that the state mutates and persists. Recognising which one a given capture needs is half of understanding closures.

Exercise 2 -- A two-upvalue closure. Extend the general Closure { func, env } model to capture two upvalues: a makeLinear(a, b) returning a closure that computes a * x + b. Both cells go in the env slice, env[0] and env[1], proving the environment-as-a-slice design scales past a single capture:

const std = @import("std");

const Cell = struct { value: i64 };

const Closure = struct {
    func: *const fn (env: []const *Cell, arg: i64) i64,
    env: []const *Cell,

    fn call(self: Closure, arg: i64) i64 {
        return self.func(self.env, arg);
    }
};

fn linear(env: []const *Cell, x: i64) i64 {
    return env[0].value * x + env[1].value; // a*x + b
}

fn makeLinear(alloc: std.mem.Allocator, a: i64, b: i64) !Closure {
    const env = try alloc.alloc(*Cell, 2);
    const ca = try alloc.create(Cell);
    const cb = try alloc.create(Cell);
    ca.* = .{ .value = a };
    cb.* = .{ .value = b };
    env[0] = ca;
    env[1] = cb;
    return .{ .func = linear, .env = env };
}

test "makeLinear(2, 1) applied to 10 gives 21" {
    const alloc = std.testing.allocator;
    const c = try makeLinear(alloc, 2, 1);
    defer {
        alloc.destroy(c.env[0]);
        alloc.destroy(c.env[1]);
        alloc.free(c.env);
    }
    try std.testing.expectEqual(@as(i64, 21), c.call(10)); // 2*10 + 1
}

Nothing about the Closure struct changed -- it already took a slice, and a slice of length two is no harder than a slice of length one. That is the payoff of designing the environment as a slice in the first place, in stead of hard-coding a single captured cell.

Exercise 3 -- A close that closes many. When a function returns, a real VM must close every open upvalue that pointed at that frame's slots, not just one. Model a tiny stack as a [4]Value array and a list of *Upvalues pointing into it, then write a closeAll that closes every upvalue whose slot sits at or above a boundary index:

const std = @import("std");

const Value = union(enum) {
    int: i64,
    float: f64,
    boolean: bool,
};

const Upvalue = struct {
    location: *Value, // points at a live stack slot while OPEN
    closed: Value = undefined,
    is_closed: bool = false,

    fn get(self: *Upvalue) Value {
        return if (self.is_closed) self.closed else self.location.*;
    }

    fn close(self: *Upvalue) void {
        self.closed = self.location.*;
        self.location = &self.closed;
        self.is_closed = true;
    }
};

fn closeAll(upvalues: []*Upvalue, stack: []Value, from_index: usize) void {
    const boundary = @intFromPtr(&stack[from_index]);
    for (upvalues) |up| {
        if (!up.is_closed and @intFromPtr(up.location) >= boundary) up.close();
    }
}

test "closeAll detaches every upvalue at or above the boundary" {
    var stack = [_]Value{
        .{ .int = 10 }, .{ .int = 20 }, .{ .int = 30 }, .{ .int = 40 },
    };

    var up_a = Upvalue{ .location = &stack[1] };
    var up_b = Upvalue{ .location = &stack[3] };
    var ups = [_]*Upvalue{ &up_a, &up_b };

    closeAll(&ups, &stack, 1); // close everything from slot 1 upward

    stack[1] = .{ .int = -1 }; // the frame retires, its slots get reused
    stack[3] = .{ .int = -1 };

    try std.testing.expectEqual(@as(i64, 20), up_a.get().int);
    try std.testing.expectEqual(@as(i64, 40), up_b.get().int);
}

Comparing raw slot addresses with @intFromPtr is exactly how the real VMs decide which upvalues a returning frame owns -- an upvalue belongs to the frame if its location points somewhere inside that frame's slice of the stack. That "close everything from here up" operation is precisely what the ret instruction will trigger once we wire in call frames. Which, funnily enough, brings us straight to today's problem: once objects start outliving the frames that made them, somebody has to decide when to free them.

What a garbage collector actually is

Let me restate the definition and then earn it: a garbage collector reclaims the memory of objects the program can no longer reach. The key word is reach. It is not about whether an object is "still needed" in some human sense -- the machine cannot know your intentions -- it is about whether there exists a chain of pointers, starting from a root, that arrives at the object. If no such chain exists, the program has no way to name the object ever again, so freeing it changes nothing observable. That is the entire correctness argument for garbage collection in one sentence, and it is airtight.

Our objects, for this episode, are deliberately simple: an integer, or a pair holding two other objects (a classic cons cell -- enough to build lists, trees, and, crucially, cycles). Every object begins with the same little GC header: a marked bit the collector will use, and a next pointer that threads it onto an intrusive linked list of every object we have ever allocated. That list is what lets us find the garbage later: to sweep, you have to be able to walk every object, reached or not.

const std = @import("std");

const ObjKind = enum { int, pair };

// Every heap object carries the same GC header: a mark bit, and a `next`
// pointer linking it onto the list of ALL live allocations.
const Obj = struct {
    kind: ObjKind,
    marked: bool = false,
    next: ?*Obj = null,

    value: i64 = 0, // used when kind == .int
    head: ?*Obj = null, // used when kind == .pair
    tail: ?*Obj = null, // used when kind == .pair
};

Notice the shape: a real runtime would use a union or a common base header with type-specific payloads following it (the same trick from the tagged unions in episode 6), but a flat struct with a kind tag keeps the idea in the foreground where I want it. The next field is the humble hero here -- without a way to enumerate every allocation, sweeping is impossible, and reference counting (which never keeps such a list) simply cannot do a full trace. Keeping the list is what buys us the ability to find cycles.

Implementing mark and sweep from scratch

Here is the whole collector. Read it once top to bottom -- it is under a hundred lines and every piece has a job -- and then we will walk the two phases carefully. The GC owns the allocator, the head of the all-objects list, and a list of roots (the objects the outside world still holds). Allocation links each new object onto the list; collect marks from the roots and sweeps the rest.

const std = @import("std");

const ObjKind = enum { int, pair };

const Obj = struct {
    kind: ObjKind,
    marked: bool = false,
    next: ?*Obj = null,
    value: i64 = 0,
    head: ?*Obj = null,
    tail: ?*Obj = null,
};

const GC = struct {
    alloc: std.mem.Allocator,
    objects: ?*Obj = null, // intrusive list of every live object
    roots: std.ArrayList(*Obj), // reachability starting points
    count: usize = 0, // how many objects are alive right now

    fn init(alloc: std.mem.Allocator) GC {
        return .{ .alloc = alloc, .roots = .empty };
    }

    fn deinit(self: *GC) void {
        var it = self.objects;
        while (it) |o| {
            const nxt = o.next;
            self.alloc.destroy(o);
            it = nxt;
        }
        self.roots.deinit(self.alloc);
    }

    fn newObject(self: *GC, kind: ObjKind) !*Obj {
        const obj = try self.alloc.create(Obj);
        obj.* = .{ .kind = kind };
        obj.next = self.objects; // link onto the front of the list
        self.objects = obj;
        self.count += 1;
        return obj;
    }

    fn newInt(self: *GC, v: i64) !*Obj {
        const o = try self.newObject(.int);
        o.value = v;
        return o;
    }

    fn newPair(self: *GC, head: ?*Obj, tail: ?*Obj) !*Obj {
        const o = try self.newObject(.pair);
        o.head = head;
        o.tail = tail;
        return o;
    }

    fn addRoot(self: *GC, obj: *Obj) !void {
        try self.roots.append(self.alloc, obj);
    }

    // MARK: paint every object reachable from a root.
    fn mark(self: *GC, obj: ?*Obj) void {
        const o = obj orelse return;
        if (o.marked) return; // already visited - THIS is what stops cycles
        o.marked = true;
        switch (o.kind) {
            .int => {}, // a leaf: no outgoing pointers
            .pair => {
                self.mark(o.head);
                self.mark(o.tail);
            },
        }
    }

    fn markRoots(self: *GC) void {
        for (self.roots.items) |root| self.mark(root);
    }

    // SWEEP: walk the whole list, free the unmarked, unmark the survivors.
    fn sweep(self: *GC) void {
        var prev: ?*Obj = null;
        var it = self.objects;
        while (it) |o| {
            if (o.marked) {
                o.marked = false; // reset for the next collection
                prev = o;
                it = o.next;
            } else {
                const dead = o;
                it = o.next;
                if (prev) |p| p.next = it else self.objects = it;
                self.alloc.destroy(dead);
                self.count -= 1;
            }
        }
    }

    fn collect(self: *GC) void {
        self.markRoots();
        self.sweep();
    }
};

test "unreachable objects are collected, reachable ones survive" {
    var gc = GC.init(std.testing.allocator);
    defer gc.deinit();

    // A rooted pair (keep) whose head and tail are also live, plus two
    // loose integers nobody points at.
    const keep = try gc.newPair(try gc.newInt(1), try gc.newInt(2));
    _ = try gc.newInt(999); // garbage
    _ = try gc.newInt(888); // garbage

    try gc.addRoot(keep);
    try std.testing.expectEqual(@as(usize, 5), gc.count);

    gc.collect();

    // keep + its two ints survive; the two loose ints are reclaimed.
    try std.testing.expectEqual(@as(usize, 3), gc.count);
    try std.testing.expectEqual(@as(i64, 2), keep.tail.?.value);
}

The mark phase is a graph traversal, no more and no less. Start at each root, set its marked bit, and recurse into its children -- for a pair, that means head and tail; for an int, there are no children so we stop. The single most important line in the whole collector is if (o.marked) return;. That early exit is what makes the trace terminate on cyclic data. Two pairs pointing at each other would loop forever without it; with it, the second visit sees the bit already set and backs out. Cycles, the exact thing that defeats reference counting, are handled here by one boolean check.

The sweep phase is a linked-list filter. Walk every object we ever allocated. If it is marked, it survived: clear the bit (so the next collection starts from a clean slate) and move on. If it is not marked, it is unreachable garbage: unlink it from the list and destroy it. The prev bookkeeping is the standard singly-linked-list removal we first met back in episode 106 -- splice the dead node out by pointing its predecessor at its successor, taking care of the special case where the dead node is the list head. After collect, count reflects only the survivors, and every freed object's memory is genuinely returned to the allocator.

How Zig keeps the tracer honest

The mark phase asks one question of every object: "what are your children?" In C, that question is answered by a switch on an int tag, and the compiler is perfectly happy if you forget a case -- the day you add a new object type, the old switch silently traces nothing for it, and you get a use-after-free that only shows up under memory pressure, which is to say in production and never in your tests. Zig's exhaustive switch on a tagged enum turns that latent bug into a compile error: add a variant, and every switch over the kind stops compiling until you have decided what its children are.

const std = @import("std");

const ObjKind = enum { int, pair, string };

const Obj = struct {
    kind: ObjKind,
    marked: bool = false,
    head: ?*Obj = null,
    tail: ?*Obj = null,
};

// The tag drives the traversal. Because the switch is exhaustive, adding
// `.string` above forces you to state, right here, whether strings have
// children the collector must trace - the compiler will not let you forget.
fn childrenOf(o: *Obj, out: *[2]?*Obj) usize {
    return switch (o.kind) {
        .int, .string => 0, // leaves: no outgoing references
        .pair => {
            out[0] = o.head;
            out[1] = o.tail;
            return 2;
        },
    };
}

test "the object tag exhaustively decides what to trace" {
    var leaf = Obj{ .kind = .int };
    var root = Obj{ .kind = .pair, .head = &leaf, .tail = null };
    var buf: [2]?*Obj = .{ null, null };

    try std.testing.expectEqual(@as(usize, 0), childrenOf(&leaf, &buf));
    try std.testing.expectEqual(@as(usize, 2), childrenOf(&root, &buf));
    try std.testing.expectEqual(&leaf, buf[0].?);
}

The other quiet safeguard is error handling. Every allocation in the collector is a try, so an out-of-memory condition propagates as an ordinary error union (episode 4) rather than a crash or, worse, a silently ignored null. A production collector actually leans on this: the usual policy is "try to allocate, and if it fails, run a collection and try again once" -- which is only expressible cleanly because allocation failure is a value you can catch and respond to, not an exception unwinding through your carefully balanced pointers.

Testing a collector

How do you test something whose job is to make objects disappear? You assert on the two populations: what must survive, and what must die. Our survival test above did exactly that -- rooted one pair, left two integers loose, collected, and checked the count dropped from five to three while the rooted data stayed intact and readable. That "still readable after collection" check matters as much as the count: a collector that frees the right number of objects but corrupts a survivor is still broken.

For extra confidence, I like a second, independent implementation of the same question that the test can cross-check against. Here is a reachability oracle that counts live objects without using the collector's own mark bits -- it uses its own visited-set, so a bug in the real mark cannot hide behind the same bug in the checker:

const std = @import("std");

const Obj = struct {
    marked: bool = false,
    next: ?*Obj = null,
    head: ?*Obj = null,
    tail: ?*Obj = null,
};

// An independent oracle: count reachable objects using its OWN visited-set,
// so it can cross-check the collector rather than trusting the same code.
fn reachable(root: ?*Obj, seen: *std.AutoHashMap(*Obj, void)) !usize {
    const o = root orelse return 0;
    if (seen.contains(o)) return 0; // count each object exactly once
    try seen.put(o, {});
    return 1 + try reachable(o.head, seen) + try reachable(o.tail, seen);
}

test "an independent reachability oracle cross-checks the collector" {
    const a = std.testing.allocator;
    var seen = std.AutoHashMap(*Obj, void).init(a);
    defer seen.deinit();

    var c = Obj{}; // one shared child...
    var left = Obj{ .head = &c };
    var right = Obj{ .head = &c }; // ...reached by two different parents
    var top = Obj{ .head = &left, .tail = &right };

    // top, left, right, c = 4 distinct objects; c is counted once despite
    // being reachable by two paths (a diamond, not a tree).
    try std.testing.expectEqual(@as(usize, 4), try reachable(&top, &seen));
}

The diamond in that test -- two parents sharing one child -- is the case that separates a correct traversal from a naive one. Count c twice and your collector will double-free it the moment both parents die. The visited-set (mirroring the marked bit) is what keeps a shared or cyclic object visited exactly once. Testing the sharing case on purpose is how you avoid shipping a double-free.

Where the cost lives, and how to keep it down

Our collector is stop the world: while it runs, nothing else does, because moving pointers around under a live mutator is a recipe for chaos. So the cost of a collection is proportional to the number of live objects (mark) plus the total number of objects (sweep). That is fine, but there are two traps worth knowing about.

The first trap is recursion. Our mark calls itself for each child, which means a deeply nested structure -- a linked list a million nodes long -- marks in a million nested stack frames, and blows the actual call stack long before it finishes. The fix is to make the traversal's depth live on the heap, where we control it, by using an explicit worklist (a mark stack) in stead of the call stack:

const std = @import("std");

const Obj = struct {
    marked: bool = false,
    head: ?*Obj = null,
    tail: ?*Obj = null,
};

// Recursive marking uses O(depth) real call frames - a long chain can blow
// the stack. An explicit worklist moves that depth onto the heap and turns
// marking into a flat loop that never recurses.
fn markIterative(alloc: std.mem.Allocator, root: *Obj) !void {
    var work: std.ArrayList(*Obj) = .empty;
    defer work.deinit(alloc);

    try work.append(alloc, root);
    while (work.pop()) |o| {
        if (o.marked) continue;
        o.marked = true;
        if (o.head) |h| try work.append(alloc, h);
        if (o.tail) |t| try work.append(alloc, t);
    }
}

test "an explicit worklist marks a deep chain without recursing" {
    const a = std.testing.allocator;

    // A chain 1000 nodes deep - deep enough to make naive recursion nervous.
    var nodes: [1000]Obj = undefined;
    for (&nodes, 0..) |*n, i| {
        n.* = .{ .head = if (i + 1 < nodes.len) &nodes[i + 1] else null };
    }

    try markIterative(a, &nodes[0]);

    try std.testing.expect(nodes[0].marked);
    try std.testing.expect(nodes[999].marked); // the far end got marked too
}

The second trap is running the collector too often. Collecting after every single allocation is correct and pathologically slow. Real runtimes collect only when live memory crosses a threshold, and then set the next threshold as a multiple of what survived -- so a program with a large live set collects rarely, and GC time stays a roughly constant fraction of runtime in stead of growing without bound:

const std = @import("std");

// Real runtimes collect when live bytes cross a threshold, then set the next
// threshold as a MULTIPLE of what survived - so GC frequency scales with the
// program's live set, not with a fixed constant.
const Heap = struct {
    bytes: usize = 0,
    next_gc: usize = 1024,
    grow_factor: usize = 2,

    fn shouldCollect(self: Heap, about_to_alloc: usize) bool {
        return self.bytes + about_to_alloc > self.next_gc;
    }

    fn afterCollect(self: *Heap, live_bytes: usize) void {
        self.bytes = live_bytes;
        self.next_gc = live_bytes * self.grow_factor;
    }
};

test "the GC threshold grows with the surviving live set" {
    var h = Heap{};
    try std.testing.expect(!h.shouldCollect(512)); // under 1024 - no GC yet
    try std.testing.expect(h.shouldCollect(2048)); // over 1024 - collect now

    h.afterCollect(4096); // 4 KB survived this cycle
    try std.testing.expectEqual(@as(usize, 8192), h.next_gc); // next trigger doubles
}

This is the profiling lesson from episode 34 wearing a different hat: do not pay a cost on the common path (a collection per allocation) to solve a problem you only occasionally have (actually running low on memory). Having said that, resist tuning the grow_factor by feel -- pick a starting value, measure your real allocation pattern, and only then adjust. A great many programs are entirely satiesfied by a factor of two.

How C, Rust and Go pay the bill

Every managed language solves reachability somehow, and their bargains are genuinely different.

C does not manage memory at all -- you malloc and you free, and getting it wrong is the source of a large fraction of all security advisories ever filed. When C programs do want automatic collection, they reach for something like the Boehm collector, which is conservative: it does not have our neat kind tags telling it where the pointers are, so it treats every machine word that looks like a pointer as one, and traces from there. It works astonishingly well in practice, but it can be fooled into keeping garbage alive by an integer that happens to hold a pointer-shaped value. Our collector is precise -- the kind tag tells us exactly which fields are pointers -- which is the luxury of controlling the object layout.

Rust takes the most radical position: no garbage collector at all, because ownership and borrowing (episodes to come in spirit, and the whole point of that language) let the compiler insert the free for you at exactly the right spot. When you genuinely need shared ownership, you reach for Rc/Arc -- reference counting -- and you inherit its one flaw, cycles, which Rust makes you break manually with Weak. It is the opposite trade from ours: Rust pays with compile-time strictness to avoid a runtime collector entirely.

Go is closest to what we built, but grown up and concurrent: a tri-color, mostly-concurrent mark-and-sweep collector that runs alongside your program in stead of stopping it dead, using write barriers to stay correct while the mutator keeps mutating. The core is the same mark-then-sweep we just wrote; the engineering is in doing it without a long stop-the-world pause. You now understand the algorithm at Go's heart -- the rest is latency engineering on top of it.

To see why tracing beats reference counting on cycles, here is the failure mode in miniature -- two nodes that keep each other alive forever:

const std = @import("std");

// A stripped-down reference count, to show the failure mode a TRACING
// collector does not have: a cycle whose members keep each other alive.
const RcNode = struct {
    refs: usize = 1,
    other: ?*RcNode = null,

    fn retain(self: *RcNode) void {
        self.refs += 1;
    }
    fn release(self: *RcNode) void {
        self.refs -= 1;
    }
};

test "reference counting leaks a cycle that mark-and-sweep would reclaim" {
    var a = RcNode{};
    var b = RcNode{};

    a.other = &b;
    b.retain(); // a now holds a reference to b
    b.other = &a;
    a.retain(); // b now holds a reference to a

    a.release(); // the outside world drops its handle to a
    b.release(); // and its handle to b

    // Neither count reaches zero - each is kept alive ONLY by the other.
    try std.testing.expectEqual(@as(usize, 1), a.refs);
    try std.testing.expectEqual(@as(usize, 1), b.refs);
    // A tracing collector, starting from an empty root set, frees BOTH.
}

Both counts stay stuck at one, so a reference-counting collector never frees either node -- a textbook leak. Our mark-and-sweep, handed an empty root set, would mark nothing and sweep both away without a second thought. That immunity to cycles is the single biggest reason real language runtimes (Python's cyclic collector, the JVM, Go, the browsers) all use tracing somewhere in the mix.

Real-world use, and where this is heading

Where does a hand-written mark-and-sweep actually earn its keep? In exactly the place we are building toward -- a language runtime. Any interpreter or VM whose users allocate objects freely and never free them (which is to say, every scripting language) needs a collector underneath, and mark-and-sweep is the honest baseline every fancier design is measured against. It is also a fine fit for long-lived tools with graph-shaped state -- editors, build systems, anything with an object model full of cross-references and cycles that reference counting would strangle on.

But there is one glaring inefficiency in what we built, and it points directly at the next improvement. Every collection, we re-mark every live object and re-walk every allocation -- including the objects that have already survived a hundred collections and will clearly survive a hundred more. That is enormous wasted work, and it flies in the face of a well-known empirical fact: most objects die young. The overwhelming majority of allocations become garbage almost immediately (temporaries, intermediate results), while the few that survive their first collection tend to live a very long time. A smarter collector should spend its effort where the garbage actually is -- among the young -- and mostly leave the old survivors alone. We can start preparing for that right now, with one cheap piece of bookkeeping: count how many collections each object has lived through.

const std = @import("std");

// Most objects die young; the few that survive one collection tend to
// survive many. Recording how many collections an object has lived through
// is the cheap bookkeeping a smarter collector uses to stop re-scanning
// veterans on every single cycle.
const Tracked = struct {
    marked: bool = false,
    survived: u8 = 0, // collections this object has lived through

    fn aged(self: *Tracked) void {
        if (self.survived < 255) self.survived += 1;
    }
};

test "survivors accumulate age across collections" {
    var young = Tracked{};
    var old = Tracked{};

    // Three collections both objects survive.
    for (0..3) |_| {
        young.aged();
        old.aged();
    }
    // Then `young` becomes garbage and is aged no further; `old` lives on.
    for (0..5) |_| old.aged();

    try std.testing.expectEqual(@as(u8, 3), young.survived);
    try std.testing.expectEqual(@as(u8, 8), old.survived);
    // Sorting objects by age - young vs old - is the next optimisation.
}

That survived counter is a small thing, but it is the seed of a much bigger idea: if you know an object is old, you can skip re-examining it most of the time, and concentrate your collector on the churn of freshly-allocated youngsters where nearly all the garbage lives. Segregating objects by age and collecting the young far more often than the old is the optimisation that makes production collectors fast -- and it is precisely where we pick up next time. ;-)

Exercises

Deep vs shallow garbage. Extend the GC with a test that builds a chain of three pairs -- a -> b -> c, where each pair's head points to the next -- and roots only a. Collect, and assert all three survive. Then remove a from the roots (clear the roots list), collect again, and assert all three are reclaimed in a single pass. This proves the collector reclaims an entire unreachable sub-graph, not just its topmost node.
A precise byte counter. Add a bytes_allocated field to the GC that grows by @sizeOf(Obj) on every newObject and shrinks by the same on every sweep of a dead object. Wire in the Heap threshold logic from this episode so the collector runs automatically inside newObject when shouldCollect returns true. Write a test that allocates a burst of unrooted garbage and asserts bytes_allocated never climbs unboundedly -- the automatic collections keep it in check.
Convert the mark phase to a worklist. Replace the recursive mark/markRoots in the full GC with the explicit markIterative worklist from this episode, so the collector can handle arbitrarily deep object graphs without risking a stack overflow. Keep the survival test passing unchanged, then add a new test that roots a 10,000-node chain and confirms it collects nothing (all reachable) -- something the recursive version would be nervous about.

Thanks for reading, and see you in the next one -- our machine can remember with closures, and now it can clean up after itself too. Next time we teach it to be clever about it. ;-)

@scipio