Building a High-Performance Lock-Free Queue from Scratch: A Modern C++ Practical Guide

Introduction: Why Lock-Free Queues?

In the realm of high-concurrency programming, queues serve as the core data structure for passing data between threads, and their performance often determines the overall throughput capacity of an entire system. Traditional locked queues (based on std::mutex), while simple to implement and semantically clear, introduce severe performance bottlenecks under high contention — threads are frequently blocked, context switch overhead skyrockets, and issues like priority inversion may even arise.

Context switching is the process by which the operating system saves and restores register states, flushes the TLB, and performs other operations when switching execution between threads. A single context switch typically costs microseconds, but under high-contention lock scenarios, it can occur hundreds of thousands of times per second, accumulating staggering overhead. Priority inversion is even more insidious: when a low-priority thread holds a lock, a high-priority thread is forced to wait, while medium-priority threads continue running, causing the high-priority task to be indefinitely delayed. This problem famously caused repeated system resets in NASA's Mars Pathfinder embedded system in 1997, becoming a classic cautionary tale in real-time system design.

Lock-Free Queues were born to solve these pain points. They leverage atomic operation instructions provided by modern CPUs (such as CAS, Compare-And-Swap) to achieve thread-safe data structures without using mutexes. This not only significantly reduces latency but also guarantees that the system as a whole can continue making progress even when any thread is suspended — this is the core meaning of "lock-free."

This article draws on practical experience from community discussions to dissect, from the ground up, how to build a high-performance lock-free queue using modern C++, covering key technical challenges including the memory model, atomic operations, and memory reclamation.

Theoretical Foundations of Lock-Free Programming

Atomic Operations and CAS

The core dependency of lock-free queues is atomic operations. In C++11 and later standards, the std::atomic template provides cross-platform atomic type support, with the most critical operations being compare_exchange_weak and compare_exchange_strong, which together implement CAS semantics.

The basic logic of CAS is: only when the current value at the target memory location equals the expected value will it be updated to the new value, and the entire process is atomic. At the hardware level, CAS operations on x86 architectures are implemented via the LOCK CMPXCHG instruction, which locks the cache line (not the entire bus) and uses the MESI cache coherence protocol to ensure atomicity across multiple cores. On ARM architectures, CAS semantics are implemented through LL/SC (Load-Linked / Store-Conditional) instruction pairs: LL reads and marks a memory location, and SC only writes successfully if the mark hasn't been cleared by another core. This explains why C++ provides both compare_exchange_weak and compare_exchange_strong variants — the weak version allows spurious failures, which avoids unnecessary internal retry loop overhead on LL/SC architectures, while the strong version guarantees success when values match but may require additional internal loops on certain architectures to eliminate spurious failures.

Lock-free algorithms typically complete state updates through a "read → compute → CAS commit" loop. If the CAS fails (indicating another thread modified the value first), the entire process is retried. This optimistic concurrency strategy effectively avoids the blocking overhead associated with locks.

Memory Ordering

The most easily overlooked and hardest to master aspect of modern C++ lock-free programming is memory ordering. std::memory_order provides several levels ranging from relaxed (most permissive) to seq_cst (sequentially consistent, most strict):

• memory_order_relaxed: Only guarantees atomicity of the operation, provides no cross-thread ordering constraints, and offers the highest performance.
• memory_order_acquire / memory_order_release: Form "acquire-release" semantics, used to establish correct visibility relationships between producer writes and consumer reads.
• memory_order_seq_cst: The default level, providing globally consistent ordering but at the highest cost.

The memory model introduced in C++11 is an abstract specification that defines the visibility and ordering rules of read/write operations in multithreaded programs, independent of specific hardware. However, different hardware architectures have varying memory model strengths: x86/x64 uses the relatively strong TSO (Total Store Order) model, where most reorderings other than store-load don't occur. Thus, acquire/release semantics are virtually zero-cost on x86 — the compiler only needs to prevent compile-time reordering without inserting additional hardware fence instructions. In contrast, ARM and RISC-V weak memory model architectures allow more aggressive instruction reordering: acquire requires load barriers (e.g., ARM's dmb ishld), release requires store barriers (dmb ish), and seq_cst requires full barriers. This means lock-free code that passes testing on x86, if memory ordering is chosen improperly, may exhibit extremely hard-to-debug concurrency bugs when migrated to ARM platforms.

Choosing memory ordering wisely is key to achieving high performance in lock-free queues. Overusing seq_cst significantly diminishes the performance advantage of lock-free queues, while employing acquire/release semantics at critical synchronization points strikes the optimal balance between correctness and efficiency.

Core Queue Implementation

Linked-List Queue Based on the Michael-Scott Algorithm

Classic lock-free FIFO queues commonly adopt the Michael-Scott algorithm (MS Queue), which uses a singly linked list with a sentinel (dummy) node, maintaining two atomic pointers: head and tail.

This algorithm was proposed by Maged M. Michael and Michael L. Scott in their 1996 paper and was the first lock-free FIFO queue rigorously proven to have linearizability. Linearizability means each operation can be viewed as completing atomically at some point between its invocation and response — this is the strongest correctness guarantee for concurrent data structures, allowing the behavior of concurrent programs to be reasoned about using sequential semantics.

Enqueue operation core steps:

1. Allocate a new node and initialize its data;
2. Use CAS to point the current tail node's next pointer to the new node;
3. Use another CAS to advance the tail pointer.

A subtle aspect of the algorithm is that the enqueue operation consists of two CAS steps. If a thread is suspended between these two steps, other threads performing enqueue will detect that tail->next is not null and will help advance tail (cooperative helping), thereby guaranteeing lock-free progress for the entire system. This cooperative advancement mechanism is the key characteristic distinguishing lock-free algorithms from wait-free algorithms — lock-free guarantees system-wide progress but doesn't guarantee that every thread completes its operation within a bounded number of steps.

Dequeue operation reads the successor of the head node and advances head via CAS. The sentinel node prevents contention between head and tail when the queue is empty, serving as an important guarantee of algorithmic correctness.

Ring Buffer Approach

For Single-Producer Single-Consumer (SPSC) or bounded queue scenarios, array-based ring buffers are often a superior choice. They avoid dynamic memory allocation, offer better cache locality, and typically outperform linked-list approaches significantly. The producer and consumer each maintain an atomic index, and lock-free synchronization is achieved through memory ordering controls on read/write visibility.

The performance advantage of ring buffers over linked lists comes not only from avoiding dynamic memory allocation but also from excellent cache locality. Array elements are stored contiguously in memory, allowing the CPU's hardware prefetcher to efficiently load subsequent elements into L1/L2 caches. High-performance implementations must also pay special attention to false sharing: if the producer index and consumer index reside on the same cache line (typically 64 bytes), frequent writes from two cores cause the cache line to bounce between cores (cache line bouncing), severely degrading performance. The solution is cache line padding; in C++17, you can use alignas(std::hardware_destructive_interference_size) for automatic alignment. LMAX Disruptor is an industrial-grade implementation of a high-performance lock-free queue based on ring buffers, widely used in financial trading systems, and its design philosophy has profoundly influenced subsequent high-performance queue libraries.

In actual engineering, clearly understanding the use case is crucial for selecting the appropriate implementation:

Scenario	Recommended Approach	Complexity
SPSC (Single Producer, Single Consumer)	Ring Buffer	Low
MPSC (Multiple Producers, Single Consumer)	Linked List or Hybrid	Medium
MPMC (Multiple Producers, Multiple Consumers)	MS Queue or Specialized Library	High

General-purpose MPMC queues have far higher complexity and runtime overhead compared to specialized SPSC queues — avoid over-engineering when making your selection.

Challenges and Pitfalls

The ABA Problem

The most famous pitfall in lock-free programming is the ABA problem: a thread reads pointer value A, then other threads change it to B and back to A, causing CAS to incorrectly determine "nothing changed" and erroneously commit. This problem is especially common in scenarios using memory pools or node recycling — a node that was dequeued and freed gets reallocated for a new enqueue operation, having the exact same memory address but potentially fundamentally different content and list structure.

Common solutions include:

• Tagged pointers with version numbers: Pack a version counter with the pointer, incrementing the version on each modification. On 64-bit systems, a common implementation uses the upper 16 bits of the pointer for the version number (since current x86-64 only uses 48-bit virtual addresses), packing both pointer and counter into a single 64-bit atomic variable for single-word CAS.
• Double-word CAS (DCAS): On supported platforms, simultaneously compare and swap both the pointer and version number. On x86, the LOCK CMPXCHG16B instruction enables 128-bit CAS operations, combining a full 64-bit pointer with a 64-bit counter. The C++ standard library doesn't directly support 128-bit CAS, typically requiring compiler built-in functions (such as GCC's __sync_bool_compare_and_swap_16) or platform-specific APIs.

The Memory Reclamation Challenge

In lock-free data structures, when to safely free dequeued nodes is a thorny problem — because other threads may still hold references to those nodes. Mature industry solutions include:

• Hazard Pointers: Proposed by Maged Michael in 2004, the core idea is that each thread maintains a set of "hazard pointers" to declare which nodes it's currently accessing. A reclaiming thread must scan all threads' hazard pointer lists before freeing a node, only releasing it after confirming no one holds a reference. The advantage is bounded reclamation delay (pending node count proportional to thread count); the disadvantage is that scanning overhead grows with the number of threads. Notably, the C++26 standard (proposal P2530) has incorporated std::hazard_pointer into the standard library, signaling the standards committee's recognition of this technology's maturity.
• Epoch-Based Reclamation: Divides time into multiple epochs. Threads record the current epoch when entering a critical section and mark completion upon exit. When all active threads have crossed an epoch boundary, nodes marked for deletion before that epoch can be safely reclaimed. Crossbeam (a well-known concurrency library in the Rust ecosystem) uses an improved epoch-based scheme. This approach is simpler to implement but carries an inherent risk: if a thread remains in an epoch for an extended period (e.g., preempted by the OS or performing a long computation), all pending memory cannot be freed, creating a de facto memory leak.
• RCU (Read-Copy-Update): Common in Linux kernel programming, reads have near-zero overhead, and safe reclamation is ensured through deferred freeing and grace period mechanisms.

These memory reclamation mechanisms are complex to implement and represent the most error-prone aspect of building lock-free queues from scratch. In practice, the choice of memory reclamation strategy often impacts final engineering reliability more than the queue algorithm itself.

Performance Testing and Engineering Recommendations

After building your implementation, rigorous benchmarking is essential. It's recommended to compare lock-free queues against traditional locked queues under varying contention levels in multi-core environments, measuring both throughput and latency. It's important to note that lock-free doesn't always mean faster — in low-contention scenarios, a well-designed locked queue may actually perform better.

Additionally, the following tools are strongly recommended for verification:

• ThreadSanitizer (TSan): A dynamic analysis tool based on compile-time instrumentation that inserts detection code at each memory access, maintaining a vector clock to track happens-before relationships, capable of detecting data races and lock-order violations. TSan incurs 5-15x performance overhead and 5-10x memory overhead, making it suitable only for testing environments — it should not be enabled in production builds.
• relacy framework: Specifically designed for correctness verification of lock-free algorithms. It employs a fundamentally different strategy: using a user-space scheduler to simulate thread execution, systematically enumerating all possible thread interleavings, and checking whether any interleaving produces assertion violations or memory safety issues. This is essentially model checking over a finite state space, capable of discovering concurrency bugs that exist but have extremely low probability of manifesting. In practice, both tools should be used together: relacy for correctness verification during the algorithm design phase, and TSan for regression testing after integration.
• Stress testing: Long-duration, high-concurrency stability testing is indispensable.

Bugs in lock-free code are often probabilistic and hard to reproduce — conventional unit testing alone is far from sufficient.

For the vast majority of application developers, using well-validated mature libraries (such as moodycamel::ConcurrentQueue, boost::lockfree) is usually the safer choice. Building a lock-free queue from scratch is more appropriate as a learning exercise to deeply understand concurrency programming principles.

Conclusion

Building a high-performance lock-free queue from scratch is an excellent litmus test for a developer's mastery of modern C++ memory models, atomic operations, and concurrency theory. It involves multiple deep-water areas including CAS loops, memory ordering selection, ABA problem mitigation, and safe memory reclamation.

Truly mastering these techniques not only enables writing more efficient concurrent code but also cultivates a profound understanding of the essence of concurrent systems. However, in production environments, mature open-source implementations validated by the community are often the more reliable choice — understanding principles and engineering implementation are both indispensable.