Zig Lock-Free Patterns

A lock-free pattern is a pattern where threads share data without holding a mutex. Progress comes from atomic operations that retry until they succeed.

One compare-and-swap increment

The loop reads 10 and swaps in 11. With no other thread running, the first try succeeds.

const std = @import("std");
fn casInc(v: *std.atomic.Value(i32)) void {
    var cur = v.load(.acquire);
    while (v.cmpxchgStrong(cur, cur + 1, .acq_rel, .acquire)) |seen| {
        cur = seen;
    }
}
pub fn main() !void {
    var v = std.atomic.Value(i32).init(10);
    casInc(&v);
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{v.load(.seq_cst)});
}

Four threads, one counter

Each thread increments twenty-five times through the retry loop. The total is always 100, because every increment either lands or retries.

const std = @import("std");
fn casInc(v: *std.atomic.Value(i32)) void {
    var cur = v.load(.acquire);
    while (v.cmpxchgStrong(cur, cur + 1, .acq_rel, .acquire)) |seen| {
        cur = seen;
    }
}
const Context = struct {
    counter: std.atomic.Value(i32) = std.atomic.Value(i32).init(0),
    fn inc(ctx: *@This()) void {
        var k: usize = 0;
        while (k < 25) : (k += 1) {
            casInc(&ctx.counter);
        }
    }
};
pub fn main() !void {
    var ctx = Context{};
    var threads: [4]std.Thread = undefined;
    for (&threads) |*t| {
        t.* = try std.Thread.spawn(.{}, Context.inc, .{&ctx});
    }
    for (threads) |t| {
        t.join();
    }
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{ctx.counter.load(.seq_cst)});
}

Exactly one thread claims the flag

Four threads each try to flip one flag from false to true. Only the first swap succeeds, so the count of winners is always 1.

const std = @import("std");
const Context = struct {
    flag: std.atomic.Value(bool) = std.atomic.Value(bool).init(false),
    slots: [4]i32 = .{ 0, 0, 0, 0 },
    fn claim(ctx: *@This(), i: usize) void {
        if (ctx.flag.cmpxchgStrong(false, true, .acq_rel, .acquire) == null) {
            ctx.slots[i] = 1;
        } else {
            ctx.slots[i] = 0;
        }
    }
};
pub fn main() !void {
    var ctx = Context{};
    var threads: [4]std.Thread = undefined;
    var i: usize = 0;
    while (i < 4) : (i += 1) {
        threads[i] = try std.Thread.spawn(.{}, Context.claim, .{ &ctx, i });
    }
    for (threads) |t| {
        t.join();
    }
    var winners: i32 = 0;
    for (ctx.slots) |s| {
        winners += s;
    }
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{winners});
}

Example

const std = @import("std");
fn casAdd(v: *std.atomic.Value(i64), amount: i64) void {
    var cur = v.load(.acquire);
    while (v.cmpxchgStrong(cur, cur + amount, .acq_rel, .acquire)) |seen| {
        cur = seen;
    }
}
const Context = struct {
    total: std.atomic.Value(i64) = std.atomic.Value(i64).init(0),
    fn partial(ctx: *@This(), k: i64) void {
        var sum: i64 = 0;
        var n: i64 = k * 25 + 1;
        while (n <= k * 25 + 25) : (n += 1) {
            sum += n;
        }
        casAdd(&ctx.total, sum);
    }
};
pub fn main() !void {
    var ctx = Context{};
    var threads: [4]std.Thread = undefined;
    var i: i64 = 0;
    while (i < 4) : (i += 1) {
        threads[@intCast(i)] = try std.Thread.spawn(.{}, Context.partial, .{ &ctx, i });
    }
    for (threads) |t| {
        t.join();
    }
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{ctx.total.load(.seq_cst)});
}

Key points

Lock-free: a lock-free pattern is a pattern where no thread ever waits on a mutex.
Compare-and-swap: a compare-and-swap is an atomic step that changes a value only when it still holds an expected value.
Retry loop: a retry loop is a loop that reads the current value, tries the swap, and tries again with the fresh value when the swap fails.
A failed swap returns the value another thread stored, so the retry never works from stale data.
A shared counter built this way always ends at the same total, no matter how threads interleave.
Lock-free code still needs a join before the main thread reads the final result.
Use this pattern for small shared state like counters and flags, not for large structures.

Each thread sums its own block of twenty-five numbers, then adds its partial sum with a compare-and-swap loop. The four blocks cover 1 to 100, so the shared total is always 5050. The main thread joins all four threads before printing.

Try it Yourself

Edit the code, then press Run.

Running is simulated

const std = @import("std");
fn casAdd(v: *std.atomic.Value(i64), amount: i64) void {
    var cur = v.load(.acquire);
    while (v.cmpxchgStrong(cur, cur + amount, .acq_rel, .acquire)) |seen| {
        cur = seen;
    }
}
const Context = struct {
    total: std.atomic.Value(i64) = std.atomic.Value(i64).init(0),
    fn partial(ctx: *@This(), k: i64) void {
        var sum: i64 = 0;
        var n: i64 = k * 25 + 1;
        while (n <= k * 25 + 25) : (n += 1) {
            sum += n;
        }
        casAdd(&ctx.total, sum);
    }
};
pub fn main() !void {
    var ctx = Context{};
    var threads: [4]std.Thread = undefined;
    var i: i64 = 0;
    while (i < 4) : (i += 1) {
        threads[@intCast(i)] = try std.Thread.spawn(.{}, Context.partial, .{ &ctx, i });
    }
    for (threads) |t| {
        t.join();
    }
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{ctx.total.load(.seq_cst)});
}

Exercise

What does a failed compare-and-swap return?

The new value. The value another thread stored. Zero. Nothing at all.