How rigtorp/spscqueue works
Purpose and public entry point
This is a header-only C++11 library implementing a fixed-capacity, wait-free/lock-free single-producer/single-consumer queue. Consumers include include/rigtorp/SPSCQueue.h directly; queue construction takes an item capacity and supports custom allocators.
Core queue implementation
include/rigtorp/SPSCQueue.h contains the entire production implementation and public API: blocking and non-blocking enqueue (emplace/push, try_emplace/try_push), inspection (front, size, empty), and dequeue (pop). The type contract permits exactly one producer thread and one consumer thread; other concurrent access is invalid.
Ring-buffer storage and ownership
The queue allocates a contiguous slot buffer sized for requested capacity plus one sentinel slot, allowing arbitrary non-power-of-two capacities while distinguishing full from empty. Producer-side operations construct elements into writable slots; consumer-side front() exposes the current element and pop() destroys it. pop() therefore requires a non-empty queue and a nothrow-destructible item type. Implementation: include/rigtorp/SPSCQueue.h.
Concurrent index protocol
Producer and consumer coordinate through head/read and tail/write indices. Each side owns updates to its respective index and reads the counterpart only as needed to determine empty/full state. Local cached remote indices let successive operations proceed without repeatedly loading the other thread’s index, reducing cache-coherency traffic. Implementation: include/rigtorp/SPSCQueue.h; conceptual layout: spsc.odg.
Memory-layout and performance boundary
Head and tail indices are aligned/padded to avoid false sharing. The slot storage is also padded at both ends to isolate it from adjacent allocations. These cache-layout decisions are integral to the queue’s performance model rather than optional tuning. Implementation: include/rigtorp/SPSCQueue.h.
Allocation extension point
Storage is obtained through the standard allocator interface. With C++17, the implementation can use allocator size-feedback (allocate_at_least), enabling callers to efficiently provide platform-specific huge-page allocators without embedding OS allocation policy in the library. The Linux huge-page usage example is src/SPSCQueueExampleHugepages.cpp; the core remains platform-neutral in include/rigtorp/SPSCQueue.h.
Build, validation, and executable entry points
CMake defines the project build and example/test/benchmark executables in CMakeLists.txt. src/SPSCQueueExample.cpp demonstrates producer/consumer usage; src/SPSCQueueBenchmark.cpp measures two-thread throughput and round-trip latency; src/SPSCQueueTest.cpp exercises single-thread correctness and multithreaded contention behavior. GitHub Actions runs C/C++ CI through .github/workflows/ccpp.yml.
Main entry points: SPSCQueue.h SPSCQueue public API · CMakeLists.txt CMake build · SPSCQueueExample.cpp Producer/consumer example · SPSCQueueExampleHugepages.cpp Huge-page allocator example
Components 15
Header-only queue
Public API and concurrency-critical implementation.
- SPSCQueue public API · Fixed-capacity queue construction, enqueue, inspection, and dequeue API.
include/rigtorp/SPSCQueue.h - SPSC ownership contract · Exactly one producer and one consumer may access a queue concurrently.
include/rigtorp/SPSCQueue.h - Sentinel ring storage · Contiguous capacity-plus-one slot buffer supports arbitrary capacities.
include/rigtorp/SPSCQueue.h - Producer operations · Constructs items through blocking and non-blocking push operations.
include/rigtorp/SPSCQueue.h - Consumer operations · Exposes front items and destroys them on pop.
include/rigtorp/SPSCQueue.h - Head/tail index protocol · Owned indices and cached remote indices determine full and empty state.
include/rigtorp/SPSCQueue.h - Cache-isolated layout · Padded aligned indices and storage prevent false sharing.
include/rigtorp/SPSCQueue.h - Allocator extension · Uses standard allocators and C++17 allocation size feedback when available.
include/rigtorp/SPSCQueue.h - Queue layout diagram
spsc.odg
Consumers and validation
- Producer/consumer example
src/SPSCQueueExample.cpp - Huge-page allocator example · Demonstrates Linux huge-page allocation without platform policy in the core.
src/SPSCQueueExampleHugepages.cpp - Throughput and latency benchmark · Measures two-thread throughput and round-trip latency.
src/SPSCQueueBenchmark.cpp - Correctness and contention tests · Covers single-thread correctness and multithreaded contention.
src/SPSCQueueTest.cpp
Build and CI
- CMake build · Defines example, benchmark, and test executables.
CMakeLists.txt - C/C++ CI
.github/workflows/ccpp.yml
Connections 21
- SPSCQueue public API → SPSC ownership contract: requires
- SPSCQueue public API → Producer operations: provides
- SPSCQueue public API → Consumer operations: provides
- Producer operations → Sentinel ring storage: constructs into
- Consumer operations → Sentinel ring storage: reads and destroys
- Producer operations → Head/tail index protocol: advances write side
- Consumer operations → Head/tail index protocol: advances read side
- Head/tail index protocol → Sentinel ring storage: coordinates slots
- Cache-isolated layout → Head/tail index protocol: isolates
- Cache-isolated layout → Sentinel ring storage: pads
- Allocator extension → Sentinel ring storage: allocates
- Queue layout diagram → Head/tail index protocol: documents
- Producer/consumer example → SPSCQueue public API: uses
- Huge-page allocator example → Allocator extension: supplies allocator to
- Throughput and latency benchmark → SPSCQueue public API: measures
- Correctness and contention tests → SPSCQueue public API: validates
- CMake build → Producer/consumer example: builds
- CMake build → Huge-page allocator example: builds
- CMake build → Throughput and latency benchmark: builds
- CMake build → Correctness and contention tests: builds
- C/C++ CI → CMake build: runs