Lock-Free Queues and Memory Ordering: An SPSC Ring Buffer Measured Against a Mutex

The reduction post ended with a rule: publishing data through a flag needs a release store on the flag and an acquire load of it. A single-producer single-consumer (SPSC) queue is that rule applied twice per message, and one of the few lock-free structures short enough to prove correct in a blog post. This post builds one with C11 <stdatomic.h>, argues why acquire/release is sufficient, and measures it against two pthread_mutex queues on an Apple-silicon laptop (Apple M1, hw.ncpu = 8).

The ring

The queue is a power-of-two array plus two counters. The producer owns tail (messages ever pushed), the consumer owns head (messages ever popped), and slot i & (CAP − 1) holds message i. The ring is empty when head == tail and full when tail − head == CAP; because the counters never reset, no slot is sacrificed to tell full from empty.

Layout matters as much as ordering. head and tail sit on separate 128-byte lines (sysctl hw.cachelinesize reports 128 here) so they do not false-share like the packed counters in the reduction post. Each side also caches the other side's counter and re-reads it only when its copy says full or empty, the textbook optimisation that the measurements below put in doubt.

The code

• Lock-free
• Mutex

• #include <stdatomic.h>
  #include <stdbool.h>
  #include <stddef.h>
  #include <stdint.h>
  
  #define LINE 128
  struct msg { uint64_t w[1]; };
  
  struct spsc {
      _Alignas(LINE) _Atomic size_t tail;   /* written only by the producer */
      _Alignas(LINE) size_t cached_head;    /* producer's private copy of head */
      _Alignas(LINE) _Atomic size_t head;   /* written only by the consumer */
      _Alignas(LINE) size_t cached_tail;    /* consumer's private copy of tail */
      _Alignas(LINE) size_t cap, mask;      /* read-only after init */
      struct msg *buf;
  };
  
  bool spsc_push(struct spsc *q, const struct msg *m)
  {
      size_t t = atomic_load_explicit(&q->tail, memory_order_relaxed);   /* own counter */
      if (t - q->cached_head == q->cap) {
          q->cached_head = atomic_load_explicit(&q->head, memory_order_acquire);
          if (t - q->cached_head == q->cap) return false;                /* full */
      }
      q->buf[t & q->mask] = *m;                                          /* plain store */
      atomic_store_explicit(&q->tail, t + 1, memory_order_release);      /* publish */
      return true;
  }
  
  bool spsc_pop(struct spsc *q, struct msg *m)
  {
      size_t h = atomic_load_explicit(&q->head, memory_order_relaxed);
      if (h == q->cached_tail) {
          q->cached_tail = atomic_load_explicit(&q->tail, memory_order_acquire);
          if (h == q->cached_tail) return false;                         /* empty */
      }
      *m = q->buf[h & q->mask];                                          /* plain load */
      atomic_store_explicit(&q->head, h + 1, memory_order_release);      /* free the slot */
      return true;
  }
  

• struct mq {
      pthread_mutex_t lock;
      pthread_cond_t not_empty, not_full;
      size_t head, tail, cap, mask;
      struct msg *buf;
  };
  
  bool mq_try_push(struct mq *q, const struct msg *m)        /* caller spins on false */
  {
      pthread_mutex_lock(&q->lock);
      bool ok = q->tail - q->head < q->cap;
      if (ok) { q->buf[q->tail & q->mask] = *m; q->tail++; }
      pthread_mutex_unlock(&q->lock);
      return ok;
  }
  
  void mq_push_wait(struct mq *q, const struct msg *m)       /* sleeps while full */
  {
      pthread_mutex_lock(&q->lock);
      while (q->tail - q->head == q->cap) pthread_cond_wait(&q->not_full, &q->lock);
      q->buf[q->tail & q->mask] = *m; q->tail++;
      pthread_cond_signal(&q->not_empty);
      pthread_mutex_unlock(&q->lock);
  }
  /* mq_try_pop and mq_pop_wait are the mirror images */
  

Loads of a thread's own counter are relaxed because a thread always sees its own latest write. Apple clang 21.0.0 at -O2 compiles the release stores to stlr and the acquire loads to ldapr, the ARMv8.3 load-acquire that is weaker than ldar but sufficient for release/acquire. There is no fence and no read-modify-write.

Why acquire/release is enough

Write $W_k$ for the producer's store of message $k$ into its slot, $R_k$ for the consumer's load of it, and $\stackrel{sb}{\to }$, $\stackrel{sw}{\to }$, $\stackrel{hb}{\to }$ for sequenced-before, synchronizes-with and happens-before. Two facts must hold for every $k$.

The consumer reads what was written. The consumer reaches $R_k$ only after an acquire load of tail returned some $v\ge k+1$. Only the producer writes tail, each write is a release store, and the one that wrote $v$ is sequenced after $W_k$. A release store read by an acquire load synchronizes with it, so

$$W_k\stackrel{sb}{\to }{\text{store}}_{\text{rel}}(\mathtt{\text{tail}},v)\stackrel{sw}{\to }{\text{load}}_{\text{acq}}(\mathtt{\text{tail}})\stackrel{sb}{\to }{R}_k⟹W_k\stackrel{hb}{\to }{R}_k.$$

If the consumer used its cached copy, the acquire load that filled the cache is still sequenced before $R_k$, and the chain is unchanged.

The producer does not overwrite a slot before it is read. Message $k+\text{CAP}$ reuses the slot of message $k$, and the producer writes it only after an acquire load of head returned at least $k+1$, which the consumer stored with release after $R_k$:

$$R_k\stackrel{sb}{\to }{\text{store}}_{\text{rel}}(\mathtt{\text{head}},k+1)\stackrel{sw}{\to }{\text{load}}_{\text{acq}}(\mathtt{\text{head}})\stackrel{sb}{\to }{W}_{k+\text{CAP}}⟹R_k\stackrel{hb}{\to }{W}_{k+\text{CAP}}.$$

So every pair of conflicting accesses to a slot is ordered, there is no data race on the buffer, and $R_k$ observes $W_k$. Nothing needs the single total order that memory_order_seq_cst would add.

What goes wrong with relaxed everywhere

Make every ordering memory_order_relaxed and the code still compiles and might even pass on x86, whose hardware keeps stores ordered with stores and loads with loads. AArch64 promises neither. The benchmark contains this variant (without the index cache) and checks every message; five runs of $2^{24}$ messages per capacity gave:

capacity	messages checked	wrong messages
8	83,886,080	89,476
64	83,886,080	139,547
1024	83,886,080	1,183

Each wrong message is its slot's content from a different lap: the store to tail became visible before the store to the slot, or the slot load was satisfied before the tail load, and the architecture allows both. Built with -fsanitize=thread, the relaxed variant is reported as a data race at the plain load in its pop; the acquire/release ring runs clean. A run with zero errors would have proved nothing.

Measurements

The harness pushes $2^{24}$ eight-byte messages through each lock-free queue ($2^{21}$ through the slower mutex queues) and the consumer checks every one. Both threads request the user-interactive QoS class, a run is timed from a start flag until both threads join, and everything is built with Apple clang 21.0.0, -O2 -std=c11. Each point is the median of seven interleaved runs. Two extra variants test the index cache: cached copies next to the published counters, and no cache at all. The mutex is the default kind (pthread_mutexattr_getpolicy_np reports PTHREAD_MUTEX_POLICY_FIRSTFIT_NP).

Small rings are where lock-free pays. With 8 slots the ring moves 23 million messages per second, against 2.1 million for the condition-variable queue and 0.5 million for the spinning mutex, whose every failed attempt takes the lock away from the thread it is waiting for: 55 failed pushes and 60 failed pops per delivered message.

Large rings close the gap. From 8192 slots up the spinning mutex delivers 24.5 to 25.7 million messages per second, level with the cached ring: the ring is rarely full or empty (under 0.15 failed attempts per message), and an uncontended lock costs about as much as the cache-line transfers any cross-core queue pays. The condition-variable queue levels off at 17 to 19 million.

The index cache lost. The variant without it was the fastest at every capacity, 45 to 48 million messages per second from 32 to 8192 slots against 29 to 38 million, and where the cached copies live made no measurable difference. The spin counters suggest a reason I have not confirmed with hardware counters: with the cache, the consumer drains a batch and then polls tail on an empty ring (1.6 to 11 failed pops per message from 128 to 8192 slots), each poll pulling the producer's line away before its next store. Without the cache, every pop reads tail anyway, so the consumer polls less (0.6 to 1.1 failed pops per message over the same range) and stays out of the producer's way. An optimisation that removes coherence traffic in one regime can add it in another; only a measurement on the target says which.

ABA, and why MPMC is a different problem

The SPSC ring has no ABA problem, though not because its counters never repeat. They are size_t values and do wrap, after about 585 years at a billion increments per second, and the ring keeps working across the wrap: each index has one writer, the unsigned difference tail - head stays between zero and the capacity, the power-of-two capacity divides $2^{64}$ so t & mask stays consistent, and a stale copy of the other side's index can only make the ring look fuller or emptier than it is, never hand out a slot early. ABA belongs to compare-and-swap designs: a thread reads pointer A, is delayed while A is popped, freed, reallocated and pushed again, and its CAS then succeeds on a stale next pointer. The repairs are a version counter beside the pointer, hazard pointers, or epoch-based reclamation.

A second producer breaks the ring's central fact, that tail has one writer. Producers must claim slots with a fetch_add or CAS, and "tail has advanced" no longer means "the slot is written", because a producer can be descheduled between claim and store. Bounded MPMC queues therefore publish per slot with a sequence number (Dmitry Vyukov's design, used in Rigtorp's MPMCQueue below). The contended read-modify-writes come back, and a producer stalled between claim and publish blocks the consumer of that slot, so the result is not lock-free in the strict sense.

When not to go lock-free

WARNING

Every lock-free variant here, and the first mutex variant, spins while the ring is full or empty. A spinning thread burns a whole core, and on an oversubscribed machine it can burn the time slice the other side needed. The condition-variable queue sleeps instead; unless a profile shows the queue itself is the bottleneck, that is the right default.

• The queue is not the bottleneck. At ten thousand messages per second, even the gap between the fastest and slowest queues above (21 ns and 1.9 µs per message) is 2 % of one core.
• The consumer has to sleep. A lock-free ring cannot wait. Adding a semaphore or futex-style wait puts system calls back on the slow path and reintroduces the lost-wake-up race the condition variable already solves.
• There is more than one producer or consumer. The proof relies on single writers; use a published MPMC design from a maintained library.
• The ordering cannot be tested. The relaxed variant fails only sometimes on ARM. Without ThreadSanitizer, a model checker or an argument like the one above, prefer the version whose correctness follows from the lock.

Further reading

• memory_order on cppreference: the definitions of sequenced-before, synchronizes-with and happens-before used above.
• Jeff Preshing, Acquire and Release Semantics and An Introduction to Lock-Free Programming.
• C/C++11 mappings to processors: which instructions each ordering becomes on AArch64, POWER and x86.
• Leslie Lamport, Specifying Concurrent Program Modules, ACM TOPLAS 1983, where the single-producer single-consumer ring appears with a correctness proof.
• Erik Rigtorp's SPSCQueue and MPMCQueue: C++ versions of the cached-index ring and the per-slot-sequence MPMC queue.
• ThreadSanitizer, which reports the race in the relaxed variant.