Building a Fast Lock-Free Queue in Modern C++ from Scratch
I explore why standard mutex-based queues struggle under heavy multi-threaded contention, causing expensive context switches that cripple performance in real-time systems. Instead of blocking, I demonstrate how to build a lock-free queue using atomic Compare-And-Swap operations, allowing threads to retry optimistically without kernel intervention. This approach is essential for high-frequency trading, game engines, and audio pipelines where every microsecond counts.
Under heavy contention your program ends up spending the vast majority of its CPU budget inside the kernel just shuffling threads around, and the standard library queue you put so much trust in starts looking like a parking lot at rush hour.
- bheadmaster
> NOTE: Throughout our implementation we strictly use compare_exchange_strong, but the C++ standard suggests that for some systems like ARM it mighe be a better idea to run a loop with compare_exchange_weak for better performance. The problem with that is a compare_exchange_weak call may fail spuriously, which essentially it can randomly fail even if everything is correct, thus it makes code code a bit more complicated, so I avoided it for this implementation.
The reason using `compare_exchange_weak` is a better idea for lock-free algorithms is that, in most cases, you'll run it in a retry loop anyway. Since `compare_exchange_strong` is compiled to a retry loop, if you do a retry loop of `compare_exchange_strong` you basically have a loop in a loop. Using `compare_exchange_weak` makes things both simpler and more performant.
- moffers
Not trying to be critical, but there are a number of misspellings and grammatical issues and it was actually a breath of fresh air to be reminded while I was reading that a real human being wrote this. I feel a little inspired to turn off spell check for my own writing.
- rfgplk
Nice article. There a few issues with your code however from a cursory glance; your dtor seems to allow for spurious/double frees due to custom deleter support (you wanna check up on that), you also seem to use seq_cst far too much even if not needed (you want to avoid them is queues as much as possible), lastly class FastQueueNodeSlot.. isn't aligned (plus 64b alignment is only a thing for amd64 cpus, apple silicon is larger).
- nly
Once you use atomic cmpxchg you've lost a great deal of scalability because it implies a retry loop (internal or by the user)
The last thing you want is all of the threads failing to cmpxchg (spuriously or otherwise ) spinning on a shared cacheline
Real world alternatives show atomic xchg only solutions scale to hundreds of threads.
- usefulcat
I would have thought that std::optional would have been a likely candidate for use with the Pop() method?