writing

My lock-free queue lost on throughput. It still won.

An SPSC ring buffer with acquire/release ordering and cache-line padding: 1.7× slower than a mutex queue on raw throughput, but a 3.7× faster median round trip and a 20× better p99. Why both results are correct, and what that means for trading systems.

6 min readShivanshu Pathak

"Lock-free is faster" is the kind of statement that gets you into trouble in an interview. Faster at what? I wrote a single-producer/single-consumer (SPSC) ring buffer, benchmarked it against a plain std::mutex + std::queue, and got a result that looks wrong at first glance.

The queue

template <class T, size_t Cap>
class Spsc {
  alignas(kLine) std::atomic<size_t> head_{0};  // written only by the consumer
  alignas(kLine) size_t cached_tail_ = 0;       // consumer's private copy of tail
  alignas(kLine) std::atomic<size_t> tail_{0};  // written only by the producer
  alignas(kLine) size_t cached_head_ = 0;       // producer's private copy of head
  alignas(kLine) T buf_[Cap];
 public:
  bool push(const T& v) {
    const size_t t = tail_.load(std::memory_order_relaxed);
    if (t - cached_head_ == Cap) {
      cached_head_ = head_.load(std::memory_order_acquire);
      if (t - cached_head_ == Cap) return false;   // full
    }
    buf_[t & (Cap - 1)] = v;
    tail_.store(t + 1, std::memory_order_release); // publish the slot
    return true;
  }
  bool pop(T& out) {
    const size_t h = head_.load(std::memory_order_relaxed);
    if (h == cached_tail_) {
      cached_tail_ = tail_.load(std::memory_order_acquire);
      if (h == cached_tail_) return false;          // empty
    }
    out = buf_[h & (Cap - 1)];
    head_.store(h + 1, std::memory_order_release);  // free the slot
    return true;
  }
};

Why each memory order is enough

  • Loading your own index is relaxed. Only the producer writes tail_ and only the consumer writes head_. A thread always sees its own writes, so no ordering is needed.
  • Publishing is a release store. The producer writes buf_[t] and then stores tail_ = t + 1 with release. That guarantees the element write becomes visible no later than the new tail.
  • Observing is an acquire load. When the consumer acquire-loads tail_ and sees t + 1, it synchronises with the release store, so the read of buf_[t] is guaranteed to see the producer's write. That is the happens-before edge the whole queue rests on.
  • The same pairing runs in reverse for head_. It tells the producer that a slot has been fully read and can be overwritten.

seq_cst would also be correct, but on most architectures it costs extra fences for a guarantee (a single total order across all threads) that two-party communication doesn't need.

Two details that matter for performance

Cached indices. The producer only re-reads the consumer's head_ when its cached copy says the queue might be full, and the consumer does the same for tail_. Without that, every push and pop would touch the other thread's cache line.

Padding to the real line size. alignas(kLine) keeps the producer's and consumer's fields on separate cache lines. On Apple M1 that is 128 bytes (sysctl hw.cachelinesize), not the 64 bytes most x86 code assumes. Getting this wrong brings back false sharing.

How much does false sharing cost? Two threads each increment their own atomic counter:

Layoutns / increment
Both counters in one 16-byte struct (same line)3.5 (one run: 15.2)
Each counter on its own 128-byte line2.5

That's a steady ~1.4× penalty, and once 6×. The spread depends on how macOS happens to schedule the two threads across performance and efficiency cores, which I can't pin.

The results

Apple M1 Pro, macOS, Apple clang 21, -O2, median of 5 runs. Correctness is checked by summing every transferred value, and the queue was run under ThreadSanitizer with no reports.

Throughput (one producer and one consumer, both spinning):

QueueM msgs / s
SPSC ring buffer16.5 – 17.5
std::mutex + std::queue27.6

Round-trip latency (A pushes, B echoes on a second queue, A waits; 1M samples):

Queuep50p99p99.9
SPSC ring buffer125 ns1.0 µs1.2 µs
std::mutex + std::queue458 ns20.3 µs46.5 µs

Why the mutex wins on throughput

When both sides run flat out, the mutex queue accidentally batches. While the consumer is blocked on the lock, the producer pushes many items, and the consumer later drains them in a burst with the cache line already local.

The SPSC queue does the opposite. It keeps the queue nearly empty, so almost every pop finds cached_tail_ stale and has to pull tail_ across the interconnect. Each message pays a cache-line transfer.

The fix, if throughput were the goal, is explicit batching: publish tail_ every N items, or pop several items per acquire. That's a good next experiment.

Why the lock-free queue is still the right choice

A trading system almost never wants maximum throughput at the cost of latency. It wants the next message processed as soon as possible, every time:

  • The median round trip is 3.7× faster, because there's no lock and no kernel involvement on contention.
  • The p99 is 20× better. A contended mutex can put a thread to sleep, and a sleeping thread is woken by the OS on the OS's schedule. That is exactly the tail that loses races in a market.

So both results are correct. The lesson is to decide what you are optimising before you pick the data structure, and to measure the percentile you actually care about.

Reproduce it

The full benchmark, including the ThreadSanitizer mode, is one file: spsc_bench.cpp.

clang++ -std=c++20 -O2 -o spsc spsc_bench.cpp && ./spsc
clang++ -std=c++20 -O1 -g -fsanitize=thread -o spsc_tsan spsc_bench.cpp && ./spsc_tsan check