MemoryPool(T) from scratch in Zig, where both create and destroy collapse to a single pointer pop and a single pointer push -- O(1), branchless, no searching;union { item: T, next: ?*Cell } is the exact shape the problem wants, and how @fieldParentPtr lets you walk from an object pointer back to its cell for free;error.OutOfMemory you must handle or a null you cannot ignore -- your choice, spelled in the type;std.heap.MemoryPool, why it exists, and when to reach for it instead of rolling your own;malloc arenas), Rust (typed-arena and slab crates), and Go (sync.Pool), and why the memory-safety story differs sharply across the four.Learn Zig Series):Episode 113 ended on a promise. We built a lock-free ring buffer and I pointed at the thing it quietly refuses to do -- it never calls the allocator on the hot path. It grabs one slab of memory up front and then recycles slots forever, so the same bytes serve a million items without a single alloc/free round-trip. And I said that this is not a quirk of ring buffers, it is a strategy: when you know the shape and size of what you are storing, you stop begging the general-purpose allocator for memory one object at a time and start managing a fixed reservoir yourself.
The ring recycles slots in a FIFO circle. Today we generalise the idea to recycle memory itself, in any order, for thousands of same-sized objects churning through create-and-destroy cycles. Network connections, particle systems, game entities, AST nodes, tree cells -- anywhere you allocate and free a zillion identically-shaped things and the general allocator's per-call overhead and fragmentation are eating your lunch. The structure that fixes it is the memory pool, and it is almost embarrassingly simple once you see the trick. But first -- the ring buffer debt from last week, three exercises, all with real code ;-)
Exercise 1 -- batch the pops. Instead of one .acquire/.release pair per item, drain up to out.len items at once and advance head a single time. The wrinkle is the wrap: the available items may straddle the end of the array, so you may need two copies. Here is popSlice, a consumer-side method on the SPSC ring:
fn popSlice(self: *Self, out: []T) usize {
const head = self.head.load(.monotonic); // we are head's only writer
const tail = self.tail.load(.acquire); // acquire: pairs with the producer's release
const available = tail - head;
const n = @min(available, out.len);
if (n == 0) return 0;
const start = head & mask;
const first = @min(n, capacity - start); // how many run from `start` to the array's end
@memcpy(out[0..first], self.buf[start .. start + first]);
if (first < n) { // wrapped: the rest is at the front of buf
@memcpy(out[first..n], self.buf[0 .. n - first]);
}
self.head.store(head + n, .release); // ONE release, after both copies -- frees all n slots
return n;
}
Why is the single release after both copies still correct? Because the release store is what publishes "these slots are free" to the producer. As long as every read of slot contents (@memcpy out of buf) happens before that store in program order, the producer cannot observe the freed head until our reads are done -- so it cannot overwrite a slot we are still copying out of. Batching does not weaken the ordering guarantee at all; it just amortises one .release across n items instead of paying it n times. On a deep ring drained in bursts, that is a real win.
Exercise 2 -- prove the ordering matters. Take the working ring, weaken the producer's tail store from .release to .monotonic, and watch it pass on x86-64 anyway (x86 is strongly ordered and hides the bug), then try to make it fail on ARM. The one-line change:
// BROKEN ON PURPOSE: .monotonic drops the happens-before edge that .release provided.
// The slot write (1) is no longer guaranteed visible before the new tail (2).
self.buf[tail & mask] = item; // (1)
self.tail.store(tail +% 1, .monotonic); // (2) was .release -- now publishes nothing
Build the stress test for ARM with the target-triple machinery from episode 35 and run it under an emulator:
// zig build test -Dtarget=aarch64-linux -fqemu (needs qemu-aarch64 installed)
// On x86-64 the checksum test passes ~every run even while broken.
// Under aarch64 the consumer can read tail advanced BEFORE the slot write lands,
// pop an uninitialised slot, and the million-item checksum comes out wrong.
The honest lesson: a bug being possible under the memory model is not the same as it being observable on a given run. x86's strong ordering silently repairs a missing .release, so the test is green on your laptop forever -- and then corrupts one run in ten thousand on a phone. That asymmetry is exactly why you write the ordering annotations from the model, not from what your local hardware happens to tolerate.
Exercise 3 -- a bounded blocking variant. When you would rather the producer sleep than spin on a full ring, wrap the array with a mutex and two condition variables:
fn BlockingRing(comptime T: type, comptime capacity: usize) type {
comptime std.debug.assert(capacity != 0 and (capacity & (capacity - 1)) == 0);
return struct {
const Self = @This();
const mask = capacity - 1;
buf: [capacity]T = undefined,
head: usize = 0,
tail: usize = 0,
mutex: std.Thread.Mutex = .{},
not_full: std.Thread.Condition = .{},
not_empty: std.Thread.Condition = .{},
fn push(self: *Self, item: T) void {
self.mutex.lock();
defer self.mutex.unlock();
while (self.tail - self.head == capacity) // while, not if: guards spurious wakeups
self.not_full.wait(&self.mutex);
self.buf[self.tail & mask] = item;
self.tail += 1;
self.not_empty.signal(); // a slot appeared -- wake one consumer
}
fn pop(self: *Self) T {
self.mutex.lock();
defer self.mutex.unlock();
while (self.head == self.tail)
self.not_empty.wait(&self.mutex);
const item = self.buf[self.head & mask];
self.head += 1;
self.not_full.signal(); // a slot freed -- wake one producer
return item;
}
};
}
Which to pick? For a producer that outruns the consumer by a hair, lock-free-plus-spin wins: the spin is short, the cache line stays hot, and you never pay a syscall to sleep and wake. But that flips the moment the imbalance grows. If the ring sits almost always full (producer way ahead), the lock-free producer burns a whole core spinning uselessly, and the condvar version -- which puts that thread to sleep -- is strictly better for throughput-per-watt. Near-empty is the mirror image on the consumer side. The while around each wait is not optional, by the way: condition variables are allowed to wake spuriously, so you re-check the predicate every time you surface. Right. Debt paid -- on to the pool.
Here is the whole memory pool in one breath. Ask the general allocator for one big block of N identically-sized cells, once. Keep a pointer to the first free cell. To allocate, pop the head of that free list and hand it back. To free, push the cell back onto the head of the list. Both operations are a single pointer assignment -- O(1), no search, no size classes, no fragmentation, because every cell is interchangeable with every other.
The clever bit -- the part that makes it cost nothing in bookkeeping memory -- is where the free list lives. A cell that is currently free is, by definition, not holding an object. So its bytes are idle. We use those idle bytes to store the "next free cell" pointer. The free list is threaded through the storage itself; there is no separate array of pointers, no metadata block, no header per cell. A free cell is a list node; an in-use cell is your object. It is only ever one or the other, never both at once, which is the textbook definition of a union.
That is the entire concept. Everything below is just spelling it in Zig and being careful about the edges.
I want this generic over the element type, fixed at compile time -- the comptime-generics pattern from episode 14. The cell is an untagged union of "your object" and "a next pointer", and I let the backing allocator hand me blocks of them:
const std = @import("std");
fn MemoryPool(comptime T: type) type {
return struct {
const Self = @This();
// A cell is your object OR a free-list node -- never both at once.
// Untagged: we track which state it is in externally (it is free iff it is
// reachable from free_list), so we pay zero bytes for a tag.
const Cell = union {
item: T,
next: ?*Cell,
};
// Blocks are chained so deinit can walk and free every slab we ever grabbed.
const Block = struct {
cells: []Cell,
prev: ?*Block,
};
backing: std.mem.Allocator,
free_list: ?*Cell = null,
blocks: ?*Block = null,
per_block: usize,
fn init(backing: std.mem.Allocator, per_block: usize) Self {
return .{ .backing = backing, .per_block = per_block };
}
fn deinit(self: *Self) void {
var b = self.blocks;
while (b) |block| {
const prev = block.prev;
self.backing.free(block.cells);
self.backing.destroy(block);
b = prev;
}
self.* = undefined; // poison: using the pool after deinit is now an obvious crash
}
};
}
Notice what the pool owns: a backing allocator, the head of the free list, the head of the block chain, and how many cells to grab per growth. That is it. No per-cell metadata anywhere -- the Cell union is exactly @max(@sizeOf(T), @sizeOf(?*Cell)) bytes wide, which for any T at least pointer-sized is just @sizeOf(T). The free list is genuinely free.
When the free list runs dry, we grow: grab a fresh block of per_block cells and thread every one of them onto the free list. Then create and destroy are the one-liners the whole design promised:
fn grow(self: *Self) !void {
const cells = try self.backing.alloc(Cell, self.per_block);
const block = try self.backing.create(Block);
block.* = .{ .cells = cells, .prev = self.blocks };
self.blocks = block;
// Push every new cell onto the free list. Back-to-front so cell[0] ends up on top --
// purely cosmetic, but it means a fresh pool hands out cells in address order.
var i: usize = cells.len;
while (i > 0) {
i -= 1;
cells[i] = .{ .next = self.free_list }; // activate the cell AS a free-list node
self.free_list = &cells[i];
}
}
fn create(self: *Self) !*T {
if (self.free_list == null) try self.grow(); // amortised: one alloc buys per_block objects
const cell = self.free_list.?;
self.free_list = cell.next; // read the next pointer OUT before we clobber it
cell.* = .{ .item = undefined }; // now flip the cell to hold an object
return &cell.item; // hand back the object-typed view
}
fn destroy(self: *Self, ptr: *T) void {
const cell: *Cell = @fieldParentPtr("item", ptr); // walk from the object back to its cell
cell.* = .{ .next = self.free_list }; // flip it back to a free-list node
self.free_list = cell;
}
Two details carry this. First, @fieldParentPtr: the caller only ever sees a *T -- the &cell.item view we handed out. To recycle it we need the *Cell that contains that item field, and @fieldParentPtr("item", ptr) computes the address of the enclosing union from a pointer to one of its fields. Because item sits at offset 0 the address is literally the same, but expressing it this way is intention-revealing and stays correct even if you later wrap the cell in a header. Compare the C version: a raw (Cell*)ptr cast the compiler cannot check at all.
Second -- and this is the bit Zig makes you say out loud where C lets you cheat -- every transition assigns the whole union (cell.* = .{ .next = ... } and cell.* = .{ .item = undefined }) rather than poking a field. A union field is only legal to read while it is the active one, so we flip the active field explicitly: grow and destroy activate next, create reads next out and then activates item before handing back &cell.item. That whole-value assignment is exactly what tells Zig "this cell now means something different", and it is why the overlay is safe rather than a reinterpret-cast you have to get right in your head. The undefined payload is deliberate -- a recycled cell holds junk until the caller fills it, precisely like the bytes malloc hands you.
The amortisation is worth saying out loud. create calls the real allocator only when the free list is empty -- once per per_block objects. Set per_block to 1024 and 1023 out of every 1024 create calls are a pointer pop with no allocator involvement whatsoever. That is the entire performance story of a pool in one sentence.
The comptime T means one MemoryPool source serves a pool of 16-byte particles, a pool of 200-byte connection structs, or a pool of tree nodes -- each monomorphised into its own tight code with the cell size baked in as a compile-time constant, zero runtime dispatch. The union's width is computed at compile time, so there is never a moment where a cell is the wrong size for its T.
Error handling is the other half. Because create returns !*T, "the pool needed to grow and the OS said no" surfaces as a normal error.OutOfMemory that the caller must handle with try or catch -- it cannot be silently ignored the way a C malloc returning NULL routinely is. And if you would rather a fixed-capacity pool that refuses to grow (common in embedded or real-time code where you must never call the OS allocator after startup), you make exhaustion a null in stead of an error:
// A pool that never grows: exhaustion is an ordinary null, not an error.
fn createFixed(self: *Self) ?*T {
const cell = self.free_list orelse return null; // no grow() -- caller decides what "full" means
self.free_list = cell.next;
cell.* = .{ .item = undefined };
return &cell.item;
}
Same machinery, different contract -- the exact parallel to episode 113's bool-vs-error-union choice for a full ring. The optional says "being full is ordinary, handle it inline"; the error union says "growing failed, that is exceptional, propagate it". Zig lets the return type tell whichever story fits your domain, and the caller cannot forget to reckon with it either way.
Here is the honest disclosure a good tutorial owes you: you rarely need to write this yourself, because the standard library has std.heap.MemoryPool, built on exactly the union-free-list idea we just derived. Reach for it first:
test "std.heap.MemoryPool does the same job" {
const Particle = struct { x: f32, y: f32, vx: f32, vy: f32 };
var pool = std.heap.MemoryPool(Particle).init(std.testing.allocator);
defer pool.deinit();
const a = try pool.create(); // *Particle, carved from a pooled block
a.* = .{ .x = 0, .y = 0, .vx = 1, .vy = -1 };
pool.destroy(a); // back onto the free list
const b = try pool.create(); // reuses a's cell -- same address
try std.testing.expect(a == b);
}
So why did we build our own? Same reason we always do in this series: you cannot reason about a tool you have only ever called. Now that you have written the free-list threading and the @fieldParentPtr recycle by hand, std.heap.MemoryPool is not a black box -- you know precisely what its create costs (a pointer pop, or one backing allocation per block), why its cells are all one size, and when it will and will not help you. That understanding is the actual deliverable; the stdlib type is just the version you ship. Having said that, our hand-rolled pool has one thing the stdlib one does not by default: you control per_block, which lets you tune the allocation granularity to your workload.
The three properties that matter for a pool are address reuse (a freed cell comes back), block growth (it survives more objects than one block holds), and that objects stay independent (no accidental aliasing). All three are checkable without any concurrency, which makes pool tests far gentler than last week's lock-free stress runs:
test "pool reuses the exact cell it just freed" {
const Point = struct { x: f64, y: f64 };
var pool = MemoryPool(Point).init(std.testing.allocator, 16);
defer pool.deinit();
const a = try pool.create();
const addr_a = @intFromPtr(a);
pool.destroy(a);
const b = try pool.create(); // free list is LIFO: b must be a's cell
try std.testing.expectEqual(addr_a, @intFromPtr(b));
pool.destroy(b);
}
test "pool grows past a single block and keeps every object distinct" {
var pool = MemoryPool(u64).init(std.testing.allocator, 4); // tiny blocks -> forces growth
defer pool.deinit();
var ptrs: [100]*u64 = undefined;
for (&ptrs, 0..) |*slot, i| {
slot.* = try pool.create();
slot.*.* = i; // stamp each object with its index
}
for (ptrs, 0..) |p, i| // if any two aliased, a stamp would be wrong
try std.testing.expectEqual(@as(u64, i), p.*);
for (ptrs) |p| pool.destroy(p);
}
The second test is the sneaky-important one. With per_block = 4 and 100 live objects, the pool is forced to grow two dozen times, and stamping each object with a unique index then reading it back proves that no two create calls ever handed out the same cell -- an aliasing bug that a lazier test (just counting allocations) would sail right past. And because we used std.testing.allocator, the test harness also verifies our deinit frees every block -- a leak would fail the test outright. Nota bene the pool does not zero cells on reuse: a recycled cell holds whatever the previous object left there, so your code must fully initialise every object after create, exactly as you would after malloc.
A quick benchmark makes the difference visceral. Write two identical hot loops -- one that hammers create/destroy through a general-purpose allocator, one through the pool -- and time each with your platform's monotonic clock (the timing API has moved around between Zig versions, so I keep the measured loops separate and leave the stopwatch to you):
// Time each of these around a million iterations. Both take a *plain* allocator interface,
// so you can hand hammerGeneral a GeneralPurposeAllocator (or a DebugAllocator on newer Zig)
// and hammerPool the pool, then compare wall-clock nanoseconds.
fn hammerGeneral(ga: std.mem.Allocator, n: usize) !void {
var i: usize = 0;
while (i < n) : (i += 1) {
const p = try ga.create(u64); // a full allocator round-trip, every single iteration
ga.destroy(p);
}
}
fn hammerPool(pool: *MemoryPool(u64), n: usize) !void {
var i: usize = 0;
while (i < n) : (i += 1) {
const p = try pool.create(); // a bare pointer pop 4095 times out of every 4096
pool.destroy(p);
}
}
Run hammerGeneral against your general-purpose allocator and hammerPool against a MemoryPool(u64) built with, say, per_block = 4096. The pool typically lands several times faster, and the gap widens the more work the general allocator has to do to find a free block of the right size. That is the first win: speed, from turning an allocator search into a pointer pop. The second, quieter win is no fragmentation -- every cell is the same size, so there are no awkward gaps a general allocator has to track and coalesce, and a freed cell is always immediately reusable by the next create. A third, often-decisive win is cache locality: because all cells come from a handful of contiguous blocks, objects that were allocated near each other in time also sit near each other in memory, and iterating a pool of live objects streams through cache the way the ring buffer's flat array did in episode 113.
But a pool is not a free lunch, and a tutorial that pretends otherwise is lying to you. The first cost is rigidity: a pool serves one size. The moment you need a different-sized object you need a different pool, and if your workload's object sizes are all over the map, you are back to wanting a general allocator (or a whole family of pools, which is where next episode is heading). The second cost is a safety footgun: the pool does not track which cells are live, so a double-free -- calling destroy twice on the same pointer -- silently corrupts the free list into a cycle, and a use-after-free reads a cell that has already been handed to someone else. The general allocator in debug mode catches some of that; a bare pool catches none of it. You trade a slice of safety for the speed, and you have to know you made that trade.
Pools shine wherever you have a high-frequency churn of same-sized objects with a clear lifetime. Game engines pool entities, particles, and components (this is half of why the ECS we built back in episodes 55-58 is fast). Network servers pool per-connection state structs, carving one on accept and recycling it on close. Interpreters and compilers pool AST and IR nodes. Kernels pool task_structs and network buffers -- Linux's slab allocator is a pool taken to its industrial conclusion. Any tree or graph whose nodes are all one type is a natural pool client: instead of a create per node hitting the general allocator, every node comes from one pool and the whole structure frees in one deinit.
When should you not? If your objects vary wildly in size, a single pool is the wrong shape. If your allocation volume is low -- a few dozen objects over a program's life -- the pool is premature optimisation and a plain allocator.create is clearer. And if you need the debug allocator's use-after-free and double-free detection more than you need the speed, stay on the general allocator until a profiler (episode 34) actually points at allocation as your bottleneck. Reach for a pool when the numbers tell you to, not because it is clever.
In C, a memory pool is the canonical "custom allocator" exercise: a struct with a void *free_list, a block list, and pool_alloc/pool_free that cast the free cell to a struct node * to read the next pointer. It is the same union trick, but unchecked -- the cast from object to node is a raw reinterpret the compiler cannot verify, nothing stops you pooling the wrong-sized type, and a double-free corrupts the list exactly as in Zig but with zero tooling to notice. Every serious C codebase (nginx, Redis, the Linux kernel, PostgreSQL's memory contexts) has its own hand-rolled pool, because the language ships nothing and the pattern is too valuable to skip.
In Rust, the ownership model makes the naive version awkward for the same reason the ring buffer was awkward: a pool that hands out &mut T while still owning the backing storage fights the borrow checker head-on. The idiomatic answers are crates -- typed-arena (bump-allocates same-typed objects, frees them all at once, no individual destroy), slab (a Vec-backed pool that hands out integer keys instead of pointers, sidestepping lifetimes entirely), and bumpalo for arena allocation. Each buys memory safety by changing the API so the compiler can prove no dangling reference survives, at the cost of the raw pointer ergonomics C and Zig give you. Rust makes the safety a type; you pay for it in interface.
In Go, the standard library ships sync.Pool, but it is a different beast -- a concurrent, GC-aware pool of temporary objects that the garbage collector is allowed to empty at any time, meant to relieve GC pressure rather than to give you deterministic O(1) allocation. You Get and Put interface{} values, and you must never assume an object is still in the pool. It is genuinely useful for reducing allocation churn on hot paths (the standard library uses it internally for buffers), but it gives you none of the layout control or determinism our Zig pool does, because Go's whole point is to not think about memory.
Our Zig version sits where it always does: the element type fixed in the type so the cell size is a compile-time constant, the free list threaded through the storage at zero metadata cost, @fieldParentPtr making the object-to-cell walk explicit and checkable, and the !*T-versus-?*T return letting you choose whether exhaustion is an error or an ordinary value. Same pattern across four languages -- but only here is it a handful of lines you can read in one sitting, with no GC, no borrow-checker ceremony, and no unchecked cast ;-)
Add a poison-on-free debug check. Extend destroy so that, when built in Debug mode (check @import("builtin").mode), it first walks the free list to confirm ptr's cell is not already on it -- turning a silent double-free into a loud @panic. Measure what this costs on the benchmark above (hint: an O(n) walk per free is brutal on a big pool), then propose a cheaper scheme -- a single "is-free" bit or a generation counter per cell -- that catches the same bug in O(1). Argue which you would actually ship.
A pool that reclaims empty blocks. Our deinit frees everything, but while running, the pool only ever grows -- a burst of a million objects leaves a million cells allocated forever, even after they are all freed. Add bookkeeping so a block whose cells are all back on the free list can be returned to the backing allocator. Think hard about the cost: how do you know a whole block is free without an O(n) scan, and is the added per-cell bookkeeping worth it versus just accepting the high-water-mark memory? Write up the trade.
Benchmark pool-of-nodes versus general-allocator-of-nodes on a real structure. Take the singly-linked list from episode 106, build it two ways -- once with every node from allocator.create, once with every node from a MemoryPool -- insert a million nodes, iterate them summing a field, then tear down. Time all three phases (build, iterate, free) separately. Explain which phase the pool helps most and why the iterate phase differs even though neither version allocates during iteration (hint: where do the nodes physically live?).
Step back and look at the load-bearing assumption under everything today: one size. The pool is fast precisely because every cell is interchangeable -- allocation is a pointer pop exactly because the allocator never has to ask "is this hole big enough?". That single constraint is what buys us O(1), zero fragmentation, and cache-friendly layout all at once.
But real programs are not so tidy. A kernel does not allocate only task_structs -- it allocates task structs and inodes and network buffers and file descriptors, dozens of distinct fixed sizes, each churning at its own rate. You could run a separate MemoryPool per type by hand, but the moment you have thirty of them you start wanting one system that manages a family of pools, routes each allocation to the pool for its size class, carves those pools out of larger page-sized runs, and hands whole pages back to the OS when a run goes cold. That is the design that actually sits under malloc in a modern libc and under the slab layer in Linux -- the forementioned pool idea, scaled up into a size-classed allocator with page-level bookkeeping. We built the single-size reservoir today. Next we build the machine that manages many of them at once, and the free-list trick you just learned becomes one gear in a much bigger clock ;-)
Bedankt voor het lezen, en tot de volgende keer!
@scipio