msqueue

Educational Modern C++ Michael-Scott MPMC queue, plus a mutex-based baseline, correctness tests, stress tests, and synthetic benchmarks.

The lock-free queue uses atomic head/tail pointers, CAS loops, a dummy node, and per-queue hazard pointers for node reclamation. It is intended for learning and comparison, not as a production queue library.

Layout

include/      queue implementations
src/          reserved for future non-template support code
tests/        correctness and stress tests
benchmarks/   throughput benchmark
docs/         design and correctness notes

Build

The project builds as C++20 and has no external dependencies.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build
ctest --test-dir build --output-on-failure

Run benchmarks from a Release build:

cmake -S . -B build-release -DCMAKE_BUILD_TYPE=Release
cmake --build build-release
./build-release/benchmark

Optional ThreadSanitizer build:

cmake -S . -B build-tsan -DCMAKE_BUILD_TYPE=Debug -DENABLE_TSAN=ON
cmake --build build-tsan
ctest --test-dir build-tsan --output-on-failure

AddressSanitizer and UBSan:

cmake -S . -B build-asan -DCMAKE_BUILD_TYPE=Debug -DENABLE_ASAN=ON -DENABLE_UBSAN=ON
cmake --build build-asan
ctest --test-dir build-asan --output-on-failure

Optimization

LockFreeQueue uses two small contention optimizations:

• head_, tail_, and hazard records are cache-line aligned to reduce false sharing between producer, consumer, and reclamation metadata updates.
• CAS retry loops use a bounded backoff before yielding, which reduces retry pressure when several threads contend on the same pointer.

Benchmark

The benchmark measures three workloads:

• producer-only: producer threads enqueue into one shared queue.
• consumer-only: a prefilled queue is drained by consumer threads.
• mixed-mpmc: producers and consumers run concurrently.

Queue construction, prefill, and destruction are outside the measured window. threads is the worker count; for mixed-mpmc, it means that many producers and that many consumers. Results vary by hardware, compiler, scheduler, and contention pattern.

Sample local Release run on 2026-06-30:

mode            queue        threads       avg ops/sec          variance     avg ns/op
--------------------------------------------------------------------------------------
producer-only   lock-free          1           3764993       76230732852           265
consumer-only   lock-free          1           4935107      613736230675           202
mixed-mpmc      lock-free          1           4127182       20359144755           242
producer-only   lock-free          2           5493324        6496668728           182
consumer-only   lock-free          2           4189710       29220351486           238
mixed-mpmc      lock-free          2           5156135       10002503075           193
producer-only   lock-free          4           5477765       20843510905           182
consumer-only   lock-free          4           4413532       32561801583           226
mixed-mpmc      lock-free          4           5887330       16954660891           169
producer-only   lock-free          8           5114173        6237964424           195
consumer-only   lock-free          8           4500366       10388070437           222
mixed-mpmc      lock-free          8           6354610        4462303206           157
producer-only   mutex              1          64937235     3870631846123            15
consumer-only   mutex              1          44451053    29584267861137            22
mixed-mpmc      mutex              1          22400068     9632595730043            44
producer-only   mutex              2          13550753     8662333879819            73
consumer-only   mutex              2          17382086      868280132847            57
mixed-mpmc      mutex              2          19130234     2758619771729            52
producer-only   mutex              4          19161379     1150999992897            52
consumer-only   mutex              4          16350976      214611695930            61
mixed-mpmc      mutex              4          14645607      264763960366            68
producer-only   mutex              8          15760947      163423825307            63
consumer-only   mutex              8          12342733      221878320133            81
mixed-mpmc      mutex              8          10171830      124198683186            98

Correctness

The implementation and its correctness boundaries are summarized in docs/correctness.md, including linearization points, memory reclamation, type requirements, and known limits.

Semantics

Both queues expose enqueue, dequeue, close, and closed.

After close() begins, new enqueue() calls fail and new dequeue() calls return std::nullopt; operations already in progress may finish. The queue object must outlive every thread that may access it.

LockFreeQueue<T> requires T to be nothrow move constructible. dequeue() advances the lock-free list before moving the value out, so throwing moves would make element loss possible after the queue state has already changed.

Limits

• Educational implementation, not a production library.
• Fixed-size hazard table: more than 128 concurrent operations on one queue throws instead of using an unsafe reclamation path.
• No epoch-based reclamation, tagged pointers, or complete ABA prevention.
• Benchmarks are local synthetic workloads, not universal performance claims.