Vyukov MPSC Queue (C++20)

The Vyukov intrusive MPSC (Multi-Producer Single-Consumer) queue in C++20, with a formal memory-ordering proof, ThreadSanitizer litmus tests, and benchmarks covering peak throughput, sustained multi-producer contention with latency histograms, a real end-to-end tick-to-trade pipeline routed through the queue, and a head-to-head comparison against a mutex, a spinlock, and boost::lockfree::queue.

In 30 seconds

• Proof: seven claims (proof/memory_model.md), including why the exchange needs acquire: without it, a producer's link can be overwritten by the previous producer's next = nullptr, silently losing nodes.
• Measured, not asserted: making every op seq_cst turns one locked XCHG per push into three. Push cost goes from 8.8 ns to 20.6 ns (2.3x), and pop is unchanged (bench/bench_ordering.cpp).
• Honest guarantees: pushes are wait-free on x86 and ARM-LSE hardware. The queue as a whole is not lock-free and not linearizable, because a producer preempted mid-push hides later nodes. Most write-ups get this wrong, and so did this repo's first version.
• A contract bug, found and pinned: the documented rule for reusing a popped node was wrong, and following it produced a self-looping node. tests/test_lifetime.cpp shows the failure and checks the correct rule under TSan and ASan.
• CI on x86-64 and AArch64: a weakly ordered CPU can expose a missing acquire or release that x86 hides.

---

The queue

#include "mpsc/queue.hpp"
using namespace mpsc;

struct MyNode : MpscNode { int value; };

MpscQueue<MyNode> q;

// Any thread — wait-free on x86 / ARM LSE:
MyNode n{42};
q.push(&n);

// Consumer thread only — never blocks, but nullptr means "nothing reachable
// right now" (empty, or a producer mid-push), not "empty":
MyNode* p = q.pop();

Nodes must inherit MpscNode. The queue is intrusive (no internal allocation). Callers manage node lifetime.

---

Algorithm

head_ ──► [stub] ──► [node₁] ──► [node₂] ──► ... ──► [nodeₙ]
                                                          ▲
                                                       tail_

push(node) — any thread, wait-free:

node->next.store(nullptr,  memory_order_relaxed);        // (P1)
prev = tail_.exchange(node, memory_order_acq_rel);       // (P2)
prev->next.store(node,     memory_order_release);        // (P3)

pop() — consumer thread only:

head = head_.load(memory_order_relaxed);
next = head->next.load(memory_order_acquire);            // (C1)
if (!next) return nullptr;   // empty or incomplete push window
head_.store(next, memory_order_relaxed);
return static_cast<T*>(next);

The incomplete push window — between (P2) and (P3) — is the only subtlety. During this window, tail_ points to node but the list traversal cannot reach it yet. The consumer returns nullptr and retries. This is documented behaviour; callers must handle it.

---

Memory ordering proof (summary)

The full proof is in proof/memory_model.md, with citations to the C++20 standard and Sewell et al.'s x86-TSO model. Key claims:

Claim 1 — Payload visibility: If pop() returns p, all writes sequenced-before push(p) are visible.

Proof sketch:

user writes to p  →(seq-before)→  (P3) release-store
(P3) release-store  →(sync-with)→  (C1) acquire-load
(C1) acquire-load   →(seq-before)→  user reads from p

By transitivity: user writes happen-before user reads. ∎

Claim 2 — acq_rel on tail_.exchange is necessary and sufficient: the previous producer's release and our acquire make its prev->next = nullptr happen-before our prev->next = node. By write-write coherence our link then wins. Without that edge, the null could land last and drop our node. No total order over all atomics is needed, so seq_cst buys nothing. Its cost is measured below.

Claim 3 — No ABA: the consumer uses no CAS — only an unconditional store to head_. Producers use only unconditional exchange on tail_. ABA requires a compare-and-swap that can match a re-used pointer; without CAS there is no ABA.

Claim 4 — Per-producer FIFO: list order equals the modification order of tail_, since every exchange returns its predecessor in that order. One producer's exchanges are sequenced, so coherence keeps them in program order. Other producers' nodes may land in between.

Claim 7 — Node lifetime: a popped node may be reused only after a later pop() returns a different node. A pop() returning nullptr does not release it.

Progress, stated precisely: push is wait-free where the hardware exchange is (x86 LOCK XCHG, ARM LSE SWPAL). The queue is not lock-free and not linearizable. If a producer is preempted between its exchange and its link store, every later node stays unreachable until that thread runs again, so a pop() can return nullptr after a later push has fully completed.

On x86-TSO: release stores and acquire loads compile to plain MOV, and the tail_ exchange is LOCK XCHG whatever ordering you request. GCC compiles a seq_cst store to XCHG, not MFENCE, so an all-seq_cst push has three locked instructions instead of one. Measured (single thread, uncontended, median of 9 runs, two invocations):

	push	pop
acq_rel	8.7–8.8 ns	1.9 ns
all seq_cst	20.5–20.9 ns	1.9 ns

The 2- and 4-producer comparison needs dedicated cores. It is in scripts/run_pinned_bench.sh, and its results are not yet recorded.

---

TSan validation

cmake -S . -B build_tsan -G Ninja -DTSAN=ON -DCMAKE_BUILD_TYPE=RelWithDebInfo
cmake --build build_tsan
./build_tsan/test_tsan

Expected: 18 passed, 0 failed, zero TSan reports. The four litmus tests:

Test	What it validates
MP (Message Passing)	Payload written before push is visible after pop
Two-producer FIFO	Each producer's nodes arrive in push order
8-producer stress	Scales correctly under high contention
Incomplete push	Consumer correctly retries during the exchange-to-store window

---

Benchmark

cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build
./build/bench_mpsc

Full results, methodology, and an explicit tier system for how much to trust a given number (shared container vs. pinned vs. kernel-isolated cores) are in BENCHMARK_RESULTS.md. Summary of what's there and how to reproduce it:

Benchmark	What it measures	Status
bench_ordering	Same algorithm with acq_rel vs all-seq_cst orderings: uncontended push/pop cost, and 2/4-producer throughput	Uncontended committed (container): +12 ns/push for seq_cst, pop unchanged. Contended: pending dedicated cores
bench_mpsc	MPSC vs mutex throughput, ping-pong latency	Committed (container + WSL2/laptop, both pinned)
bench_batch	Batch push vs single push, K=1..128	Committed (container + WSL2/laptop, both pinned)
bench_t2t	ITCH decode -> LOB -> A-S quote, single-threaded	Committed (container + WSL2/laptop, both pinned)
bench_stress	Sustained (not peak) multi-producer contention, full latency histograms	Committed (WSL2/laptop, 6 pinned cores); kernel-isolated-core run still pending
bench_t2t_queue	Same tick-to-trade pipeline, but split across a decode thread and a strategy thread connected by MpscQueue — the version that actually exercises the queue	Committed (WSL2/laptop, 6 pinned cores); kernel-isolated-core run still pending
bench_comparison	MpscQueue vs std::mutex, a spinlock, and boost::lockfree::queue, same workload, with a written trade-off discussion	Committed (WSL2/laptop, 6 pinned cores) — MpscQueue beats the best alternative by 3.7-4.3x, median of 5 runs; kernel-isolated-core run still pending

scripts/run_pinned_bench.sh runs all of the above with core isolation checks, taskset/chrt -f pinning, and governor/Turbo reporting, and tells you plainly if the environment it's running in doesn't qualify as a trustworthy result rather than silently printing numbers anyway. See BENCHMARK_RESULTS.md for the exact environment behind every number below — that document does not present anything as a result that wasn't actually produced by the command printed next to it.

Numbers below are the committed container results (see BENCHMARK_RESULTS.md for the exact environment and full methodology, plus the WSL2/laptop results run on real dedicated hardware):

=== Throughput: MPSC vs Mutex (msgs/sec) ===

producers   K=1 (single push)
1             46.73 M
2             67.03 M
4             75.76 M
8             74.87 M

=== Push-to-pop latency (single-thread ping-pong) ===
  p50     :  21 ns
  p99     :  25 ns
  p99.9   :  98 ns

These are same-thread round-trip numbers, not cross-thread contention under sustained load. On real dedicated hardware (WSL2, 6 pinned cores — see BENCHMARK_RESULTS.md), MpscQueue beats std::mutex by 3-4x at every non-oversubscribed producer count, and by 3.7-4.3x over the best of three alternatives (mutex, spinlock, boost::lockfree::queue) in a head-to-head comparison — see BENCHMARK_RESULTS.md's "Sustained multi-producer contention" and "Comparison" sections for the full numbers and how they were produced.

---

Properties

Property	Value
Producer threads	Any number (M)
Consumer threads	Exactly one
Push	Wait-free, O(1) (x86, ARM LSE); lock-free on ARMv8.0 LL/SC
Pop	O(1), never blocks; algorithm is not lock-free (see Progress)
Linearizable	No — per-producer FIFO, no loss/duplication, eventual visibility
Memory allocation	None (intrusive)
ABA problem	Impossible (no CAS)
Per-producer ordering	FIFO guaranteed
Cross-producer ordering	Not guaranteed (by design)
Memory model	C++20 acquire/release (no seq_cst)

---

Building

# Release build + tests
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure

# ThreadSanitizer (proves zero data races)
cmake -S . -B build_tsan -G Ninja -DTSAN=ON -DCMAKE_BUILD_TYPE=RelWithDebInfo
cmake --build build_tsan && ctest --test-dir build_tsan --output-on-failure

# AddressSanitizer (catches memory errors)
cmake -S . -B build_asan -G Ninja -DASAN=ON -DCMAKE_BUILD_TYPE=RelWithDebInfo
cmake --build build_asan && ctest --test-dir build_asan --output-on-failure

---

Limitations

Single consumer only. For MPMC, use a different algorithm (e.g., the Michael-Scott queue with CAS on both head and tail). This queue trades the MPMC generality for wait-free producers and simpler proof obligations.

Intrusive nodes. Nodes must inherit MpscNode. For a non-intrusive version, embed a MpscNode as a member of a wrapper and use a free-list allocator to amortise allocation cost.

Incomplete push window. pop() may return nullptr when a producer has completed tail_.exchange but not yet stored to prev->next. Callers must retry on nullptr. This is inherent to the algorithm, and it is also why the queue is not lock-free: if that producer is preempted, the window lasts until it runs again. Don't busy-spin unconditionally on this — see the recommended retry pattern below.

Node lifetime after pop(). A node returned by pop() becomes the queue's new sentinel (head_), and if the queue is now empty, also tail_. It stays in use until a later pop() returns a different node. A pop() that returns nullptr does not release it. An earlier version of this README said it did. Following that rule (pop a, pop nullptr, re-push a) links a to itself, and pop() then returns a forever, as tests/test_lifetime.cpp demonstrates. A drained queue therefore holds on to its last node until the next node arrives. This bit bench/bench_stress.cpp during development — see BENCHMARK_RESULTS.md's "Validation" section for how it manifested (a livelock, not a crash) and the fix (release node k only once pop() has returned node k+1). Full detail and the fix pattern are in queue.hpp's pop() doc comment.

Recommended retry pattern. A bare while (!(p = q.pop())); is correct but burns a full core even when idle, and can starve producers on an oversubscribed host. Escalate: spin briefly, then yield, then sleep:

T* p; int spins = 0;
while ((p = q.pop()) == nullptr) {
    if      (spins < 1000) { mpsc::cpu_relax(); ++spins; }   // PAUSE on x86, YIELD on ARM
    else if (spins < 1100) { std::this_thread::yield(); ++spins; }
    else                     std::this_thread::sleep_for(20us);
}

This is bench::Backoff in bench/histogram.hpp, used throughout this repo's own benchmarks.

---

References

1. Vyukov, D. (2010). Intrusive MPSC node-based queue. https://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue

2. ISO/IEC 14882:2020 §6.9.2 — memory ordering semantics.

3. Sewell, P. et al. (2010). x86-TSO: A rigorous and usable programmer's model for x86 multiprocessors. CACM 53(7).

4. Boehm, H. & Adve, S. (2008). Foundations of the C++ concurrency memory model. PLDI 2008.