Learn Zig Series (#113) - Ring Buffers: Lock-Free

avatar

Learn Zig Series (#113) - Ring Buffers: Lock-Free

zig.png

What will I learn?

  • Why a ring buffer (a.k.a. circular buffer) is the data structure that answers the question episode 112 ended on -- a buffer of exactly known size that you fill and drain forever, handing slots back the instant you are done, with no allocator call on the hot path at all;
  • The one arithmetic trick that makes the whole thing work -- monotonic head and tail counters that never wrap, masked into an index only at the moment of access, which quietly kills the classic "is it full or empty?" ambiguity;
  • What "lock-free" actually buys you and what it costs, and why a single-producer/single-consumer (SPSC) ring is the sweet spot where you can drop the mutex entirely and still be provably correct;
  • How memory ordering -- the acquire/release pairing we first met with atomics back in episode 30 -- is the load-bearing wall of a lockless queue, and exactly which store must happen-before which load or the whole thing corrupts silently on a weakly-ordered CPU;
  • How to build a generic RingBuffer(T, capacity) from scratch in Zig, with comptime enforcing the power-of-two size at compile time and the element type baked into the buffer;
  • How to test a structure whose bugs only appear under real concurrency -- a million items crossing a thread boundary, and the checksum that proves not one was lost or duplicated;
  • Why false sharing is the performance trap that turns a "lock-free" queue into a slow one, and how a few bytes of cache-line padding claw the throughput back;
  • How the same design maps onto C, Rust, and Go, and why the memory-ordering annotations are the part where each language shows its hand.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Zig 0.14+ distribution (download from ziglang.org);
  • Episode 112 fresh in mind -- we built a cuckoo filter, got clean deletion, and hit the first real crack in the "size it once and leave it alone" comfort: error.TableFull, the moment a structure had to say "do something about my memory";
  • A working feel for atomics and memory ordering from episode 30 -- this episode leans on it harder than any since;
  • Comfort with comptime generics (episode 14) and power-of-two bit masking (the trick recurs from episodes 17 and 22);
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#113) - Ring Buffers: Lock-Free

I closed episode 112 by turning the whole series on its side. For a hundred-odd episodes we obsessed over what to store -- lists, trees, tries, filters. Then the cuckoo filter's error.TableFull cracked that open: a structure that had to look up from its own contents and say "I am out of room, do something". And I asked what happens if the fixed-size table is not a wall to grow past but the entire point -- a buffer of exactly known size you fill and drain and refill forever, handing each slot back the instant you are done with it, with no allocator call on the hot path at all. Then the harder half of the question: what if two threads could push and pop from that buffer at the same time, without ever taking a lock, leaning on nothing but the atomics we met in episode 30?

That structure is the ring buffer -- circular buffer, if you learned it under that name -- and the lock-free single-producer/single-consumer version is one of the genuinely beautiful things in systems programming. It is the beating heart of audio pipelines, network card drivers, log collectors, and every "producer thread hands work to a consumer thread" pattern you will ever write. Today we build it, we make it lock-free, and we prove it correct under a million-item stress test. But first -- the debt from last week, three exercises, all with real code ;-)

Solutions to Episode 112 Exercises

Exercise 1 -- tighten the fingerprint to u16, measure the rate. The change is mechanical: the fingerprint function keeps the low 16 bits instead of 8, and the backing store becomes []u16 instead of []u8. Every extra bit of fingerprint roughly halves the false-positive rate, so eight extra bits should divide it by about 256. Here are the two functions that actually change, plus the measurement test that confirms it:

// buckets is now []u16 (allocated with allocator.alloc(u16, ...) and @memset to 0).
fn fingerprint(key: []const u8) u16 {
    const h = std.hash.Wyhash.hash(0x9E3779B97F4A7C15, key);
    const fp: u16 = @truncate(h);   // keep the low 16 bits -- was @truncate to u8 before
    return if (fp == 0) 1 else fp;  // 0 still reserved for "empty slot"
}

fn altIndex(self: *Self, i: usize, fp: u16) usize {
    const h = std.hash.Wyhash.hash(0x2545F4914F6CDD1D, std.mem.asBytes(&fp)); // hash both bytes now
    return i ^ (@as(usize, @intCast(h)) & (self.num_buckets - 1));
}

test "u16 fingerprint slashes the false-positive rate" {
    var cf = try CuckooFilter16.init(std.testing.allocator, 8192);
    defer cf.deinit();
    var buf: [24]u8 = undefined;
    var i: usize = 0;
    while (i < 4000) : (i += 1) {
        const key = try std.fmt.bufPrint(&buf, "member-{d}", .{i});
        try cf.add(key);
    }
    var fp_hits: usize = 0;
    i = 0;
    while (i < 200000) : (i += 1) { // 10x the sample -- a ~0.01% rate needs a big denominator to see
        const key = try std.fmt.bufPrint(&buf, "stranger-{d}", .{i});
        if (cf.contains(key)) fp_hits += 1;
    }
    const rate = @as(f64, @floatFromInt(fp_hits)) / 200000.0;
    try std.testing.expect(rate < 0.001); // 8-bit sat ~3%; 16-bit lands near 0.01%, assert < 0.1%
}

The trade you just made: one extra byte per slot (doubling the table's memory) bought roughly a 256-fold drop in false positives. Nota bene the test now samples ten times as many strangers -- at a 0.01% rate, 20,000 samples might show you two or three hits and the measured rate becomes pure noise, so you widen the denominator to get a number you can actually assert on. For a 0.01% target you would now firmly pick the cuckoo filter: the u16 version sits right at that rate and keeps deletion, where a bloom filter matching it would cost more bits per key.

Exercise 2 -- resize on error.TableFull. Wrap add so that a full table triggers a rebuild at double the bucket count. The subtle part I warned about: you cannot copy fingerprints slot-for-slot, because primaryIndex and altIndex both mask against num_buckets, and that mask just changed. But you can recompute a fingerprint's home in the new table from the fingerprint and its old bucket alone -- that is exactly the involution the cuckoo filter is built on:

fn addOrGrow(self: *Self, key: []const u8) !void {
    self.add(key) catch |err| switch (err) {
        error.TableFull => {
            try self.grow();      // double the table, re-home every live fingerprint
            try self.add(key);    // the insert that failed now has room
        },
    };
}

fn grow(self: *Self) !void {
    const old_buckets = self.buckets;
    const old_nb = self.num_buckets;
    const new_nb = old_nb * 2;
    const new_buckets = try self.allocator.alloc(u8, new_nb * bucket_size);
    @memset(new_buckets, 0);
    self.buckets = new_buckets;
    self.num_buckets = new_nb;
    self.count = 0; // re-add rebuilds the count

    // Re-home each live fingerprint. We have no keys -- but a fingerprint plus its old
    // bucket is enough to reconstruct its TWO candidates and drop it into either.
    var b: usize = 0;
    while (b < old_nb) : (b += 1) {
        for (old_buckets[b * bucket_size .. (b + 1) * bucket_size]) |fp| {
            if (fp == 0) continue;
            // In the OLD table, this fp lived in bucket b, so its partner was altIndex(b, fp).
            // In the NEW table both indices are recomputed against the larger mask.
            const i1 = b & (new_nb - 1);
            if (!self.insertIntoBucket(i1, fp)) {
                _ = self.insertIntoBucket(self.altIndex(i1, fp), fp);
            }
            self.count += 1;
        }
    }
    self.allocator.free(old_buckets);
}

Why this is trickier for a cuckoo filter than for a bloom filter is the punchline worth stating out loud: a bloom filter cannot be resized this way at all. Its bits are the OR of k hash positions computed modulo the old size; halving or doubling m changes every one of those positions and there is no way to recover which keys set which bits, because the keys were never stored and the bits are shared. The cuckoo filter escapes that trap only because a fingerprint is a self-contained token that still knows how to find its own buckets. That is the same property that made deletion possible -- it is the gift that keeps giving.

Exercise 3 -- pack two fingerprints into three bytes (12-bit fingerprints). An 8-bit fingerprint over-serves if 12 bits is your accuracy target, and a full u16 wastes space the other way. Four 12-bit values fit in exactly 6 bytes per bucket. The arithmetic is the same nibble-and-byte dance as the counting bloom filter, one level fiddlier:

// Four 12-bit fingerprints packed into 6 bytes. slot in 0..3.
fn getSlot(bucket_bytes: []const u8, slot: usize) u12 {
    const bit = slot * 12;
    const byte = bit >> 3;             // starting byte
    const shift: u4 = @intCast(bit & 7); // bit offset within that byte
    const word = @as(u16, bucket_bytes[byte]) | (@as(u16, bucket_bytes[byte + 1]) << 8);
    return @truncate(word >> shift);   // 12 bits, straddling at most two bytes
}

fn setSlot(bucket_bytes: []u8, slot: usize, fp: u12) void {
    const bit = slot * 12;
    const byte = bit >> 3;
    const shift: u4 = @intCast(bit & 7);
    const mask = @as(u16, 0x0FFF) << shift;
    var word = @as(u16, bucket_bytes[byte]) | (@as(u16, bucket_bytes[byte + 1]) << 8);
    word = (word & ~mask) | (@as(u16, fp) << shift); // clear the 12-bit field, drop fp in
    bucket_bytes[byte] = @truncate(word);
    bucket_bytes[byte + 1] = @truncate(word >> 8);
}

Keep 0 reserved as empty exactly as before, re-run all three episode tests against the packed layout, and the accounting lands like this: the u12 version costs 12 bits per slot versus 8 for the u8 (50% more memory) but 25% less than the u16, while its false-positive rate sits between the two. What you paid for it is in contains latency -- a packed read is no longer a single aligned byte load; it is two byte loads, a shift, and a truncate, and the 6-byte bucket no longer aligns cleanly to a machine word. On a hot lookup path that is measurable. Space or speed -- you rarely get both, and picking is the job ;-)

Right. Debt paid. On to the ring.

The one idea: a line that bites its own tail

A ring buffer is an array you pretend is circular. You keep two cursors: a tail where the producer writes the next item, and a head where the consumer reads the next item. Each advances forward; when a cursor walks off the end of the array it wraps back to the start. The array is finite, but because both cursors chase each other round and round, you can push and pop forever without ever moving or reallocating a single byte. That is the whole appeal -- a fixed slab of memory, reused endlessly, zero allocation on the hot path.

The classic beginner's implementation wraps the cursors themselves with a modulo: head = (head + 1) % capacity. It works, but it walks straight into an ugly ambiguity. When head == tail, is the buffer empty (consumer caught up to producer) or full (producer lapped the consumer)? The two states are indistinguishable, and the usual patch -- "waste one slot so full means (tail + 1) % capacity == head" -- is a wart you carry forever.

There is a cleaner trick, and it is the one serious ring buffers use. Do not wrap the cursors. Let head and tail be monotonically increasing counters that only ever go up -- 64-bit, so they will not realistically overflow this side of the heat death of the universe. Compute the actual array index by masking, only at the moment you touch the slot:

const index = cursor & (capacity - 1);   // capacity is a power of two, so & is exact modulo

Now the two states separate cleanly and for free. The number of items currently buffered is simply tail - head. Empty is head == tail (difference zero). Full is tail - head == capacity (difference equals the capacity). No wasted slot, no ambiguity, and -- this is the part that matters in a moment -- no read-modify-write on the cursors, just a plain increment. That last property is what makes the lock-free version possible. Having said that, let's lay it out in Zig.

Laying out the ring in Zig

I want this generic over the element type and the size, both fixed at compile time, so I write it as a function that returns a type -- the comptime-generics pattern from episode 14. The power-of-two requirement is not a suggestion; if it is violated the masking silently computes wrong indices, so I assert it at comptime and turn a runtime catastrophe into a compile error.

const std = @import("std");

fn RingBuffer(comptime T: type, comptime capacity: usize) type {
    // A power-of-two capacity turns "mod" into a single AND. Enforce it where it is cheapest:
    // at compile time, so a bad size never even builds.
    comptime std.debug.assert(capacity != 0 and (capacity & (capacity - 1)) == 0);
    return struct {
        const Self = @This();
        const mask = capacity - 1;

        buf: [capacity]T = undefined,   // the slab we reuse forever; no allocator involved
        head: usize = 0,                // read cursor  -- owned by the consumer
        tail: usize = 0,                // write cursor -- owned by the producer

        fn len(self: *const Self) usize {
            return self.tail - self.head; // works precisely BECAUSE the cursors never wrap
        }

        fn isEmpty(self: *const Self) bool {
            return self.head == self.tail;
        }

        fn isFull(self: *const Self) bool {
            return self.tail - self.head == capacity;
        }
    };
}

Notice there is no init, no allocator, no deinit. The buffer is a value you can put on the stack, embed in another struct, or drop into an arena -- it owns a fixed array and nothing else. This is the anti-tree: no nodes, no pointers, one contiguous block, and the memory management story is "there is none". That is exactly the property episode 112 promised we were heading toward.

Single-threaded first: push and pop

Before we get clever with threads, the single-threaded version. push refuses when full, pop returns an optional that is null when empty -- Zig's optionals doing the "nothing to hand you" job that a sentinel would do clumsily in C.

fn push(self: *Self, item: T) bool {
    if (self.isFull()) return false;        // caller decides: drop, block, or grow elsewhere
    self.buf[self.tail & mask] = item;      // mask ONLY here, at the point of access
    self.tail += 1;                         // plain increment -- the cursor never wraps
    return true;
}

fn pop(self: *Self) ?T {
    if (self.isEmpty()) return null;        // null == "the ring is empty right now"
    const item = self.buf[self.head & mask];
    self.head += 1;
    return item;
}

That is a perfectly good ring buffer for one thread -- a bounded FIFO queue with zero allocation, constant-time on both ends, cache-friendly because everything lives in one flat array. For a lot of uses (a fixed-size event queue inside a single event loop, say) this is all you need and you should not reach for anything fancier. But the reason I brought us here is the two-thread case, and that is where it gets interesting.

Going lock-free: the producer and consumer never meet

Here is the situation that makes ring buffers special. Suppose exactly one thread pushes (the producer) and exactly one thread pops (the consumer). This is the single-producer/single-consumer (SPSC) case, and it is the pattern behind audio callbacks, driver rings, and pipeline stages everywhere.

Look again at the cursor ownership. The producer is the only writer of tail. The consumer is the only writer of head. Each side only ever reads the other's cursor. There is no slot they both write. So if we can make the cursor updates and the slot access visible to the other thread in the right order, we never need a lock at all -- no mutex, no compare-and-swap loop, just plain loads and stores with the right memory ordering. THAT is the whole game, and it rests entirely on the atomics from episode 30.

The danger is not that two threads clobber the same variable -- they do not. The danger is reordering. Modern CPUs and compilers reorder memory operations freely as long as single-threaded behaviour is preserved. The producer writes the item into the slot and then bumps tail. But nothing stops a weakly-ordered CPU (ARM, POWER) from letting the consumer see the bumped tail before the slot write lands -- at which point the consumer reads a slot the producer has not actually filled yet. Garbage, intermittently, only on some hardware, only under load. The worst kind of bug.

The fix is a release/acquire pair, exactly the tool episode 30 introduced. When the producer stores tail with .release, every write it did before that store (the slot write) is guaranteed visible to any thread that reads tail with .acquire. The release "publishes" everything before it; the matching acquire "receives" it. Wrap the cursors in std.atomic.Value and pair the orderings:

fn RingBuffer(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: std.atomic.Value(usize) = std.atomic.Value(usize).init(0), // consumer writes
        tail: std.atomic.Value(usize) = std.atomic.Value(usize).init(0), // producer writes

        // PRODUCER thread only.
        fn push(self: *Self, item: T) bool {
            const tail = self.tail.load(.monotonic);  // we are tail's only writer -- no sync needed to read our own
            const head = self.head.load(.acquire);    // acquire: see the consumer's latest freeing
            if (tail -% head == capacity) return false; // full
            self.buf[tail & mask] = item;             // (1) fill the slot...
            self.tail.store(tail +% 1, .release);     // (2) ...release: publishes (1) to the consumer
            return true;
        }

        // CONSUMER thread only.
        fn pop(self: *Self) ?T {
            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
            if (head == tail) return null;            // empty
            const item = self.buf[head & mask];       // (3) read the slot BEFORE we free it
            self.head.store(head +% 1, .release);     // (4) release: tells producer the slot is free
            return item;
        }
    };
}

Read the orderings slowly, because they are the entire correctness argument. In push, the producer reads its own tail with .monotonic (it is the only writer, so it needs no synchronisation to trust it), reads the consumer's head with .acquire (so it sees slots the consumer has genuinely freed), writes the slot, then stores tail with .release so that the slot write is guaranteed visible before the new tail is. In pop, the mirror image: the .acquire load of tail pairs with the producer's .release store, guaranteeing that if the consumer sees tail advanced, it also sees the slot contents the producer wrote. The +% wrapping addition is deliberate -- on the vanishingly rare 64-bit overflow the difference tail -% head still comes out right in modular arithmetic, so even that edge is covered.

If you took only one thing from episode 30, let it be this: release publishes, acquire receives, and they only work in pairs. A lone release or a lone acquire buys you nothing. This little queue is the cleanest real example of the pairing I can show you.

Where Zig's type system earns its keep

The comptime capacity is not just tidiness. Because the size is known at compile time, mask is a compile-time constant and the & mask compiles to a single AND instruction with an immediate operand -- no load, no register for the mask, nothing. A runtime-sized ring would have to keep capacity - 1 in memory and load it every access. And the power-of-two check runs at comptime, so RingBuffer(u8, 100) -- 100 is not a power of two -- fails to compile rather than corrupting indices at 3am in production. That is the recurring Zig bargain: push the invariant into the compile step and the runtime is left small, flat, and hard to hold wrong.

The element type T being generic means the same code serves a ring of u64 timestamps, a ring of 64-byte audio frames, or a ring of pointers to work items -- with zero runtime dispatch, each specialisation monomorphised into its own tight machine code. And the ?T return from pop makes "empty" a value the caller cannot ignore: you have to unwrap the optional, so there is no path where you accidentally read a stale item because you forgot to check. Compare a C ring returning a raw T plus a separate bool *ok out-parameter that half the callers will forget to inspect.

If you would rather the caller be forced to reckon with fullness the way episode 112 forced them to reckon with error.TableFull, swap the bool for an error union:

const RingError = error{ Full, Empty };

fn pushOrError(self: *Self, item: T) RingError!void {
    if (!self.push(item)) return error.Full; // caller must try/catch -- no silent drop
}

fn popOrError(self: *Self) RingError!T {
    return self.pop() orelse error.Empty;
}

Same machinery, different contract. The bool/optional version says "failure is ordinary, handle it inline"; the error-union version says "failure is exceptional, propagate it". For a ring that legitimately fills and empties constantly I prefer the optional -- being empty is not an error, it is just Tuesday -- but when a full ring means something has gone wrong upstream, the error union makes that impossible to overlook. Zig lets you pick which story the types tell.

Testing a structure whose bugs hide in the timing

Single-threaded tests are table stakes -- fill it, drain it, check FIFO order, check the full and empty edges:

test "ring: fifo order, full and empty edges" {
    const Ring = RingBuffer(u32, 4);
    var r = Ring{};
    try std.testing.expect(r.push(10));
    try std.testing.expect(r.push(20));
    try std.testing.expect(r.push(30));
    try std.testing.expect(r.push(40));
    try std.testing.expect(!r.push(50));           // full: capacity is 4
    try std.testing.expectEqual(@as(?u32, 10), r.pop()); // FIFO: first in, first out
    try std.testing.expect(r.push(50));            // one slot freed -> one push fits
    try std.testing.expectEqual(@as(?u32, 20), r.pop());
    try std.testing.expectEqual(@as(?u32, 30), r.pop());
    try std.testing.expectEqual(@as(?u32, 40), r.pop());
    try std.testing.expectEqual(@as(?u32, 50), r.pop());
    try std.testing.expectEqual(@as(?u32, null), r.pop()); // empty
}

But the tests that matter for a lock-free structure are the concurrent ones, and they are genuinely hard: a memory-ordering bug does not fail every run, it fails one run in ten thousand on one CPU family. The honest strategy is a high-volume stress test with a checksum that cannot pass if a single item was lost, duplicated, or torn. Push the integers 0 .. N from one thread, sum everything the other thread pops, and compare against the closed-form N*(N-1)/2. If any item went missing or got read twice, the sum is wrong.

const StressRing = RingBuffer(u64, 1024);

fn produceInto(r: *StressRing, n: u64) void {
    var i: u64 = 0;
    while (i < n) {
        if (r.push(i)) i += 1 else std.atomic.spinLoopHint(); // ring full: back off, retry
    }
}

test "spsc: a million items cross the thread boundary intact" {
    var ring = StressRing{};
    const n: u64 = 1_000_000;
    const producer = try std.Thread.spawn(.{}, produceInto, .{ &ring, n });

    var received: u64 = 0;
    var sum: u64 = 0;
    while (received < n) {
        if (ring.pop()) |v| {
            sum += v;
            received += 1;
        } else {
            std.atomic.spinLoopHint(); // ring empty: let the producer get ahead
        }
    }
    producer.join();
    // If even one item were lost or double-counted, this sum could not match.
    try std.testing.expectEqual(n * (n - 1) / 2, sum);
}

The spinLoopHint is a small kindness to the CPU -- on a full or empty ring, instead of hammering the cache line in a tight loop, it emits a pause-style instruction that eases contention and saves power. Run this test under zig build test a few dozen times; run it on an ARM machine if you have one, because x86 is strongly ordered enough to hide a missing .release that ARM would expose. That asymmetry -- code that passes forever on your laptop and corrupts on a phone -- is exactly why the ordering annotations are not decoration.

Performance: the invisible tax called false sharing

The ring is lock-free, so it must be fast, right? Not automatically -- and the trap has a name: false sharing. Cache coherency works at the granularity of a cache line (64 bytes on most x86-64, 128 on some ARM). If head and tail happen to land in the same cache line -- and in our struct they sit adjacent, so they will -- then every time the producer writes tail, the hardware invalidates that whole line in the consumer's cache, and vice versa. The two threads are not sharing any data, but they are fighting over the same cache line, ping-ponging it between cores on every single operation. It can cost you an order of magnitude of throughput. Brutal, and invisible in the source -- the code is correct, it is just quietly slow.

The cure is to pad the two cursors onto separate cache lines so neither invalidates the other:

const cache_line = std.atomic.cache_line; // 64 on x86-64, 128 on aarch64 -- the platform's line size

fn PaddedRing(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 align(cache_line) = undefined,
        head: std.atomic.Value(usize) align(cache_line) = std.atomic.Value(usize).init(0),
        // The pad forces `tail` onto its OWN line, so producer and consumer never
        // invalidate each other's cursor cache line. Pure throughput, zero logic change.
        _pad: [cache_line - @sizeOf(std.atomic.Value(usize))]u8 = undefined,
        tail: std.atomic.Value(usize) align(cache_line) = std.atomic.Value(usize).init(0),
        // ... push/pop identical to before
    };
}

That is it -- a few dozen wasted bytes buy back the throughput the coherency protocol was quietly stealing. It is the kind of optimisation you would never guess from reading the algorithm; you find it with a profiler (episode 34) and a perf counter watching cache-line bounces. The lesson generalises: with lock-free code, correctness and speed are two entirely separate battles, and winning the first does not win the second. Beyond padding, the other free wins are already baked in -- the power-of-two mask, the monotonic cursors that avoid read-modify-write, and the flat array that streams through cache like water.

How this compares to C, Rust, and Go

In C, an SPSC ring is a struct with two _Atomic size_t cursors and a flat array, and the orderings are atomic_store_explicit(&tail, ..., memory_order_release) and friends from <stdatomic.h>. It works, and the kernel's kfifo and DPDK's rte_ring are exactly this at industrial scale -- but C gives you no help remembering to pad against false sharing, no compile-time power-of-two check, and nothing stops a maintainer from "cleaning up" a release into a relaxed because the tests still pass on their x86 desktop. The correctness lives entirely in a comment and the author's discipline.

In Rust, the borrow checker gets awkward precisely here, because a lock-free ring wants two threads holding references to the same struct -- which safe Rust forbids by default. The idiomatic answer is to split the ring into a Producer and a Consumer half at construction (crates like ringbuf and rtrb do exactly this), each half owning its cursor, so the type system proves single-producer/single-consumer at compile time rather than trusting a comment. That is genuinely lovely -- it is a stronger guarantee than Zig gives you out of the box. The cost is that you buy it with unsafe blocks and UnsafeCell under the hood, and the ergonomics of the split-handle API. Rust makes the invariant a type, at the price of more ceremony.

In Go, you would almost never hand-roll this -- you reach for a buffered channel (make(chan T, 1024)), which is a bounded concurrent queue, mutex-protected internally, and it is the right call 95% of the time. Go trades the last slice of lock-free throughput for an API so clean it is almost invisible, and the garbage collector means you never think about the backing memory. When you genuinely need the lock-free version (ultra-low-latency trading, audio), you drop to sync/atomic and write essentially the Zig code above, minus the comptime guarantees.

Our Zig version sits where it always does: the size and element type fixed in the type so the mask is a compile-time immediate, the power-of-two invariant caught at build time, the ?T making empty impossible to misread, and the memory orderings spelled out as explicit .acquire/.release arguments you cannot fat-finger into silence without it showing in the diff. Same structure across four languages -- but only in Zig is "this size must be a power of two" a fact the compiler enforces for free, and only here is the whole thing a stack value with no allocator in sight ;-)

Exercises

  1. Batch the pops. Our pop hands back one item at a time, and each call does an .acquire load and a .release store -- fine, but wasteful when the ring is deep and you want to drain it fast. Write a popSlice(self: *Self, out: []T) usize that copies as many available items as fit in out (up to tail - head), advancing head once at the end with a single .release store instead of one per item. Mind the wrap: the available items may straddle the end of the array, so you may need two @memcpy calls (one to the end of buf, one from the start). Return how many you copied. Then argue in a comment why doing the single release after both copies is still correct -- what does the producer see, and when?

  2. Prove the ordering matters. Take the SPSC ring and deliberately weaken the producer's tail store from .release to .monotonic. On x86-64 the stress test will very likely still pass (x86 is strongly ordered and hides the bug). Now cross-compile the test for aarch64 (episode 35's target triples) and run it under an emulator or on real ARM hardware, and see if you can make it fail -- a lost or torn item. Write up what you observed. If it stubbornly passes even on ARM, explain why a bug being possible under the memory model is not the same as it being observable on a given run, and why that makes lock-free bugs so vicious.

  3. A bounded blocking variant. The lock-free ring makes the caller spin when it is full or empty. Sometimes you want the producer to sleep until space appears rather than burn a core spinning. Build a BlockingRing that wraps the same array with a std.Thread.Mutex and two std.Thread.Condition variables (not_full, not_empty), where push waits on not_full and signals not_empty, and pop does the mirror. Then answer, in a paragraph: for a producer that outruns the consumer by a hair, which design -- lock-free-plus-spin or mutex-plus-condvar -- would you pick, and how does the answer change if the ring is almost always near-empty versus almost always near-full?

Where this is heading

Step back and notice what the ring buffer quietly refuses to do: it never calls the allocator on the hot path. It grabs one slab up front and then recycles slots forever, handing each one back the instant the consumer is done, so the same bytes serve a million items without a single alloc/free round-trip. That is not a coincidence of this one structure -- it is a strategy, and it is one of the most important ideas in high-performance systems programming: when you know the shape and size of what you are storing, you stop asking the general-purpose allocator for memory one object at a time and start managing a fixed reservoir yourself.

The ring solves it for a queue of homogeneous items in FIFO order. But the same instinct -- carve a block once, hand out fixed-size pieces on demand, take them back and reuse them with no per-object bookkeeping -- generalises far beyond queues. What if you have thousands of same-sized objects churning through create-and-destroy cycles (network connections, particles, game entities) and the general allocator's per-call overhead and fragmentation are killing you? What if you could pre-carve a slab into a free list of identically-sized cells and make allocation a single pointer pop, deallocation a single pointer push, both O(1), both allocation-free at the OS level? We spent this episode recycling slots in a circle. Next we start recycling memory itself -- reaching back into episode 7's allocators and episode 26's custom allocator and asking how the fastest allocators in the world actually carve their memory. The hot path has no room for malloc, and we are about to find out why ;-)

Bedankt en tot de volgende keer!

@scipio

stem stemsocial steemstem zig programming
0
0
0.000
0 comments