Lock Free Is Not Fast

You replaced a std::mutex-guarded queue with a CAS-loop queue. At 4 threads it is 1.3x faster than the mutex version. At 32 threads throughput is 40 percent below the mutex version, and perf shows about 6 CAS attempts per successful push. A colleague concludes the new queue must be broken. Which reading is correct?

Moving every operation to std::memory_order_seq_cst would cut the retry rate, since the retries come from threads reading stale values.

The numbers are consistent with a correct lock-free queue. Lock-free guarantees that some thread completes an operation, not that any given thread is fast, and under heavy contention the retries burn cache-line transfers that a mutex avoids by parking its waiters.

The queue is not lock-free at all. Threads that retry are being blocked by other threads, which makes it obstruction-free at best.

There must be a bug, because a correct lock-free structure never performs worse than a lock.