The Real Cost of Lock-Free Queues

Removing a mutex does not automatically produce a low-latency queue. In long-running, high-throughput systems I have seen lock-free structures lose at P99 because several cores repeatedly compete for the same cache line.

The useful property is the progress guarantee, not the absence of a lock.

What lock-free guarantees

Lock-free is a system-wide progress property: even if one thread stalls, at least one competing thread should still be able to make progress. It does not guarantee bounded latency for every thread, freedom from starvation or better throughput.

CAS retries have a hardware cost

Many non-blocking queues use a loop such as:

read state
compute new state
CAS(old,new)
retry on failure

Under contention, failed CAS operations create repeated cache-coherence traffic. I therefore measure retry count and CPU consumption together with throughput.

False sharing remains possible

False sharing can dominate even when logical queue fields are independent. Producer and consumer counters placed on the same cache line can bounce ownership between cores. Padding and memory layout may therefore be part of the algorithm.

Memory ordering is correctness

Atomic operations need an ordering contract that matches which writes must become visible before which reads. Ordering that is too weak breaks correctness; unnecessarily strong ordering can reduce optimization opportunities.

Bounded queues make overload explicit

An unbounded queue can hide overload until memory or latency becomes the failure mode. A bounded queue with explicit backpressure makes the policy visible: wait, reject, drop or degrade.

SPSC, MPSC and MPMC are different workloads

Single-producer/single-consumer assumptions cannot be carried unchanged into multi-producer/multi-consumer designs. Producer and consumer counts, payload size, queue occupancy and CPU placement all belong in a benchmark description.

Allocation can dominate

A queue that allocates a node per operation can spend more time in allocator or GC behavior than in synchronization. Ring buffers and pooled nodes can change the result completely.

How I benchmark

I record producer/consumer topology, CPU affinity/NUMA placement, payload size, occupancy, batching, allocation policy, warm-up and p95/p99 latency. Throughput alone is insufficient.

Lock-free is useful when its progress and contention behavior solve a measured problem. A simple bounded blocking queue can be the better engineering choice when it gives lower CPU use and predictable tails.

References

• Maurice Herlihy, Wait-Free Synchronization
• Michael and Scott, Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
• Cameron Desrochers, concurrentqueue