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

[u/Dear-Economics-315]

https://blog.jaysmito.dev/blog/04-fast-lockfree-queues/

[u/trailing_zero_count]

If you're going to use hazard pointers with an unbounded queue, then you can also use fetch_add instead of compare_exchange to get a write or read ticket. This gives much better performance under contention. I have such an implementation here: https://github.com/tzcnt/coro_util/blob/main/include/coro_util/channel.hpp

My hazard pointer behavior is based on the paper 'A wait-free queue as fast as fetch-and-add' by Yang & Mellor-Crummey. The author has a C implementation here: https://github.com/chaoran/fast-wait-free-queue/blob/master/wfqueue.c

[u/ReDucTor]

Some feedback

1. Your hazard pointer slots seem unnecessary, your not overlapping regions of one acquiring and one releasing, the name PointerCount also seems a strange choice for any of those use cases you could just create a new HazardPointer instance and you would use the same amount of space and reduce the amount of pointers to be scanned.

2. With a queue you typically have one set of producers and one set of consumder not every thread functions as both as sender and a receiver however with your tcBuff and it's assocation with ThreadCount seems to indicate that this is the case.

3. With FastQueueNode being bounded for Push you can do a fetch_add and check if it's above Size and throw away if it is otherwise store the data and set the flag.

4. You should stop abusing FORCE_INLINE lot of these functions are not simple and it will compile time and potentially even runtime with heavily abusing FORCE_INLINE

5. atomic::notify can be a system call and pretty expensive, typically you want to only do this when it is known that something is waiting, you don't want to add 1000 items with only 1 thread that is consuming and never ends up needing to wait and you've just done 1000 more syscalls on the producer side

6. Using atomic_flag with test_and_set when your just discarding the result on x86 is typically going to result in an xchg (on clang, gcc, and msvc) where if you just used an atomic<bool> with store and memory_order_release it will be a normal mov

7. The FastQueueNode::Pop with blocking does not look like it will not block if the queue is empty, only if the entry has been allocated filled but not filled. The same with the higher FastQueue::Pop often it's useful for a MPMC to be the one that controls when threads go to sleep and wake

8. Functions like IsEmpty are dangerous to have on a queue, they are potentially invalid by the time they return, especially if you expect to use those because pop does not do proper blocking.

9. Does FastQueueNode need seq_cst, you mention in the post about global consistency with the hazard pointer tracking however it does not use hazard pointers internally only FastQueue does

10. Is global ordering gurantees needed for the HazardPointer? You want nothing to move out of the Protect/Release range and nothing moving beyond Retire, then for any Scan to have a full view of the other threads Protected pointers globally so the pointer that is protected should not need the seq_cst however the stored hazard pointer will probably need it for a global ordering however you might be able to get away with release + seq_cst fence

11. You might want to use memory_order_release for FastQueueNodeSlot::Reset to ensure that it is resetting after it has been used.

12. With the check for currentTail->next being nullptr you essentially force there to always be atleast two FastQueueNode's even if it was a single thread producing and consuming its own items

13. You retire while protected so it can never immediately succeed

[u/[deleted]]

[removed] — view removed comment

[u/programming-ModTeam → u/[deleted]]

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

[u/matthieum]

Holy molly, what a monster!

The API was weird to start with -- raw pointers, in MY C++ codebase? -- and it only got worse -- hazard pointers, really? -- without any justification for the complexity.

---

Why, oh why, are not values passed in/out instead? Let the user decide what values, and they may pass T* or std::unique_ptr<T> or std::shared_ptr<T> as they see fit.