Learn Zig Series):Last episode we built a mark-and-sweep collector and I ended it with a complaint: every single collection re-marks every live object and re-walks every allocation, including the veterans that have already survived a hundred collections and will obviously survive a hundred more. That is a lot of wasted work, and it collides with one of the most reliable observations in all of memory management. Today we act on that observation and build a collector that stops re-scanning the objects that never die. It is the same mark-and-sweep at heart -- we are not throwing anything away -- but organised so the cheap common case stays cheap.
The observation has a name: the weak generational hypothesis, and it says that most objects die young. Think about what your programs actually allocate. The overwhelming majority are temporaries -- the intermediate string in a formatting call, the small slice a helper returns, the pair built inside a loop iteration and dropped before the next one comes around. They live for microseconds. A small minority -- the config loaded at startup, the connection pool, the interned symbols -- are allocated once and live for the entire run. Very few objects live for a "medium" amount of time. If that is true (and decades of measurement say it overwhelmingly is), then a collector should concentrate almost all of its effort on the young objects, where nearly all the garbage is, and mostly leave the old survivors in peace. That is the whole idea of generational garbage collection. Here we go!
Three exercises last time, all extending our mark-and-sweep collector. Full code for each.
Exercise 1 -- Deep vs shallow garbage. Build a chain of three pairs a -> b -> c through the head field, root only a, and confirm all three survive a collection. Then drop a from the roots and collect again: the entire unreachable sub-graph goes in one pass, not just the topmost node. This is the property that makes tracing collectors so pleasant -- you free a data structure by forgetting its root, and the collector reclaims the whole thing:
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,
roots: std.ArrayList(*Obj),
count: usize = 0,
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 n = o.next;
self.alloc.destroy(o);
it = n;
}
self.roots.deinit(self.alloc);
}
fn newObject(self: *GC, kind: ObjKind) !*Obj {
const o = try self.alloc.create(Obj);
o.* = .{ .kind = kind };
o.next = self.objects;
self.objects = o;
self.count += 1;
return o;
}
fn newPair(self: *GC, h: ?*Obj, t: ?*Obj) !*Obj {
const o = try self.newObject(.pair);
o.head = h;
o.tail = t;
return o;
}
fn addRoot(self: *GC, o: *Obj) !void {
try self.roots.append(self.alloc, o);
}
fn mark(self: *GC, obj: ?*Obj) void {
const o = obj orelse return;
if (o.marked) return;
o.marked = true;
if (o.kind == .pair) {
self.mark(o.head);
self.mark(o.tail);
}
}
fn collect(self: *GC) void {
for (self.roots.items) |r| self.mark(r);
var prev: ?*Obj = null;
var it = self.objects;
while (it) |o| {
if (o.marked) {
o.marked = false;
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;
}
}
}
};
test "an entire unreachable sub-graph is reclaimed in one pass" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
const c = try gc.newPair(null, null);
const b = try gc.newPair(c, null);
const a = try gc.newPair(b, null); // a -> b -> c
try gc.addRoot(a);
gc.collect();
try std.testing.expectEqual(@as(usize, 3), gc.count); // all reachable from a
gc.roots.clearRetainingCapacity(); // drop the only handle
gc.collect();
try std.testing.expectEqual(@as(usize, 0), gc.count); // whole chain gone
}
Exercise 2 -- A precise byte counter with automatic collection. Track allocated bytes, and run a collection automatically inside newObject once live memory crosses a threshold that grows with the survivors. Allocate a burst of unrooted garbage and the live count stays bounded, in stead of climbing forever:
const std = @import("std");
const Obj = struct {
marked: bool = false,
next: ?*Obj = null,
head: ?*Obj = null,
tail: ?*Obj = null,
};
const GC = struct {
alloc: std.mem.Allocator,
objects: ?*Obj = null,
roots: std.ArrayList(*Obj),
bytes_allocated: usize = 0,
next_gc: usize = 4 * @sizeOf(Obj),
fn init(a: std.mem.Allocator) GC {
return .{ .alloc = a, .roots = .empty };
}
fn deinit(self: *GC) void {
var it = self.objects;
while (it) |o| {
const n = o.next;
self.alloc.destroy(o);
it = n;
}
self.roots.deinit(self.alloc);
}
fn mark(self: *GC, obj: ?*Obj) void {
const o = obj orelse return;
if (o.marked) return;
o.marked = true;
self.mark(o.head);
self.mark(o.tail);
}
fn collect(self: *GC) void {
for (self.roots.items) |r| self.mark(r);
var prev: ?*Obj = null;
var it = self.objects;
while (it) |o| {
if (o.marked) {
o.marked = false;
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.bytes_allocated -= @sizeOf(Obj);
}
}
}
fn newObject(self: *GC) !*Obj {
if (self.bytes_allocated + @sizeOf(Obj) > self.next_gc) {
self.collect();
self.next_gc = @max(self.next_gc, self.bytes_allocated * 2);
}
const o = try self.alloc.create(Obj);
o.* = .{};
o.next = self.objects;
self.objects = o;
self.bytes_allocated += @sizeOf(Obj);
return o;
}
};
test "automatic collection keeps unrooted garbage bounded" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
for (0..10_000) |_| _ = try gc.newObject(); // a burst nobody roots
// The automatic collections keep live memory near the threshold instead
// of letting it grow to 10k objects.
try std.testing.expect(gc.bytes_allocated < 100 * @sizeOf(Obj));
}
Exercise 3 -- Convert the mark phase to a worklist. Replace recursive marking with an explicit heap-allocated stack so a deep chain marks in a flat loop rather than a mountain of call frames. Root a 10,000-node chain and confirm it survives, something the recursive version would be nervous about:
const std = @import("std");
const Obj = struct {
marked: bool = false,
next: ?*Obj = null,
head: ?*Obj = null,
tail: ?*Obj = null,
};
const GC = struct {
alloc: std.mem.Allocator,
objects: ?*Obj = null,
roots: std.ArrayList(*Obj),
work: std.ArrayList(*Obj),
count: usize = 0,
fn init(a: std.mem.Allocator) GC {
return .{ .alloc = a, .roots = .empty, .work = .empty };
}
fn deinit(self: *GC) void {
var it = self.objects;
while (it) |o| {
const n = o.next;
self.alloc.destroy(o);
it = n;
}
self.roots.deinit(self.alloc);
self.work.deinit(self.alloc);
}
fn newPair(self: *GC, h: ?*Obj, t: ?*Obj) !*Obj {
const o = try self.alloc.create(Obj);
o.* = .{ .head = h, .tail = t };
o.next = self.objects;
self.objects = o;
self.count += 1;
return o;
}
fn addRoot(self: *GC, o: *Obj) !void {
try self.roots.append(self.alloc, o);
}
fn markAll(self: *GC) !void {
for (self.roots.items) |r| try self.work.append(self.alloc, r);
while (self.work.pop()) |o| {
if (o.marked) continue;
o.marked = true;
if (o.head) |h| try self.work.append(self.alloc, h);
if (o.tail) |t| try self.work.append(self.alloc, t);
}
}
};
test "a 10,000-node chain marks without recursion" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
var head: ?*Obj = null;
for (0..10_000) |_| head = try gc.newPair(head, null);
try gc.addRoot(head.?);
try gc.markAll();
try std.testing.expect(gc.objects.?.marked); // reachable chain got marked
try std.testing.expectEqual(@as(usize, 10_000), gc.count);
}
Onward to the real subject.
To act on "most objects die young" we need a way to tell young objects from old ones, and a way to keep them apart. We add two fields to the object header: a generation tag, and one small bookkeeping flag we will need shortly. Everything else is inherited from episode 138 -- the kind tag, the marked bit, the intrusive next pointer:
const std = @import("std");
const ObjKind = enum { int, pair };
// Two generations. Every object records which one it currently lives in.
const Generation = enum { young, old };
const Obj = struct {
kind: ObjKind,
marked: bool = false,
gen: Generation = .young, // born young; promoted on survival
remembered: bool = false, // already queued in the remembered set?
next: ?*Obj = null, // intrusive list WITHIN a generation
value: i64 = 0, // kind == .int
head: ?*Obj = null, // kind == .pair
tail: ?*Obj = null, // kind == .pair
};
test "a fresh object is born into the young generation" {
const o = Obj{ .kind = .int, .value = 5 };
try std.testing.expectEqual(Generation.young, o.gen);
try std.testing.expect(!o.remembered);
}
The plan is this. Every object is born young. A minor collection looks only at the young generation: it reclaims the young garbage and promotes (tenures) the young survivors into the old generation. Because the young generation is small and mostly dead, a minor collection is fast. A major collection is our old friend from episode 138 -- a full mark-and-sweep across both generations -- and we run it rarely, only when the old generation itself has grown enough to be worth scanning. The vast majority of collections are minor, and minor collections never touch the old objects. That is where the speed comes from.
Here is the whole thing. It is longer than last episode's collector, but only because there are now two lists to manage and two collection routines. Read the structure first, then we will pick apart the one genuinely new idea, which lives in writeParent:
const std = @import("std");
const ObjKind = enum { int, pair };
const Generation = enum { young, old };
const Obj = struct {
kind: ObjKind,
marked: bool = false,
gen: Generation = .young,
remembered: bool = false,
next: ?*Obj = null,
value: i64 = 0,
head: ?*Obj = null,
tail: ?*Obj = null,
};
fn freeList(alloc: std.mem.Allocator, list: ?*Obj) void {
var it = list;
while (it) |o| {
const n = o.next;
alloc.destroy(o);
it = n;
}
}
// Filter a list in place: free the unmarked, keep and un-mark the survivors.
fn sweepList(alloc: std.mem.Allocator, list: ?*Obj, count: *usize) ?*Obj {
var kept: ?*Obj = null;
var it = list;
while (it) |o| {
const nxt = o.next;
if (o.marked) {
o.marked = false;
o.next = kept;
kept = o;
} else {
alloc.destroy(o);
count.* -= 1;
}
it = nxt;
}
return kept;
}
const GC = struct {
alloc: std.mem.Allocator,
young: ?*Obj = null,
old: ?*Obj = null,
roots: std.ArrayList(*Obj),
remembered: std.ArrayList(*Obj), // OLD objects holding a pointer into YOUNG
young_count: usize = 0,
old_count: usize = 0,
fn init(alloc: std.mem.Allocator) GC {
return .{ .alloc = alloc, .roots = .empty, .remembered = .empty };
}
fn deinit(self: *GC) void {
freeList(self.alloc, self.young);
freeList(self.alloc, self.old);
self.roots.deinit(self.alloc);
self.remembered.deinit(self.alloc);
}
// Every new object is born YOUNG, linked onto the young list.
fn newObject(self: *GC, kind: ObjKind) !*Obj {
const o = try self.alloc.create(Obj);
o.* = .{ .kind = kind };
o.next = self.young;
self.young = o;
self.young_count += 1;
return o;
}
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, o: *Obj) !void {
try self.roots.append(self.alloc, o);
}
// THE WRITE BARRIER. Whenever an OLD object is made to point at a YOUNG
// one, record the old object, so a minor collection can find that young
// referent without scanning the entire old generation.
fn writeParent(self: *GC, parent: *Obj, slot: enum { head, tail }, child: *Obj) !void {
switch (slot) {
.head => parent.head = child,
.tail => parent.tail = child,
}
if (parent.gen == .old and child.gen == .young and !parent.remembered) {
parent.remembered = true;
try self.remembered.append(self.alloc, parent);
}
}
// Minor mark paints only YOUNG objects; reaching an old object stops the
// trace, since old objects are not collected this cycle.
fn markYoung(self: *GC, obj: ?*Obj) void {
const o = obj orelse return;
if (o.gen == .old) return;
if (o.marked) return;
o.marked = true;
if (o.kind == .pair) {
self.markYoung(o.head);
self.markYoung(o.tail);
}
}
// MINOR collection: reclaim dead young objects, promote the survivors.
fn minorCollect(self: *GC) void {
// Roots for a minor GC: the real roots, PLUS every young object an old
// object points at (captured by the remembered set).
for (self.roots.items) |r| self.markYoung(r);
for (self.remembered.items) |old_obj| {
self.markYoung(old_obj.head);
self.markYoung(old_obj.tail);
}
// Sweep the young list: free the unmarked, promote the marked to old.
var it = self.young;
while (it) |o| {
const nxt = o.next;
if (o.marked) {
o.marked = false;
o.gen = .old; // tenure the survivor
o.next = self.old;
self.old = o;
self.old_count += 1;
} else {
self.alloc.destroy(o);
}
it = nxt;
}
self.young = null; // nothing young remains after a minor GC
self.young_count = 0;
// Every old->young edge is resolved; the remembered set resets.
for (self.remembered.items) |old_obj| old_obj.remembered = false;
self.remembered.clearRetainingCapacity();
}
// Major mark traces EVERYTHING from the roots, ignoring generations.
fn markAny(self: *GC, obj: ?*Obj) void {
const o = obj orelse return;
if (o.marked) return;
o.marked = true;
if (o.kind == .pair) {
self.markAny(o.head);
self.markAny(o.tail);
}
}
// MAJOR collection: a full mark-and-sweep across both generations.
fn majorCollect(self: *GC) void {
for (self.roots.items) |r| self.markAny(r);
self.old = sweepList(self.alloc, self.old, &self.old_count);
self.young = sweepList(self.alloc, self.young, &self.young_count);
for (self.remembered.items) |o| o.remembered = false;
self.remembered.clearRetainingCapacity();
}
};
test "a minor collection reclaims young garbage and promotes survivors" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
const keep = try gc.newPair(try gc.newInt(1), try gc.newInt(2));
_ = try gc.newInt(999); // young garbage
try gc.addRoot(keep);
try std.testing.expectEqual(@as(usize, 4), gc.young_count);
gc.minorCollect();
try std.testing.expectEqual(@as(usize, 0), gc.young_count); // young drained
try std.testing.expectEqual(@as(usize, 3), gc.old_count); // 3 promoted
try std.testing.expectEqual(Generation.old, keep.gen);
try std.testing.expectEqual(@as(i64, 2), keep.tail.?.value); // still readable
}
test "a young object kept alive only by an old object survives a minor GC" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
// Make an old object: allocate, root, run a minor GC to promote it.
const parent = try gc.newPair(null, null);
try gc.addRoot(parent);
gc.minorCollect();
try std.testing.expectEqual(Generation.old, parent.gen);
// Now a fresh YOUNG object, pointed at ONLY by the old parent, through
// the write barrier. It is not a root.
const child = try gc.newInt(42);
try gc.writeParent(parent, .head, child);
gc.minorCollect(); // without the remembered set, child would die here
try std.testing.expectEqual(@as(i64, 42), parent.head.?.value);
try std.testing.expectEqual(Generation.old, parent.head.?.gen); // promoted
}
test "a major collection reclaims dead objects in both generations" {
var gc = GC.init(std.testing.allocator);
defer gc.deinit();
const keep = try gc.newInt(7);
try gc.addRoot(keep);
gc.minorCollect(); // promote keep to old
try std.testing.expectEqual(@as(usize, 1), gc.old_count);
_ = try gc.newInt(100); // young garbage
_ = try gc.newInt(200); // young garbage
gc.majorCollect();
try std.testing.expectEqual(@as(usize, 1), gc.old_count); // keep survives
try std.testing.expectEqual(@as(usize, 0), gc.young_count); // garbage gone
try std.testing.expectEqual(@as(i64, 7), keep.value);
}
The minorCollect routine is the star. Look at what it does not do: it never walks the old list. It marks young objects reachable from the roots, sweeps the young list, and promotes survivors -- and that is the entire cost of a minor collection, proportional to the young generation alone. After it runs, the young generation is empty (everything was either freed or promoted), which is exactly right: young objects that lived through a collection have earned their place among the old.
There is a lie hiding in that description, and if we do not catch it, our collector will free live objects. Here it is. A minor collection marks from the program roots and traces only young objects. But what if an old object holds the only pointer to a live young object? The roots do not mention that young object. The trace never reaches it, because we deliberately stop the moment we hit an old object. So the minor collection would sweep it away while an old object is still pointing right at it -- a use-after-free waiting to happen. This old-points-to-young situation is not exotic: it happens the instant you push a freshly-made element onto a long-lived array, or store a new value into a cache that has been around since startup.
The fix is the write barrier and the remembered set, and they are the reason generational collection is more than a nice idea. A write barrier is a tiny piece of code that runs on every pointer write into an object -- that is what writeParent models. Its job is to notice the dangerous case: an old object being made to point at a young one. When it sees that, it records the old object in the remembered set. Then, at the start of a minor collection, we treat the remembered set as an extra source of roots: for each remembered old object, we mark its young children. The young object that only an old object pointed at is now reachable from the trace, and it survives. That is precisely what the second test above proves -- parent is old, child is young and rooted nowhere else, and it lives only because writeParent remembered parent.
Two details make this pay off. First, the barrier only fires on old-to-young writes -- young-to-young and old-to-old writes are harmless and cost nothing but a branch. Second, the remembered flag on the object keeps each old object in the set at most once, so a hot loop hammering the same array does not flood the remembered set with duplicates. The remembered set is usually tiny, which is the whole point: we pay a couple of instructions per pointer write to avoid scanning megabytes of old objects on every minor collection. Having said that, a write barrier is not free, and this is the fundamental trade of generational GC -- you tax every mutation a little to make every collection a lot cheaper. For the allocation-heavy, mutation-light workloads that dominate real programs, that trade is wildly favourable.
The same discipline from episode 138 protects us here, and generations add a second place for it to help. Collection policy -- how often each generation is collected -- is a total function of the generation tag, and an exhaustive switch makes the compiler enforce that you have an answer for every generation. The day you add a third generation (a survivor space, say), the switch stops compiling until you decide its policy:
const std = @import("std");
const Generation = enum { young, old };
// Collection frequency is a total function of the generation. Because the
// switch is exhaustive, adding a `.survivor` generation would refuse to
// compile until you state how often it is collected.
fn minorsPerCollection(gen: Generation) usize {
return switch (gen) {
.young => 1, // collected every cycle
.old => 10, // one major for roughly every ten minors
};
}
test "generation policy is exhaustive and total" {
try std.testing.expectEqual(@as(usize, 1), minorsPerCollection(.young));
try std.testing.expectEqual(@as(usize, 10), minorsPerCollection(.old));
}
Error unions carry their weight too. writeParent can fail -- appending to the remembered set allocates -- and Zig forces that failure to be a visible !void the caller must handle, not a silently dropped write that would quietly corrupt the remembered set and, three collections later, free a live object. In a language where the barrier can "just fail" invisibly, that is one of the nastiest bugs a runtime can have. Here it is a value you cannot ignore.
Testing a generational collector means testing an invariant, not just an output. The load-bearing invariant is: every old object that points at a young object must be in the remembered set. If that ever breaks, a minor collection will free a live young object -- the exact bug from two sections ago. We can write that invariant as an independent checker and assert it in tests, so a bug in the barrier gets caught by a completely separate piece of code:
const std = @import("std");
const Generation = enum { young, old };
const Node = struct {
gen: Generation,
child: ?*Node = null,
};
// A test-only invariant: every old object pointing at a young object must be
// recorded in the remembered set. A violation is a latent use-after-free.
fn barrierInvariantHolds(all: []const *Node, remembered: []const *Node) bool {
outer: for (all) |o| {
if (o.gen != .old) continue;
const c = o.child orelse continue;
if (c.gen != .young) continue;
for (remembered) |r| {
if (r == o) continue :outer; // covered - good
}
return false; // an unrecorded old->young edge
}
return true;
}
test "the remembered set covers every old-to-young edge" {
var young = Node{ .gen = .young };
var old_ok = Node{ .gen = .old, .child = &young };
var old_bad = Node{ .gen = .old, .child = &young };
var remembered = [_]*Node{&old_ok};
var all_ok = [_]*Node{ &old_ok, &young };
try std.testing.expect(barrierInvariantHolds(&all_ok, &remembered));
var all_bad = [_]*Node{ &old_bad, &young };
try std.testing.expect(!barrierInvariantHolds(&all_bad, &remembered)); // caught
}
This is the same trick as last episode's reachability oracle: a second, dumber implementation of the property, so a bug cannot hide behind the same bug in both. Beyond the invariant, the population tests we already wrote carry a lot of weight -- assert the young count drops to zero after a minor collection, assert the promoted count is exactly the number of survivors, and assert a survivor is still readable afterwards. A collector that frees the right count but corrupts a survivor is still broken, and only that last check catches it.
A generational collector has two thresholds, not one, because it has two collections with wildly different costs. A minor collection is cheap and frequent; a major collection is expensive and rare. So we trigger a minor collection when the young generation fills, and a major collection only after enough minors have run (or the old generation has grown past its own limit). Modelled bare:
const std = @import("std");
// Two independent triggers: fill the young space to fire a cheap MINOR
// collection; count minors until enough have run to justify an expensive
// MAJOR collection that also scans the old generation.
const Schedule = struct {
young_bytes: usize = 0,
young_limit: usize = 64 * 1024,
minors_since_major: usize = 0,
minors_per_major: usize = 8,
fn onAlloc(self: *Schedule, bytes: usize) enum { none, minor, major } {
self.young_bytes += bytes;
if (self.young_bytes < self.young_limit) return .none;
self.young_bytes = 0;
self.minors_since_major += 1;
if (self.minors_since_major >= self.minors_per_major) {
self.minors_since_major = 0;
return .major;
}
return .minor;
}
};
test "minor collections are frequent, major collections are rare" {
var s = Schedule{};
var minors: usize = 0;
var majors: usize = 0;
for (0..64) |_| {
switch (s.onAlloc(64 * 1024)) {
.none => {},
.minor => minors += 1,
.major => majors += 1,
}
}
try std.testing.expectEqual(@as(usize, 56), minors);
try std.testing.expectEqual(@as(usize, 8), majors); // one in eight
}
The lesson from episode 34 applies again: keep the common path cheap. Here the common path is a minor collection over a small young space, and the whole architecture exists to make sure the expensive full scan happens as seldom as we can get away with. Do not tune minors_per_major or young_limit by feel -- pick sane starting values, measure your real allocation pattern, and only then adjust. A great many programs are entirely satiesfied by defaults in this neighbourhood.
Our collector promotes a young object the very first time it survives a collection. That is simple, but it is a little too eager: an object that happens to live slightly longer than one collection gets tenured into the old generation, where reclaiming it later requires an expensive major collection. Real collectors add a survivor space and an aging rule -- an object must survive several minor collections before it is promoted, so medium-lived objects die cheaply in the young generation in stead of polluting the old one. This is exactly the survived counter I planted at the end of episode 138, now doing real work:
const std = @import("std");
// Do not tenure a survivor on its first escape; age it across a few minor
// collections first, so a medium-lived object dies young instead of being
// promoted into the expensive-to-collect old generation.
const Aged = struct {
age: u8 = 0,
const tenure_threshold: u8 = 3;
fn survivedMinor(self: *Aged) bool {
self.age += 1;
return self.age >= tenure_threshold; // true => promote to old
}
};
test "an object is tenured only after several minor collections" {
var o = Aged{};
try std.testing.expect(!o.survivedMinor()); // age 1: stays young
try std.testing.expect(!o.survivedMinor()); // age 2: stays young
try std.testing.expect(o.survivedMinor()); // age 3: promote
}
Now, how do the big runtimes stand on all this? The bargains genuinely differ. Java's HotSpot is the textbook generational collector -- an Eden space where objects are born, two survivor spaces they are copied between while aging, and an old generation for the tenured; its collectors (G1, ZGC) are elaborate machinery built on exactly the young-often, old-rarely idea we just implemented. V8, the JavaScript engine, is generational too: a small "new space" scavenged constantly with a copying collector, and an "old space" collected by mark-sweep-compact -- which is why allocation-heavy JS stays fast, most of that garbage never leaves the new space. Go, interestingly, is not generational: it runs a single concurrent tri-color mark-and-sweep and bets on low-latency concurrency and escape analysis (keeping short-lived objects off the heap entirely) in stead of generations -- a deliberate, and sometimes debated, engineering choice. And Rust, as last episode, sidesteps the whole question: ownership frees objects at compile-time-known points, and when you opt into Rc/Arc you get reference counting, whose cyclic-leak weakness a generational tracer does not share. We have now built the core that V8 and the JVM are elaborations of; theirs add copying, compaction and concurrency on top of the same skeleton.
A generational collector is what you reach for the moment a mark-and-sweep runtime starts spending too much time collecting -- which, for any interpreter whose programs allocate freely (every scripting language, our little VM included), happens quickly. The young/old split is not an academic nicety; it is the single change that takes a toy collector from "correct but pauses too much" to "usable in production", precisely because it aligns the collector's effort with where the garbage actually is. If you take one idea from this episode into your own runtime, let it be that: measure your object lifetimes, and if most of them are short (they will be), collect the young space often and leave the old alone.
That, for now, closes our tour of automatic memory management. Our little machine can parse, compile to bytecode, run on a stack VM, hold closures, and clean up after itself efficiently. It is correct. What it is not, yet, is fast in the way a real language runtime is fast -- every instruction still travels through the interpreter's big dispatch loop, one bytecode at a time. The forementioned dispatch overhead is the next mountain to climb, and climbing it means teaching our machine to stop interpreting and start generating real code. That is where we go next.
A promotion counter. Add a promotions: usize field to the GC that increments each time minorCollect tenures a young object into the old generation. Write a test that allocates a rooted structure plus a pile of young garbage, runs one minor collection, and asserts promotions equals exactly the number of rooted (reachable) objects -- proving the survivors, and only the survivors, were promoted.
Age before tenure. Fold the Aged idea into the real GC: give Obj an age: u8, and in minorCollect, only move a marked young object to the old generation once its age reaches a threshold -- otherwise keep it young (increment its age and leave it on a rebuilt young list). Write a test showing an object that survives two minor collections is still young, and after a third is finally old.
A remembered-set stress test. Build ten old objects (allocate, root, minor-collect to promote them), then in a loop point each old object at a freshly allocated young object through writeParent. Run a minor collection and assert all ten young objects survived and were promoted, and that the remembered set is empty afterwards. This proves the write barrier scales past the single old-to-young edge the tests above cover.
That is our garbage collector grown up -- young objects swept often, old ones left in peace, and a write barrier holding the two worlds together. Thanks for reading! Next time we stop merely cleaning up after our little machine and start making it genuinely fast. ;-)
@scipio