Shard Your Locks in Zig: Benchmarking Four Cache Designs

A few days ago I read a post that builds the same in-memory cache six times in Go and measures each version under different loads. The result that stayed with me was that the design most of us write first, one mutex around one map, gets slower when you add cores. I wanted to see what happens in Zig, so I wrote the same cache four times with the Standard Library only and measured each version with 1, 2, 4 and 8 threads under four workloads. The short version is that the single mutex gets slower with more threads in Zig too, the read-write lock helps less than you expect and sharding the lock is the design that scales.

The contenders Link to heading

All four designs store string keys with string values in std.StringHashMap and offer the same get() and put() methods. They differ only in how they lock the map.

• mutex. One std.Io.Mutex around one hash map. Every operation, read or write, takes the same lock.
• rwlock. One std.Io.RwLock around one hash map. Readers take the lock in shared mode and many of them can hold it at the same time. A writer takes it in exclusive mode and waits for all readers to leave.
• sharded. The data is split into 64 hash maps and each one has its own mutex. The hash of the key picks the map, so two threads that work on different keys rarely touch the same lock.
• sharded-rw. The same 64 shards, each one with a read-write lock instead of a mutex, to see whether the two ideas add up.

The Go post also has a copy-on-write design, where readers never lock and every write copies the whole map and swaps a pointer. I left it out. In Go the Garbage Collector frees the old copy when the last reader is done with it. In Zig the writer has to know when that happens, which needs reference counting or hazard pointers and that is a post of its own.

If you have used Zig before 0.16 you may look for std.Thread.Mutex. It is gone. The locks live under std.Io now and every lock() and unlock() call takes an io parameter, because the lock asks the Io implementation to put the thread to sleep when it has to wait. The lock() method returns an error if the task is cancelled. I use lockUncancelable() in the benchmark, which cannot fail and keeps the hot path simple.

The code Link to heading

const std = @import("std");
const Io = std.Io;

const n_keys = 1_000_000;
const total_ops = 8_000_000;
const padded = true;
const use_defer = true;
// Must differ from the seed that StringHashMap uses, which is 0.
const shard_seed = 0x5a1d;

// A mutex that offers the read/write interface of a RwLock.
const MutexLock = struct {
    inner: Io.Mutex = .init,

    fn lockRead(l: *MutexLock, io: Io) void {
        l.inner.lockUncancelable(io);
    }
    fn unlockRead(l: *MutexLock, io: Io) void {
        l.inner.unlock(io);
    }
    fn lockWrite(l: *MutexLock, io: Io) void {
        l.inner.lockUncancelable(io);
    }
    fn unlockWrite(l: *MutexLock, io: Io) void {
        l.inner.unlock(io);
    }
};

const RwLock = struct {
    inner: Io.RwLock = .init,

    fn lockRead(l: *RwLock, io: Io) void {
        l.inner.lockSharedUncancelable(io);
    }
    fn unlockRead(l: *RwLock, io: Io) void {
        l.inner.unlockShared(io);
    }
    fn lockWrite(l: *RwLock, io: Io) void {
        l.inner.lockUncancelable(io);
    }
    fn unlockWrite(l: *RwLock, io: Io) void {
        l.inner.unlock(io);
    }
};

fn Cache(comptime Lock: type, comptime n_shards: usize) type {
    comptime std.debug.assert(std.math.isPowerOfTwo(n_shards));
    const shard_align = if (padded) std.atomic.cache_line else @alignOf(Lock);

    return struct {
        const Self = @This();

        const Shard = struct {
            lock: Lock align(shard_align) = .{},
            map: std.StringHashMap([]const u8),
        };

        shards: [n_shards]Shard,

        fn init(allocator: std.mem.Allocator) Self {
            var self: Self = undefined;
            for (&self.shards) |*s| {
                s.* = .{ .map = std.StringHashMap([]const u8).init(allocator) };
            }
            return self;
        }

        fn deinit(self: *Self) void {
            for (&self.shards) |*s| s.map.deinit();
        }

        fn shardOf(self: *Self, key: []const u8) *Shard {
            if (n_shards == 1) return &self.shards[0];
            const h = std.hash.Wyhash.hash(shard_seed, key);
            return &self.shards[h & (n_shards - 1)];
        }

        fn get(self: *Self, io: Io, key: []const u8) ?[]const u8 {
            const s = self.shardOf(key);
            s.lock.lockRead(io);
            if (use_defer) {
                defer s.lock.unlockRead(io);
                return s.map.get(key);
            } else {
                const v = s.map.get(key);
                s.lock.unlockRead(io);
                return v;
            }
        }

        fn put(self: *Self, io: Io, key: []const u8, value: []const u8) !void {
            const s = self.shardOf(key);
            s.lock.lockWrite(io);
            defer s.lock.unlockWrite(io);
            try s.map.put(key, value);
        }
    };
}

fn worker(cache: anytype, io: Io, keys: []const []const u8, ops: usize, read_pct: u8, seed: u64) void {
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var found: usize = 0;
    for (0..ops) |_| {
        const key = keys[rand.uintLessThan(usize, keys.len)];
        if (rand.uintLessThan(u8, 100) < read_pct) {
            if (cache.get(io, key)) |v| found += v.len;
        } else {
            cache.put(io, key, "updated") catch unreachable;
        }
    }
    std.mem.doNotOptimizeAway(found);
}

fn run(comptime Lock: type, comptime n_shards: usize, init: std.process.Init, keys: []const []const u8, read_pct: u8, n_threads: usize) !f64 {
    const io = init.io;
    var cache = Cache(Lock, n_shards).init(init.gpa);
    defer cache.deinit();
    for (keys) |key| try cache.put(io, key, "initial");

    const ops = total_ops / n_threads;
    var threads: [64]std.Thread = undefined;
    const start = Io.Clock.now(.awake, io);
    for (threads[0..n_threads], 0..) |*t, i| {
        t.* = try std.Thread.spawn(.{}, worker, .{ &cache, io, keys, ops, read_pct, @as(u64, i + 1) });
    }
    for (threads[0..n_threads]) |t| t.join();
    const end = Io.Clock.now(.awake, io);

    const ns: f64 = @floatFromInt(start.durationTo(end).nanoseconds);
    return ns / @as(f64, @floatFromInt(ops * n_threads));
}

pub fn main(init: std.process.Init) !void {
    var args = init.minimal.args.iterate();
    _ = args.next();
    const design = args.next() orelse return error.MissingDesign;
    const shards = try std.fmt.parseInt(usize, args.next() orelse "1", 10);
    const read_pct = try std.fmt.parseInt(u8, args.next() orelse "90", 10);
    const n_threads = try std.fmt.parseInt(usize, args.next() orelse "1", 10);
    if (n_threads == 0 or n_threads > 64) return error.BadThreadCount;

    const arena = init.arena.allocator();
    const keys = try arena.alloc([]const u8, n_keys);
    for (keys, 0..) |*key, i| key.* = try std.fmt.allocPrint(arena, "key-{d}", .{i});

    const ns_per_op = if (std.mem.eql(u8, design, "mutex")) switch (shards) {
        1 => try run(MutexLock, 1, init, keys, read_pct, n_threads),
        4 => try run(MutexLock, 4, init, keys, read_pct, n_threads),
        16 => try run(MutexLock, 16, init, keys, read_pct, n_threads),
        64 => try run(MutexLock, 64, init, keys, read_pct, n_threads),
        256 => try run(MutexLock, 256, init, keys, read_pct, n_threads),
        1024 => try run(MutexLock, 1024, init, keys, read_pct, n_threads),
        else => return error.BadShardCount,
    } else if (std.mem.eql(u8, design, "rwlock")) switch (shards) {
        1 => try run(RwLock, 1, init, keys, read_pct, n_threads),
        64 => try run(RwLock, 64, init, keys, read_pct, n_threads),
        else => return error.BadShardCount,
    } else return error.UnknownDesign;

    std.debug.print("{s},{d},{d},{d},{d:.1}\n", .{ design, shards, read_pct, n_threads, ns_per_op });
}

The two small structs at the top, MutexLock and RwLock, give the mutex and the read-write lock the same four methods. The MutexLock type implements lockRead() with a plain exclusive lock, because a mutex has no shared mode. This is what lets one Cache type cover all four designs. The Cache() function is generic over the lock type and the number of shards, so Cache(MutexLock, 1) is the mutex design and Cache(MutexLock, 64) is the sharded one. With one shard the shardOf() method skips the hash and returns the only shard there is. With more shards, it hashes the key with std.hash.Wyhash and a seed of its own and masks the result, which is why the shard count has to be a power of two. Each shard holds its lock and its map and the align(shard_align) on the lock pads every shard to a cache line, so that two shards never share one. I come back to this near the end of the post.

The worker() function is what every thread runs. It picks a random key, reads it with probability read_pct and overwrites it otherwise. The call to std.mem.doNotOptimizeAway() stops the compiler from removing the reads whose result is never used. The run() function fills the cache with every key, starts the threads with std.Thread.spawn(), waits for them with join() and divides the elapsed time by the total number of operations. Time comes from std.Io.Clock.now() with the .awake clock, which is monotonic.

How I measured Link to heading

The program creates one million keys up front, from key-0 to key-999999 and inserts all of them before the clock starts, so every read finds its key. The threads perform 8 million operations in total, split evenly among them, which means that a run with 8 threads does the same amount of work as a run with 1 thread. The read ratio is 100, 90, 50 or 10 percent and the thread count is 1, 2, 4 or 8. I built the program with -O fast and ran every combination 5 times. The numbers that follow are the medians and the variation between runs stayed within a few percent. The experiments ran on macOS on a Mac with an Apple M4 Pro CPU, which has 10 performance cores and 4 efficiency cores, so 8 threads fit on the performance cores. Everything is measured in-process. Putting an HTTP server in front of the cache would hide differences of a few nanoseconds behind the cost of a request.

Save the code as locks.zig and run one combination like this:

$ zig version
0.17.0
$ zig build-exe locks.zig -O fast
$ ./locks mutex 1 50 8
mutex,1,50,8,135.2
$ ./locks mutex 64 50 8
mutex,64,50,8,19.1

The arguments are the lock type, the number of shards, the read percentage and the number of threads and the output is one CSV line with the nanoseconds per operation at the end. A shell loop over the combinations and a short Python script with matplotlib produced the plots below.

The results Link to heading

The first plot shows how each design scales on the balanced workload, where half of the operations are reads. The y axis is the speedup over the run with one thread, so a design that scales perfectly would follow the dashed line.

The single mutex gets slower when you add threads. One thread needs 55 ns per operation and 8 threads need 135 ns, which is less than half of the single thread speed on eight times the cores. Every lock() and unlock() call is an atomic operation on the same memory location, so the cache line that holds the lock moves from core to core on every operation. When a thread finds the lock taken it asks the Operating System to put it to sleep and the thread that unlocks has to wake it up, which costs microseconds. The hash map is behind the lock as well, so a lookup that misses the cache keeps everyone else waiting. The read-write lock does the same and it is worse, because its bookkeeping is more expensive than that of a mutex. The sharded design goes the other way and reaches 3.6 times the speed of one thread with 8 threads. It does not reach 8 because the cache is one million keys and almost every lookup misses the CPU caches, so at some point the memory system is the limit and not the locks. The sharded design with read-write locks starts the same and falls behind the plain sharded design from four threads on.

The second plot shows the cost per operation with 8 threads for every workload. The y axis is logarithmic, because the slowest design is more than ten times slower than the fastest one.

The read-write lock wins only when there are no writes at all and only with 2 and 4 threads. With 2 threads and only readers it needs 38 ns per operation, which is better than one thread, but with 8 threads it needs 164 ns, which is worse than the mutex. Readers of a read-write lock still have to increment and decrement a shared counter atomically, so 8 readers fight over one cache line the same way 8 mutex holders do. As soon as there are writes the read-write lock is the slowest design everywhere. A writer has to wait for all readers to leave and readers that arrive while a writer is waiting have to queue behind it, so everyone waits for everyone. On the write-heavy workload it needs 255 ns per operation against 136 ns for the mutex. The two sharded designs are between 14 and 29 ns in every column. The sharded design with read-write locks is the fastest of all when there are no writes and loses to the plain sharded design as soon as there are some, for the same reason the single read-write lock loses to the single mutex.

The third plot shows what the number of shards does on the balanced workload with 8 threads. One shard is the mutex design.

Going from 1 to 64 shards makes the cache seven times faster. Going from 64 to 256 gives another 25 percent and 1024 shards are almost the same as 256. With 8 threads and 64 shards the chance that another thread is in your shard at the same time is about one in ten, which is what the step to 256 removes. After that the locks are no longer the problem and the time goes to the memory system. I use 64 in the post because it is where the curve bends and 64 maps are easy to reason about, but 256 is a fine default too. Each shard costs one cache line for the lock and the map header, which is 128 KB for 1024 shards, so you can afford many more shards than that. They do not help, because a lookup in a map with a few thousand entries behaves the same as a lookup in a map with a million entries once the map does not fit in the cache.

The plots show the shape of the results and the table below has the numbers behind them. There is one row per design and read ratio and one column per thread count. Every cell is the median of 5 runs in nanoseconds per operation, so lower is better. Read across a row to see what adding threads does to one design and down a column to compare the designs at the same thread count. The 8 threads column is what the second plot shows and the 50% rows are what the first plot shows, divided by their first cell.

The 1 thread column says that the sharded design is slower than the mutex when there is no contention at all, 66 ns against 53 ns. That is the price of hashing the key a second time to pick the shard. The hash map hashes the key again when it looks it up. You can compute the hash once and hand it to the map through a custom context, but I kept the code simple. The 2 threads column is where the mutex starts to lose. It gives up almost a third of its speed with the second thread alone, from 55 ns to 78 ns, which is the moment the lock starts to bounce between two cores. Down the 8 threads column the four rows of the mutex are within 6 ns of each other and the four rows of the sharded design within 1 ns. Once you hold the lock a read and a write cost about the same, so the read ratio makes no difference to either of them. The read ratio does change the numbers of the two designs with read-write locks. The single lock goes from 164 ns with no writes to 255 ns on the write-heavy workload and the sharded one from 14 ns with no writes to 29 ns on the balanced workload, because a read-write lock behaves differently from a mutex only while there are readers to overlap.

Hash seed, padding and defer Link to heading

With a seed of 0 the sharded cache is three times slower than the single mutex with one thread. My first version had that bug. The shardOf() method hashed the key with std.hash.Wyhash.hash(0, key) and used the low bits of the result to pick the shard. The StringHashMap type hashes its keys with the same function and the same seed and it uses the low bits of the hash to pick the slot in its table. So every key that landed in shard 5 had a hash that ended in the bits 000101 and inside the map of shard 5 only one slot in 64 could be the home of a key. Almost every key collided with another one and every lookup walked a long run of occupied slots. Changing the seed of the shard hash to any other value, which is what the shard_seed constant does, took the single thread cost from 147 ns to 68 ns and the 8 thread cost from 38 ns to 19 ns. If you shard a hash map, the function that picks the shard must not agree with the function that picks the slot.

The Shard struct is aligned to std.atomic.cache_line, which is 128 bytes for every aarch64 target, Apple Silicon included, so each shard gets its own cache line. Without the padding, a lock is 4 bytes and a map header is a few words, so several shards share a cache line and a thread that locks shard 5 invalidates the line of the thread that works on shard 6, even though they never touch the same data. This is called false sharing. On the balanced workload with 8 threads the padded version needs 19.5 ns per operation and the unpadded one 22.3 ns, so the padding is worth about 13 percent. The cost is 128 bytes per shard, which is 8 KB for 64 shards.

The Go post found that calling Unlock() by hand instead of with defer made the hot path about 8 percent faster, because defer in Go has a small runtime cost. The use_defer constant in the program switches get() between the two styles. In Zig there is no difference that I can measure, 18.6 ns against 18.7 ns with 8 threads, because defer in Zig is not a runtime mechanism. The compiler copies the deferred code to every exit of the scope and that is all. So use defer for every unlock() and do not think about it again.

What to actually use Link to heading

• Start with sharded mutexes. The design is 30 lines of code, it is the fastest or close to it under every workload and it keeps getting faster as you add threads.
• Use a single std.Io.Mutex when the data is small, when there is little contention or when the program has one or two threads. Measure before you shard, because with one thread the mutex is the fastest design.
• Use std.Io.RwLock only after measuring that reads dominate and that it is faster than the mutex. In my numbers it lost to the mutex everywhere except with two or four threads and no writes at all.
• Never share a plain StringHashMap between threads. Go crashes the program when it detects a concurrent map write. Zig does not detect anything and the map gets corrupted silently.

The Go post and this one agree on the ranking, which I did not expect. The runtimes are different, the locks are different and the hash maps are different, but a cache line that bounces between cores costs the same in both.

Happy coding in Zig!

Want to learn Zig? Look at my book Systems Programming with Zig.