Building a Fast Lock-Free Queue in Modern C++ from Scratch

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).

▲

p0w3n3d an hour ago | parent [-]

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.

▲

bluGill an hour ago | parent | next [-]

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.

▲

RossBencina an hour ago | parent [-]

"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

	▲	bluGill 7 minutes ago \| parent [-]
		I 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.

▲

RossBencina an hour ago | parent | prev [-]

In many application code bases no doubt. But how do you think make_unique and make_shared are implemented?

▲

pjmlp 12 minutes ago | parent [-]

With what will most likely become [[unsafe]] profile in C++29, assuming WG21 actually gets their profiles story right.

	▲	bluGill 4 minutes ago \| parent [-]
		I 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)

▲

moffers 2 hours ago | parent | prev | next [-]

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.

▲

nly 2 hours ago | parent | prev | next [-]

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.

▲

RossBencina an hour ago | parent | next [-]

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).

▲

adzm 2 hours ago | parent | prev [-]

> Real world alternatives show atomic xchg only solutions scale to hundreds of threads

But notably only with certain workloads

	▲	nly 2 hours ago \| parent [-]
		Once you get to using custom lock free queues you should be picking something that matches your workload/broader design anyway.

▲

jeffbee 23 minutes ago | parent | prev | next [-]

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.

▲

PcChip 2 hours ago | parent | prev [-]

Is this similar to moodycamel’s?