← Labsconcurrency-02Concurrency●●●○

SPSC ring buffer, three ways — memory orders, padding, cached indices

concurrency/02_spsc_queue.cppneeds: tools/bench.h, TSan build1 steps

0/1 steps

what this lab teaches

The single-producer single-consumer queue is the workhorse of low-latency systems: one thread pushes, one pops, no locks, no CAS. Three versions of the same queue move 50M items between two P-cores: naive seq_cst everywhere, head and tail adjacent (same cache line) padded acquire/release on the shared indices, each on its own line cached padded + each side keeps a private copy of the other's index and then the padded/cached queue on two SMT siblings of ONE core. The TSan build proves the acquire/release version is race-free.

evidence to leave with

naive 148 ns/item; padded 18-42; cached 29-34 (stable); siblings 2.4 ns; TSan 0 warnings

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ cd concurrency && ./build.sh

produces bin/02_spsc_queue (CAP 4096), bin/02_spsc_queue.big (CAP 65536), bin/02_spsc_queue.tsan

walk it, one step at a time

run this

$ ./bin/02_spsc_queue

what it printed on the machine that wrote this lab

producer on CPU 2, consumer on CPU 4, 50000000 items, capacity 4096
naive            148.2 ns/item     6.7 M items/s
padded            17.7 ns/item    56.4 M items/s
cached            33.6 ns/item    29.8 M items/s
-- same physical core, two SMT threads (CPU 2 and 3): --
cached/SMT         2.6 ns/item   383.8 M items/s

run this

$ ./bin/02_spsc_queue        (second run, same binary)

what it printed on the machine that wrote this lab

padded            42.2 ns/item    23.7 M items/s
cached            30.2 ns/item    33.1 M items/s
cached/SMT         2.4 ns/item   413.1 M items/s

run this

$ ./bin/02_spsc_queue.big    (capacity 65536)

what it printed on the machine that wrote this lab

padded            22.8 ns/item    43.9 M items/s
cached            28.9 ns/item    34.6 M items/s
cached/SMT         2.4 ns/item   420.0 M items/s

run this

$ ./bin/02_spsc_queue.tsan 2>&1 | grep -c 'WARNING: ThreadSanitizer'

what it printed on the machine that wrote this lab

how to read it

- naive: 148 ns/item. Every push does a seq_cst store (xchg: a full fence and a store-buffer drain) AND head/tail share one line, so every operation on either side pulls the line across cores (false sharing, cache lab 04). Both mistakes, 5-8x. - padded vs cached: 17.7 / 42.2 / 22.8 ns for padded across three runs, 33.6 / 30.2 / 28.9 for cached. The honest reading: on this laptop they are within each other's run-to-run variance; the cached variant is more STABLE (its worst run is 34 ns; padded's is 42 ns), the padded variant has the best single run. The cached-index trick reduces reads of the other side's line from one-per-operation to one-per- batch; it pays most when the producer and consumer run at similar speed with the queue partly full, which is workload-dependent. Do not copy the "cached is 2x faster" claim from a blog; measure YOUR producer and consumer. - SMT siblings: 2.4-2.6 ns/item. The two threads share one L1, so the lines never leave the core: 10-15x faster than across cores. In real systems this is a design choice (co-locate the hottest pair on one core's siblings) with a cost (they share execution units). THE ORDERS, AND WHY (see QueuePadded): producer: t = tail.load(relaxed) // my own index: nobody else writes it if (t - head.load(acquire) == CAP) full // acquire: see the consumer's slot reads as done buf[t & mask] = v tail.store(t + 1, release) // release: the slot write happens-before any acquire of tail consumer: mirror image. The release/acquire pair on the index that PUBLISHES is the only synchronization needed; seq_cst adds a fence for nothing (x86: xchg vs mov; lab 03). relaxed on your own index is safe because it has a single writer. TSan agrees: 0 warnings.

what breaks with two producers

both read the same tail and write the same slot. You need an atomic claim (fetch_add/CAS on tail) plus a per-slot sequence number so the consumer can tell "claimed" from "filled" (the bounded MPMC design), or one SPSC queue per producer. Nothing in this file is safe for that; its speed comes precisely from the 1:1 contract.

the rules

Q1. Never let the producer's and consumer's written variables share a line. alignas(64) on head and tail, and keep the buffer off those lines too. Q2. release on the publishing store, acquire on the reading load, relaxed on your own index. seq_cst is a fence you did not need. Q3. Measure with YOUR item size and speed ratio; the classic micro-optimizations (cached indices, batching) are workload-dependent. Q4. Prove race-freedom with TSan, not by reasoning alone.

take it further

1. Change QueuePadded's release/acquire to relaxed: TSan reports a race on buf[] (the slot write is no longer ordered before the index). Run it without TSan: it will probably still "work". That is R1 of lab 01. 2. Make the item 64 bytes (a struct): the buffer traffic now dominates; compare padded vs cached again. 3. Pin producer and consumer to an E-core pair (8 and 9): slower cores, and no SMT: the "same core" row disappears. ============================================================

read the source · concurrency/02_spsc_queue.cpp

#include "../tools/bench.h"
#include <atomic>
#include <thread>
#include <cstring>
#ifndef CAP_LOG2
#define CAP_LOG2 12
#endif
static const size_t CAP = 1u << CAP_LOG2;                 /* slots, power of two (4096 by default) */
static const uint64_t N = 50000000;                       /* items to transfer */

/* A: "obvious" version: seq_cst everywhere, head and tail adjacent (same cache line). */
struct QueueNaive {
    std::atomic<size_t> head{0}, tail{0}; uint64_t buf[CAP];
    bool push(uint64_t v) { size_t t = tail.load(); if (t - head.load() == CAP) return false; buf[t & (CAP - 1)] = v; tail.store(t + 1); return true; }
    bool pop(uint64_t &v) { size_t h = head.load(); if (tail.load() == h) return false; v = buf[h & (CAP - 1)]; head.store(h + 1); return true; }
};
/* B: acquire/release on the shared indices, each index on its own cache line. */
struct QueuePadded {
    alignas(64) std::atomic<size_t> head{0};
    alignas(64) std::atomic<size_t> tail{0};
    alignas(64) uint64_t buf[CAP];
    bool push(uint64_t v) { size_t t = tail.load(std::memory_order_relaxed); if (t - head.load(std::memory_order_acquire) == CAP) return false; buf[t & (CAP - 1)] = v; tail.store(t + 1, std::memory_order_release); return true; }
    bool pop(uint64_t &v) { size_t h = head.load(std::memory_order_relaxed); if (tail.load(std::memory_order_acquire) == h) return false; v = buf[h & (CAP - 1)]; head.store(h + 1, std::memory_order_release); return true; }
};
/* C: B + each side keeps a private copy of the OTHER index and only re-reads the shared line when it must. */
struct QueueCached {
    alignas(64) std::atomic<size_t> head{0}; size_t tail_cache{0};    /* consumer's line: head + its copy of tail */
    alignas(64) std::atomic<size_t> tail{0}; size_t head_cache{0};    /* producer's line: tail + its copy of head */
    alignas(64) uint64_t buf[CAP];
    bool push(uint64_t v) {
        size_t t = tail.load(std::memory_order_relaxed);
        if (t - head_cache == CAP) { head_cache = head.load(std::memory_order_acquire); if (t - head_cache == CAP) return false; }
        buf[t & (CAP - 1)] = v; tail.store(t + 1, std::memory_order_release); return true;
    }
    bool pop(uint64_t &v) {
        size_t h = head.load(std::memory_order_relaxed);
        if (tail_cache == h) { tail_cache = tail.load(std::memory_order_acquire); if (tail_cache == h) return false; }
        v = buf[h & (CAP - 1)]; head.store(h + 1, std::memory_order_release); return true;
    }
};
template <class Q> static double run(const char *name, int cpu_p, int cpu_c) {
    Q *q = new Q();
    uint64_t t0 = bench_ns();
    std::thread prod([&] { bench_pin(cpu_p); for (uint64_t i = 0; i < N; i++) while (!q->push(i)) {} });
    std::thread cons([&] { bench_pin(cpu_c); uint64_t v, sum = 0; for (uint64_t i = 0; i < N; i++) { while (!q->pop(v)) {} sum += v; } BENCH_KEEP(sum); if (sum != N * (N - 1) / 2) printf("  !! %s: checksum mismatch\n", name); });
    prod.join(); cons.join();
    double ns = (double)(bench_ns() - t0) / (double)N;
    printf("%-14s %7.1f ns/item  %6.1f M items/s\n", name, ns, 1000.0 / ns);
    delete q; return ns;
}
int main(int argc, char **argv) {
    int cp = argc > 1 ? atoi(argv[1]) : 2, cc = argc > 2 ? atoi(argv[2]) : 4;   /* two different physical P-cores */
    printf("producer on CPU %d, consumer on CPU %d, %llu items, capacity %zu\n", cp, cc, (unsigned long long)N, CAP);
    run<QueueNaive>("naive", cp, cc); run<QueuePadded>("padded", cp, cc); run<QueueCached>("cached", cp, cc);
    printf("-- same physical core, two SMT threads (CPU %d and %d): --\n", cp, cp + 1);
    run<QueueCached>("cached/SMT", cp, cp + 1);
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.