Recipe: An Atomic Work Index

The problem

Static chunking (one slice piece per thread) balances load only when every item costs the same. If item 7 takes a hundred times longer than item 8, the thread that owns item 7’s chunk finishes last while the others sit idle. You want threads to pull the next job when they are free, like workers taking tickets from a dispenser.

A mutex around a next_job counter works, but the counter is the entire critical section. Atomics do the same job without a lock.

The plan

1. Share two atomics: next, the index of the next unclaimed job, and total, the running result.
2. Each worker loops: claim an index with fetchAdd(1, .monotonic), stop when it is past the end, otherwise process the job and fold the result into total with another fetchAdd.
3. Spawn the workers, join them, read the total.

const std = @import("std");

const jobs = blk: {
    var j: [100]u64 = undefined;
    for (&j, 1..) |*x, i| x.* = i;
    break :blk j;
};

fn worker(next: *std.atomic.Value(usize), total: *std.atomic.Value(u64)) void {
    while (true) {
        // fetchAdd hands out each index exactly once, no lock involved.
        // Two threads can race here and still never get the same job.
        const i = next.fetchAdd(1, .monotonic);
        if (i >= jobs.len) return;

        const result = jobs[i] * jobs[i]; // the "work"
        _ = total.fetchAdd(result, .monotonic);
    }
}

pub fn main(init: std.process.Init) !void {
    var buf: [256]u8 = undefined;
    var file_writer = std.Io.File.stdout().writerStreaming(init.io, &buf);
    const out = &file_writer.interface;

    var next = std.atomic.Value(usize).init(0);
    var total = std.atomic.Value(u64).init(0);

    var threads: [4]std.Thread = undefined;
    for (&threads) |*t| {
        t.* = try std.Thread.spawn(.{}, worker, .{ &next, &total });
    }
    for (threads) |t| t.join();

    // Threads finished in some order, but every job ran exactly once, so
    // the sum is the same on every run.
    try out.print("sum of squares 1..100: {d}\n", .{total.load(.monotonic)});

    try out.flush();
}

Why fetchAdd cannot double-serve a job

fetchAdd is a single indivisible read-modify-write: it returns the old value and stores the incremented one, and no other thread can slip in between. Two threads racing on the same counter get two different indices, always. That property, not speed, is the reason to use an atomic here; the lock-free part is a bonus.

Both atomics use .monotonic ordering because each one is independent: no thread reads total until after join, and join already provides the visibility guarantee. The moment one atomic is supposed to publish writes to other memory, ordering gets subtle; keep counters independent and the simplest ordering stays correct.

When threads out-claim the work

Every worker exits by claiming an index past the end. With 4 threads, up to 4 claims overshoot; the counter ends beyond jobs.len. That is harmless and normal. Do not reuse the counter’s final value as “jobs done”; count completions separately if you need the number.

Variations

• Batch claiming: fetchAdd(16, ...) hands out sixteen jobs per claim, cutting contention on the counter when jobs are tiny.
• Results per job: when each job produces data rather than a number to fold, write to results[i]; index ownership makes the slot private, so the write needs no lock.
• Compare with chunking: the parallel sum recipe is the static version; prefer it when per-item cost is uniform, since it touches the shared counter zero times.