Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- How can I make a lock free queue without OS support, ESP32?
- I'd ask your friendly neighborhood LLM for design advice, but off the top of my head, so long as `static_assert(std::atomic<whatever>::is_lock_free)` passes, you could build a lock-free SPSC queue with just plain ol' std::atomics and probably liberal use of `alignas()` callsby stackghost
- Is this similar to moodycamel’s?by PcChip
- I would have thought that std::optional would have been a likely candidate for use with the Pop() method?by usefulcat
- Whether the allocator calls are "naive" or not depends entirely on the allocator in use. If you need thread/core locality and batching you can get that by replacing global new/delete functions with a decent allocator.by jeffbee
- 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.
by nly - > Real world alternatives show atomic xchg only solutions scale to hundreds of threads
But notably only with certain workloads
by adzm - Agreed. But you make it sound like the worst case is necessarily fatal. It depends on the use-case. The workable cmpxchg algorithms will make progress on at least one core each round. In a push or pop operation one of the cmpxchg must have succeeded for another to fail. The atomic xchg algorithms that I know of have other undesirable pathologies (e.g. a suspended producer can stall the consumer).by RossBencina
- 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).by rfgplk
- a C++ experienced programmer, I spoke recently to, told me that using new and delete is basically prohibited nowadays in C++ in favour of std::make_unique, std::make_shared etc.by p0w3n3d
- 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.by moffers
- Strong "oll korrect" vibes.by harrisi
- > 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.
by bheadmaster - This is overstated in value; on arm systems with LSE it's faster to use that even for weak operations than to use ll/sc. Even if you are limited to ll/sc the compiler may not put your cas-loop body into the ll/sc region as there's limitations on how many and what type of instructions are permitted there.