Constructing a High-Performance Lock-Free Queue in Modern C++

Published: May 22, 2026

For those who prefer to dive straight into the implementation, the source code is available [here], and you can see it integrated into a live project [at this link]!

Understanding the Foundation

To provide some perspective for the uninitiated, a Queue is a cornerstone data structure in computer science, utilized across nearly every facet of software engineering. At its core, a queue is a First-In-First-Out (FIFO) mechanism.

The basic operations are:

1. Push: Adding an element to the rear.
2. Pop: Removing an element from the front.

In a single-threaded context, implementing this is trivial. C++ provides std::queue, and writing your own from scratch is a beginner-level exercise. However, the complexity spikes exponentially when we transition to a multi-threaded environment.

The Concurrency Conflict

When multiple threads compete for the same data, you encounter contention. Without rigorous management, you run into the dreaded Undefined Behavior (UB)—where one thread modifies the structure while another attempts to read it, leading to catastrophic data corruption.

---

Do You Actually Need a Lock-Free Queue?

Before diving into the "how," you must ask "why." For the vast majority of applications, standard mutex-based synchronization is perfectly adequate.

Check your requirements:

• Is this a general-purpose application? $\rightarrow$ Use a Mutex.
• Is the contention low (few threads)? $\rightarrow$ Use a Mutex.
• Is this a High-Frequency Trading (HFT) system? $\rightarrow$ Lock-Free.
• Is this a real-time game engine or audio synthesis pipeline? $\rightarrow$ Lock-Free.
• Is this a massive data ingestion system? $\rightarrow$ Lock-Free.

In these high-performance domains, a delay of even a fraction of a millisecond can cause a ripple effect: stuttering audio, dropped frames, or missed financial trades. We need a solution that scales linearly with the thread count rather than collapsing under pressure.

Personal Note: I encountered this need while optimizing my software renderer. During a structural re-architecture, the multithreaded CPU communication became a primary bottleneck.

---

Establishing the Baseline: SimpleQueue

Most C++ tutorials suggest that you just slap a std::mutex on a std::queue and call it a day. While this is the correct choice for 90% of use cases, we need a baseline to measure our performance gains.

We will implement SimpleQueue. This version wraps std::queue<T> with a std::mutex. To ensure consistency for future benchmarking, we include a threadId parameter in all methods, even though the baseline doesn't utilize it.

The Implementation

template <typename T> 
class SimpleQueue { 
public: 
    SimpleQueue() = default; 
    
    // Mutexes cannot be copied or moved
    SimpleQueue(SimpleQueue<T>&) = delete; 
    SimpleQueue(SimpleQueue<T>&&) = delete; 

    void Push(T* item, uint32_t threadId) { 
        (void)threadId; 
        std::unique_lock lock(m_Mutex); 
        m_Queue.push(*item); 
    } 

    bool Pop(T* item, uint32_t threadId) { 
        (void)threadId; 
        std::unique_lock lock(m_Mutex); 
        if (m_Queue.empty()) return false; 
        
        *item = m_Queue.front();
        m_Queue.pop(); 
        return true; 
    } 

    // Useful for putting threads to sleep when the queue is empty
    bool IsEmpty(uint32_t threadId) { 
        (void)threadId; 
        std::unique_lock lock(m_Mutex); 
        return m_Queue.empty(); 
    } 

private: 
    std::queue<T> m_Queue; 
    mutable std::mutex m_Mutex; 
};

---

The Hidden Cost of Mutexes

On the surface, SimpleQueue looks elegant. It is correct and performs well with 2 or 3 threads. But what happens when 16 threads hammer this queue thousands of times per second?

The Context Switch Nightmare

When a thread attempts to acquire a lock already held by another, it cannot simply spin and waste CPU cycles indefinitely. Instead, the OS scheduler intervenes via a context switch.

The Performance Gap

The disparity in time scales is staggering. We can represent the cost difference using LaTeX:

$\text{Queue Operation} \approx 10^{-9} \text{ seconds (nanoseconds)}$ $\text{Context Switch} \approx 10^{-6} \text{ seconds (microseconds)}$

This means you are spending roughly $1,000\times$ more time managing the threads than performing the actual work. Under heavy contention, your CPU budget is consumed by the kernel shuffling threads, turning your high-speed queue into a "parking lot at rush hour."

Fun Fact: Modern mutexes are actually "hybrid." They will spin in user space for a short duration before falling back to a kernel wait to mitigate some of this cost. However, under sustained, heavy contention, the penalty remains severe.