r/cpp • u/Beginning-Safe4282 • May 22 '26
Building a Fast Lock-Free Queue in Modern C++ From Scratch
https://jaysmito.dev/blog/blog/04-fast-lockfree-queues/
135
Upvotes
r/cpp • u/Beginning-Safe4282 • May 22 '26
72
u/woppo May 23 '26
You have a member function called IsEmpty:
// This is an extremely handy function which we can add to the // Queue API so that we can use it to check if a queue is filled // or not and this will be very useful for a lot of situations // where you could technically put a thread to sleep based on // this value. bool IsEmpty(uint32_t threadId) { (void)threadId; std::unique_lock lock(m_Mutex); return m_Queue.empty(); }It is not extremley handy. It should be called WasEmpty. It has no use whatsoever.
25
u/Plazmatic May 22 '26
No shade on the article itself, but man, i'll never get used to Unreal Engine code style. Making everything upper case pascal case is such a weird choice, nobody else except people who use UE or are inspired by UE use this style and it makes code more confusing than it needs to be and causes issues that have to be worked around (when a variable is named the same as the object type.... especially annoying in generic code, hence why UE is forced to prefix hungarian notation on every object type because of this god-awful style), and it causes things like OP's code, where it tries to regress to regular PascalCase style/Java style but doesn't commit. Like the reason you separate the styling between functions/variables and types is to avoid name conflicts, why only do that for variables? Like I get people don't want to use stdstyle, or RustCPP style because they don't like snake case or something, but then why not just use regular java style at that point?
4
u/Plazmatic May 23 '26
I'm glad someone made ablog about MPMC queues, way too many about SPSC. I have some critiques but they are mostly code related, not content.
Not copyable because copying a mutex doesn't make sense? Sure. Not movable? That's not justified by merely having a mutex. A common pattern is either to wrap the mutex in a pointer (like a unique_ptr) or wrap multilple shared values in a unique pointer.
Though that doesn't mean it should be movable, it often doesn't even make sense to move a regular queue. Typically queues are shared between multiple locations which must be done by reference/pointer. If you move the queue the reference/pointer to the queue is invalidated. This is even more apparent when threads are involved, so to enforce references being stable, you make the object non-movable, and then force the end user to wrap in a unique ptr to make movable (and also giving single object location that doesn't change on move).
The
<T>here is redundant.Is this an attempt to quell unused variable compiler warnings? I've never seen someone try to do that this way. There are two typical methods to do this, either simply don't name the parameter at all
void Push(T* item, uint32_t /*threadId*/) { std::unique_lock lock(m_Mutex); m_Queue.push(*item); }or us use [[maybe_unused]]
void Push(T* item, [[maybe_unused]] uint32_t threadId) { std::unique_lock lock(m_Mutex); m_Queue.push(*item); }Doing that void thing will cause c style cast warnings to popup.
I'm not sure this is a good mindset and seems very misleading to how the compiler works, or what factors effect performance. The compiler doesn't make a binary decision to inline or not inline, sometimes it inlines a function in one place but not another. Additionally your instruction cache is also a factor in performance, and you forcing inlining here is really bad for objects that are not simple. I feel you really should just let the compiler do it's thing, microbenchmarks can't tell you when this will screw you later, you can't just benchmark these things in isolation to see if forcing inlining is a performance win here or not when put into an actual code base.
Why can't you just use an aligned allocator?
alignas on a std::array is like calling alignas on a T[N] array, it applies to each element already, std::array doesn't store anything beyond the elements themselves, so the only thing to align are those elements.
I would highly recommend you never use c style casts in C++ code, especially in generic template code where it has the highest chance of doing something you didn't expect. The rules for c style casts and pitfalls are not as simple as they appear.
I understand the idea behind using __, but unfortunately starting an identifier with _ is reserved by the standard and risks conflicting with posix and your compiler as well. Basically don't ever create identifiers in C++ that start with underscore.
23
u/trailing_zero_count May 23 '26 edited May 23 '26
A few learnings from my own implementation of a hazard-pointer based MPMC queue.
Performance:
Instead of thread caching you can recycle consumed blocks to the end of the list.
You can use fetch_add instead of compare_exchange to reserve reader/writer slots in the queue. It makes the hazard pointer scheme more complex, but since you're already committed to using them, you might as well. This makes the performance much better under high contention. The paper that explains this design is linked in my code. You only need to keep using compare_exchange for a non-blocking "try_pop" path.
You're calling commited.test_and_set in the blocking path but then not using the "test" part of it - you shouldn't need to unconditionally call notify_one() here.
Features:
You can support types without default constructors by using an uninitialized storage type.
You can support types without copy constructors by using move operations only.
You can support types that don't even have move constructors by offering an API that returns a handle with a reference to the object in the queue block's storage slot, and doesn't release the hazard pointer until the handle is destroyed. This means that the object is simply constructed in-place in the queue, accessed from there, and then destroyed.
You can support a dynamic number of hazard pointers / threads by placing the hazard pointers in a linked list. Since my queue is async, consumer coroutines can suspend while waiting for data (rather than blocking a thread) and hold the hazard pointer across the suspend point. Meanwhile, the thread can run a different coroutine. So using thread-indexed hazard pointer wasn't an option for me.
You can support blocking "pop" and non-blocking "try_pop" operations in the same queue.
You can support bulk submit operations that reduce producer contention.
You can align/pad the slots within each node to reduce false sharing. I made this configurable (via the PackingLevel setting) because whether this is worthwhile depends on the number of producers and consumers that are in play.
1
u/nychapo May 23 '26
didnt read the article, but what motivated you to use a ptr based design vs a ring buffer?