Why Understanding Lock‑Free Queues Is Essential for High Concurrency

1. Locked Queues

1.1 Queue essence: shared resource

A queue is the middleman in a producer‑consumer model: producers push data, consumers pop data, ideally without interfering with each other.

1.2 What locks actually protect

Locks safeguard three aspects:

Data consistency : enqueue involves updating the tail pointer, writing the element, and incrementing the count; without atomicity the head and tail can become mismatched.

Operation atomicity : the whole enqueue sequence must appear as an indivisible unit to other threads.

Memory visibility : a write performed by one thread must become visible to another thread after the lock is released.

1.3 Simple locked queue implementation (C++)

#include <queue>
#include <mutex>
#include <condition_variable>

template<typename T>
class ThreadSafeQueue {
private:
    std::queue<T> queue_;
    mutable std::mutex mutex_;
    std::condition_variable cv_;
    size_t capacity_; // 0 means unbounded
public:
    explicit ThreadSafeQueue(size_t capacity = 0) : capacity_(capacity) {}
    void push(T value) {
        std::unique_lock<std::mutex> lock(mutex_);
        if (capacity_ > 0) {
            cv_.wait(lock, [this]{ return queue_.size() < capacity_; });
        }
        queue_.push(std::move(value));
        cv_.notify_one();
    }
    bool pop(T& value) {
        std::unique_lock<std::mutex> lock(mutex_);
        cv_.wait(lock, [this]{ return !queue_.empty(); });
        value = std::move(queue_.front());
        queue_.pop();
        cv_.notify_one();
        return true;
    }
};

The example uses a single coarse‑grained mutex; finer‑grained locking is possible but adds complexity.

1.4 Where lock contention hurts

Uncontended mutex acquire/release costs tens to a hundred nanoseconds; under contention a futex system call can raise the cost to hundreds of nanoseconds or microseconds. Additional hidden costs are cache misses when lock ownership moves between cores and thread starvation when a thread never acquires the lock.

In most workloads these overheads are negligible—seconds of thousands of operations per second make lock cost a tiny fraction, so spending weeks to implement a lock‑free queue for a < 1 % gain is rarely worthwhile.

2. Lock‑Free Queues

2.1 From pessimistic to optimistic concurrency

Locked queues use a pessimistic strategy (assume contention, acquire lock first). Lock‑free queues are optimistic: assume no conflict, proceed, and retry only when a conflict is detected.

2.2 Atomic operations and CAS

The core primitive is Compare‑And‑Swap (CAS). On x86 it maps to the cmpxchg instruction. C++11 wraps it in std::atomic:

std::atomic<int> value{0};
void cas_demo() {
    int expected = 0;
    int desired = 42;
    bool success = value.compare_exchange_weak(expected, desired);
}

compare_exchange_weak

may spuriously fail, which is acceptable in a retry loop; compare_exchange_strong guarantees no spurious failure but is slightly slower.

2.3 Pitfalls of lock‑free queues

ABA problem : a pointer can be recycled to the same address after an intermediate modification, causing a CAS to succeed incorrectly. The usual fix is to attach a version counter to the pointer.

Memory reclamation : after a node is removed other threads may still hold references. Techniques such as Hazard Pointers, RCU, or reference counting are required.

Memory model : choosing the right std::memory_order is critical. memory_order_relaxed is fastest but provides no ordering guarantees; memory_order_seq_cst is safest but slowest. In practice memory_order_acquire and memory_order_release are sufficient for most queue operations.

Because of these complexities, a hand‑rolled lock‑free queue is often slower than a well‑tested library implementation.

3. Two Main Lock‑Free Queue Designs

3.1 Linked‑list (unbounded) – Michael & Scott (MSQueue)

Uses a dummy node; head always points to the dummy, tail points to the last real node. Enqueue appends after tail, dequeue removes after head.

template<typename T>
class MSQueue {
private:
    struct Node {
        T data;
        std::atomic<Node*> next;
        Node() : next(nullptr) {}
        explicit Node(const T& val) : data(val), next(nullptr) {}
    };
    std::atomic<Node*> head;
    std::atomic<Node*> tail;
public:
    MSQueue() {
        Node* dummy = new Node();
        head.store(dummy);
        tail.store(dummy);
    }
    void enqueue(const T& val) {
        Node* new_node = new Node(val);
        Node* old_tail = tail.load();
        while (true) {
            Node* next = old_tail->next.load();
            if (next == nullptr) {
                if (old_tail->next.compare_exchange_weak(next, new_node)) {
                    break; // linked successfully
                }
            } else {
                tail.compare_exchange_weak(old_tail, next); // help advance tail
            }
        }
        tail.compare_exchange_weak(old_tail, new_node);
    }
    // dequeue omitted for brevity
};

Pros: truly unbounded. Cons: each enqueue allocates a node, which is undesirable in low‑latency scenarios.

3.2 Ring buffer (bounded) – SPSC example

Pre‑allocates a contiguous array and uses two atomic indices (head, tail). In the single‑producer‑single‑consumer case no CAS is needed, only appropriate memory orders.

template<typename T>
class SPSCRingBuffer {
private:
    std::vector<T> buffer_;
    size_t capacity_;
    std::atomic<size_t> head_{0};
    std::atomic<size_t> tail_{0};
public:
    explicit SPSCRingBuffer(size_t capacity) : buffer_(capacity), capacity_(capacity) {}
    bool enqueue(const T& item) {
        size_t tail = tail_.load(std::memory_order_relaxed);
        size_t next = (tail + 1) % capacity_;
        if (next == head_.load(std::memory_order_acquire)) {
            return false; // full
        }
        buffer_[tail] = item;
        tail_.store(next, std::memory_order_release);
        return true;
    }
    bool dequeue(T& item) {
        size_t head = head_.load(std::memory_order_relaxed);
        if (head == tail_.load(std::memory_order_acquire)) {
            return false; // empty
        }
        item = buffer_[head];
        head = (head + 1) % capacity_;
        head_.store(head, std::memory_order_release);
        return true;
    }
};

For multiple producers/consumers (MPMC) the design adds a third cursor (commit) and requires CAS to coordinate producers.

4. Choosing the Right Queue

4.1 Self‑assessment questions

Concurrency level : hundreds‑thousands ops/sec → locked queue is sufficient; hundreds‑thousands‑to‑millions ops/sec → consider lock‑free.

Latency requirement : millisecond latency → locked; microsecond or nanosecond latency → lock‑free.

Queue size : if maximum capacity is known, prefer a fixed‑size ring buffer; otherwise a linked‑list implementation.

4.2 When locked queues are appropriate

Medium concurrency (10³‑10⁴ ops/sec).

Latency tolerance at the millisecond level.

Complex business logic where lock overhead is negligible.

Maintainability concerns – locked queues are simple and well‑understood.

4.3 When lock‑free queues are appropriate

Very high concurrency (10⁵‑10⁶ ops/sec).

Latency‑sensitive workloads (micro‑ or nanosecond).

Real‑time systems, high‑frequency trading, game engines, autonomous driving.

Team has expertise to handle the added complexity.

4.4 Business‑flow design matters more than the queue type

Even in high‑frequency trading, most latency stems from inefficient data flow (multiple intermediate queues, cross‑core communication, IO in consumers) rather than the lock itself. Reducing unnecessary stages can cut latency dramatically without changing the queue implementation.

5. Performance Comparison

5.1 Benchmarks

Boost’s lockfree::queue outperforms std::queue + mutex by 75 %–150 % in the evpp benchmark.

moodycamel’s ConcurrentQueue beats locked queues by 100 %–500 %, reaching >70 M ops/sec.

In an HFT test, a lock‑free queue handled 10 M enqueues in 12 ms versus 63 ms for a locked queue.

On some hardware, lock‑free queues can be 15× slower than locked queues when contention is low because CAS spin‑loops waste CPU cycles.

Thus, lock‑free queues excel only under high contention; otherwise locked queues may be faster.

6. Practical Advice

6.1 Recommendations

Measure first. Use perf or flame graphs to locate bottlenecks before replacing a lock.

Prefer mature libraries (moodycamel::ConcurrentQueue, boost::lockfree::queue, atomic_queue) over hand‑rolled implementations.

Start with SPSC designs; only move to MPMC when truly needed.

Prefer fixed‑size ring buffers for low‑latency workloads to avoid dynamic allocation.

6.2 Key takeaways

Locks protect data consistency; they are not inherently a performance killer.

Lock‑free algorithms trade simplicity for higher concurrency; they bring complexity, debugging difficulty, and subtle bugs (ABA, memory reclamation).

The most important skill is to match the queue implementation to the actual workload, not to chase “lock‑free” for its own sake.