4 ms·
Building a Fast Lock-Free Queue in Modern C++ from Scratch
- rfgplk 3mo agoNice 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).
- p0w3n3d 3mo agoa 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.
- RossBencina 3mo agoIn many application code bases no doubt. But how do you think make_unique and make_shared are implemented?
- pjmlp 3mo agoWith what will most likely become [[unsafe]] profile in C++29, assuming WG21 actually gets their profiles story right.
- bluGill 3mo agoI don't think adding unsafe will be possible - it will break too much existing code. We might be able to add something new that is only possible in an unsafe context, but there is too much existing code. However I do expect a [[safe]] profile (or perhaps several, depending on which paper you read) that everyone is encourage to opt-in to. Likely combines with compiler warnings and static analysis to encourage that use. (Also syntax is still open for debate)
- pjmlp 3mo agoCheck the WG21 mailing proposals. I was for Safe C++ paper, based on Circle experience, but it was shot down due to politics. So we're left with the profiles camp actually delivering, followed by the remaining compilers caring to actually implement them, otherwise it will be static and dynamic analysis as usual.
- will4274 3mo agoIt wasn't shot down due to politics. It was shot down because it solved the wrong problem.
- pjmlp 3mo agoYeah, that is why there was a paper created specifically to kill any other proposal, by the profiles folks with WG21 majority, and ironically profiles are just as annotation heavy, but since it is profiles, it is alright. I call that politics, and in the end the most likely outcome is that by C++29 nothing will be delivered by the profiles group, that is any better than using clang-tidy already today.
- saghm 3mo agoClassic C++, any issue is at most three years away from going away! There will definitely not be any other issues that are also three years from getting fixed when you reach that year though
- pjmlp 3mo agoActually no, because you are missing the time between standard being ratified and actuality being widely available in all major compilers. By the way, it is also classical Web standards, C, Vulkan, OpenCL, and everything else that has a similar process. Ideally we should have gotten rid of C and C++, but I haven't yet found a better Typescript for C.
- saghm 3mo agoFair enough, three years might be more of an upper bound than a lower bound. And yeah, the issue of having to wait is common to standard-based processes, but I've never seen anything else based on a standard so frequently have people need to jump in and try to dissuade people that issues matter because of the rolling timeline so frequently, regularly, and for such a long time as C++. Obviously it would be unreasonable to expect it to become perfect and not need any more changes, but like, I was hearing people complain about various aspects of `unique_ptr` a decade ago, and it seems like we're not even past that yet.
- bluGill 3mo agoFor 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.
- RossBencina 3mo ago"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." For 95% of code std::unique_ptr has no loss of performance. Perhaps. Just remember that it is not a zero-cost abstraction, the compiler won't always be able to entirely eliminate the overhead: https://www.youtube.com/watch?v=rHIkrotSwcc https://www.youtube.com/watch?v=rHIkrotSwcc
- bluGill 3mo agoI watched that about 7 years ago when it first came out, and at an hour long I'm not about to watch it again... From what I can recall those are things that rarely are important. There is a cost, but in most real world code they only add a few nanoseconds - I have more important things to worry about.
- superxpro12 3mo agoAs a firmware developer commonly operating on devices with 32MHz of cpu, i am offended sir.
- bluGill 3mo agoEven at 32Mhz you typically have more important things to worry about. These nanoseconds are unlikely to add up - the overhead from the underlying new/delete is going to be much worse.
- PcChip 3mo agoIs this similar to moodycamel’s?
- nly 3mo agoOnce 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.
- adzm 3mo ago> Real world alternatives show atomic xchg only solutions scale to hundreds of threads But notably only with certain workloads
- nly 3mo agoOnce you get to using custom lock free queues you should be picking something that matches your workload/broader design anyway.
- RossBencina 3mo agoAgreed. 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).
- nly 3mo agocmpxchg can fail spuriously on some platforms
- moffers 3mo agoNot 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.
- deleted 3mo ago[deleted]
- harrisi 3mo agoStrong "oll korrect" vibes.
- jeffbee 3mo agoWhether 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.
- bheadmaster 3mo ago> 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.
- charleslmunger 3mo agoThis 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.
- jeffbee 3mo agoSure, 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.
- bheadmaster 3mo agoOn ARM systems with LSE both weak and strong compile to the same CAS instruction anyway. On LL/SC, using strong means CPU will attempt to retry the same exchange on spurious failure, which increases likelihood that another thread will update the value in the meantime, requiring an outer loop retry. On any plaform which implements strong exchange with zero overhead over weak exchange, we can safely assume they compile to the same thing, and use weak. The only reason to use `strong` is if you have a one-shot CAS operation and you don't want to write a retry loop.
- usefulcat 3mo agoI would have thought that std::optional would have been a likely candidate for use with the Pop() method?
- brcmthrowaway 3mo agoHow can I make a lock free queue without OS support, ESP32?
- stackghost 3mo agoI'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()` calls
- saghm 3mo agoMost 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
- stackghost 3mo agoEdited my comment for clarity. I meant "friendly local" as a euphemism, like "neighborhood pub". Anyways. Ask Claude.
- saghm 3mo agoFair enough! It occurred to me after sending my comment that maybe you didn't mean it literally, but I'm easily confused, so clarity is helpful!
- ojinai 3mo ago[flagged]