High-Performance SPSC Queue

Lock-free single-producer single-consumer queue optimized for low-latency applications.

Performance Comparison

Benchmarked on 4-core system (2.2 GHz), 2M operations, median of 10 runs:

Version	Throughput	Latency p50	Latency p99
Naive	98M ops/sec	5.5 ns	15.4 ns
Cached	115M ops/sec	5.5 ns	8.2 ns
Improvement	+17%	-	-47%

Key Optimization: Index Caching

Problem

In the naive implementation, every push() reads read_index_ from the consumer's core, and every pop() reads write_index_ from the producer's core. These cross-core atomic loads are expensive (~50 CPU cycles each).

Solution

Cache the remote thread's index locally. Only reload from memory when the operation appears to fail.

Naive version:

bool push(const T& item) {
    // Always read from remote core (~50 cycles)
    const size_t current_write = write_pos_.load(std::memory_order_relaxed);
    
    // Check if full
    if (current_write - read_pos_.load(std::memory_order_acquire) >= Capacity) {
        return false; // full
    }
    // ...
}

Optimized version:

bool push(const T& item) {
    // Check local cache first (~1 cycle)
    const size_t current_write = write_pos_.load(std::memory_order_relaxed);
    
    // Check if full using cached read position
    if (current_write - cached_read_pos_ >= Capacity) {
        // Might be full - reload consumer's position
        cached_read_pos_ = read_pos_.load(std::memory_order_acquire);
        if (current_write - cached_read_pos_ >= Capacity) {
            return false; // Actually full
        }
    }

    // ...
}

Why It's Safe

The cached value can be stale, but this is always safe:

• Producer caches read_index_: Consumer only increments it (frees slots). If our cache is stale, we think there's less space than there actually is → false negative (think queue is full when it's not). Never a false positive.

• Consumer caches write_index_: Producer only increments it (adds items). If our cache is stale, we think there are fewer items than there actually are → false negative (think queue is empty when it's not). Never read uninitialized data.

Result: No data corruption possible. We only read from memory when absolutely necessary.

Impact

• Tail latency: 47% improvement (15.4ns → 8.2ns)
• Throughput: 17% improvement
• Cache traffic: ~90% reduction in cross-core atomic loads

The biggest win is in p99 latency, which is critical for high-frequency trading where predictable performance matters more than average-case speed.

Implementation Details

Cache Line Alignment

All shared variables are aligned to 64-byte cache lines to prevent false sharing:

alignas(64) std::atomic<size_t> write_index_{0};  // Producer's cache line
alignas(64) std::atomic<size_t> read_index_{0};   // Consumer's cache line  
alignas(64) T buffer_[Capacity];                  // Buffer in separate lines

Memory Ordering

• relaxed for reading own thread's index (no synchronization needed)
• acquire when reading the other thread's index (establish happens-before)
• release when updating own index (make writes visible to other thread)

This is the minimum synchronization required for correctness.

Power-of-2 Capacity

Queue capacity must be a power of 2 to enable fast modulo via bitmask:

size_t next = (current + 1) & (Capacity - 1);  // Fast bitwise AND
// vs
size_t next = (current + 1) % Capacity;        // Slow division

Build & Run

# Build both versions
make

# Run naive version
make bench

# Run cached version  
make bench_cached

# Compare results
./bench && ./bench_cached

Usage Example

#include "include/spsc_queue_cached.h"

// Create queue with capacity 8192 (must be power of 2)
spsc_queue_cached<int, 8192> queue;

// Producer thread
std::thread producer([&]() {
    for (int i = 0; i < 1000000; ++i) {
        while (!queue.push(i)) {
            // Spin wait if queue full
        }
    }
});

// Consumer thread
std::thread consumer([&]() {
    int value;
    for (int i = 0; i < 1000000; ++i) {
        while (!queue.pop(value)) {
            // Spin wait if queue empty
        }
        process(value);
    }
});

Use Cases

This queue is ideal for:

• Market data processing - Low-latency order book updates
• Trade execution - Minimize order submission delay
• Event streaming - High-throughput message passing
• Signal processing - Real-time data pipelines

Limitations

• Single producer, single consumer only - Not thread-safe for multiple producers/consumers
• Fixed capacity - No dynamic resizing
• Blocking - Uses spin-waiting (high CPU usage when queue is full/empty)
• No backpressure - Caller must handle full queue

References

• Dmitry Vyukov's 1024cores MPMC queue
• Linux kernel kfifo implementation
• C++ Concurrency in Action by Anthony Williams

License

MIT