> 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.
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.
Sure, with LSE. But you have to target LSE and get a system that actually contains it, i.e. not the default compiler flags and not the original AWS Graviton.
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.
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).
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.
For 95% of all code that is correct. std::make_* is easy to use and prevents a lot of mistakes, while having no loss of performance. That last 5% though you are doing weird things and so need to do something manually. (as the other poster said, make_unique is implemented with new) Of course the 5% is overall. Some projects never have anything that gets into that last 5%, while others it is more like 50% of the code can't use make_*. If at all possible your use of new/delete should be limited to a data structure/container than handles it, and not scatters all over.
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).
I'd ask your friendly local 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()` calls
Most local LLMs I've used are not particularly great with the advice unfortunately, probably because I haven't spent thousands of dollars on new hardware recently
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.
> 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.
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.
Sure, with LSE. But you have to target LSE and get a system that actually contains it, i.e. not the default compiler flags and not the original AWS Graviton.
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.
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).
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.
For 95% of all code that is correct. std::make_* is easy to use and prevents a lot of mistakes, while having no loss of performance. That last 5% though you are doing weird things and so need to do something manually. (as the other poster said, make_unique is implemented with new) Of course the 5% is overall. Some projects never have anything that gets into that last 5%, while others it is more like 50% of the code can't use make_*. If at all possible your use of new/delete should be limited to a data structure/container than handles it, and not scatters all over.
7 replies →
In many application code bases no doubt. But how do you think make_unique and make_shared are implemented?
7 replies →
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.
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).
> Real world alternatives show atomic xchg only solutions scale to hundreds of threads
But notably only with certain workloads
Once you get to using custom lock free queues you should be picking something that matches your workload/broader design anyway.
I would have thought that std::optional would have been a likely candidate for use with the Pop() method?
Is this similar to moodycamel’s?
How can I make a lock free queue without OS support, ESP32?
I'd ask your friendly local 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()` calls
Most local LLMs I've used are not particularly great with the advice unfortunately, probably because I haven't spent thousands of dollars on new hardware recently
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.