I’m a C++ student and I’ve spent the last few months obsessing over concurrent data structures. I’m sharing daking::MPSC_queue, a header-only, lock-free, and unbounded MPSC queue designed to bridge the gap between linked-list flexibility and array-based throughput.
1. FACING THE CHALLENGE: THE "LINKED-LIST BOTTLENECK" In traditional MPSC linked-list queues, if multiple producers attempt to enqueue single elements at a high, uniform frequency, the resulting CAS contention causes severe Cache Line Bouncing. In these saturated uniform-load scenarios, throughput hits a physical "floor" that often underperforms compared to pre-allocated ring buffers.
2. ARCHITECTURAL SOLUTIONS FOR REAL-WORLD SCENARIOS Rather than focusing on average throughput under uniform load, this design targets two specific real-world challenges:
Scenario A: Non-Uniform Contention (Burst Resilience) In many systems, producers are mostly idle but burst occasionally. By facilitating a high-speed lifecycle where node chunks circulate from Consumer (Recycle) -> Global Stack -> Producer (Allocate) with strictly O(1) complexity, the queue can rapidly establish SPSClike performance during a burst, peaking at ~161M/s.
Scenario B: Bulk Contention Reduction The enqueue_bulk interface allows producers to pre-link an entire segment in private memory. This reduces the contention from N atomic operations down to a single atomic exchange. The larger the batch, the lower the contention.
3. IMPLICIT CHUNKING & RESOURCE LIFECYCLE Instead of fragmented allocations, memory is managed via a Page -> Chunk -> Node hierarchy.
Implicit Composition: Unlike chunked-arrays, nodes are not stored in contiguous arrays but are freely combined into logical "chunks." This maintains linked-list flexibility while gaining the management efficiency of blocks.
Zero-Cost Elasticity: The unbounded design eliminates backpressure stalls or data loss during traffic spikes, with heap allocation frequency reduced to log(N).
4. ENGINEERING RIGOR * Safety: Fully audited with ThreadSanitizer (TSAN) and ASAN. * Type Safety: Supports non-default-constructible types; noexcept is automatically deduced. * Lightweight: Zero-dependency, header-only, and compatible with C++17/20.
A NOTE ON BENCHMARKS: In the interest of full transparency, I’ve benchmarked this against moodycamel::ConcurrentQueue. In highly uniform, small-grain contention scenarios, our implementation is slightly slower. However, daking::MPSC_queue provides a 3x-4x performance leap in non-uniform bursts and bulk-transfer scenarios where "Zero-Cost Elasticity" and contention reduction are the primary goals.
I’d love to hear your thoughts on this repository!