unsafe impl<T, const N: usize> Sync for WFQueue<T, N> {}
unsafe impl<T, const N: usize> Send for WFQueue<T, N> {}
These impls are unsound, because neither constrains `T` to be `Sync`/`Send`. As-written this would let you declare a `WFQueue<Rc<T>, N>` and pass non-atomic-refcount pointers between threads.
> Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect. Being wait-free requires that failure or suspension of any thread can’t cause failure or suspension of another thread. This queue in fact does not fulfill that requirement. The main section which discusses the wait bounds of queue operations has been amended to reflect this, but other parts of this article have not been. As such there may parts of the text which refer to this as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks of this post after it was already posted. Thanks for the correction Reddit user matthieum!
Thanks. I jumped at the headline. I'd be happy with wait-free MPSC. I haven't checked in for a while. Have there been any breakthroughs in low-complexity wait-free queues in the past 10 years?
This was the very best bounded MPMC queue when I last looked into these things years ago, and as far as descendants of the Vyukov MPMC cycle queue go, I don't think it's possible to do much better.
I think your citation date is off, by the way. As far as I can tell, it was first published in January 2011.
Perhaps I missed it but there didn't appear to be discussion of false sharing between the N individual data slots. It might be beneficial to pad each slot to a cache line width (or at least less slots per line), and/or using some kind of bijective hashing on the slot lookup so that sequential tickets don't access adjacent slots.
If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.
If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.
It's also a joke because girls definitely don't care about "Fast MPMC Queues with Bounded Waiting" at all. We can estimate the HN audience to be ≈95% male.
Because it would not even pass initial code review for most developers. Most people use short review prompt, with yes/no answers.
Imagine the code compilers (or some analysis tool) gives several concurrency and memory warnings. It has easy workaround (just annotate strange code, with links to explanations that this is workaround for low level bugs).
I am too tired of shitty "safe" Rust code, with 'unsafe' section around every library call (not case here, just an example)! Be clear with that, it takes 15 minutes and 10 cents!
This project could have correct concurrent code and design, but around much narrower definitions. But most people will not go too deep with review to find it!
Surprised nobody here nor on the reddit thread caught this one: https://github.com/nahla-nee/wfqueue/blob/main/src/lib.rs#L3...
These impls are unsound, because neither constrains `T` to be `Sync`/`Send`. As-written this would let you declare a `WFQueue<Rc<T>, N>` and pass non-atomic-refcount pointers between threads.
The fix is straightforward:
I.e., WFQueue is only Sync if T is Sync, and likewise for Send.
Actually, later on, the code makes a similar mistake, but only for one impl.
> Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect. Being wait-free requires that failure or suspension of any thread can’t cause failure or suspension of another thread. This queue in fact does not fulfill that requirement. The main section which discusses the wait bounds of queue operations has been amended to reflect this, but other parts of this article have not been. As such there may parts of the text which refer to this as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks of this post after it was already posted. Thanks for the correction Reddit user matthieum!
Classy disclaimer! matthieum's (long) reddit comment is also an informative read: https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...
Thanks. I jumped at the headline. I'd be happy with wait-free MPSC. I haven't checked in for a while. Have there been any breakthroughs in low-complexity wait-free queues in the past 10 years?
The MPSC/MPMC structure in Aeron is wait-free with respect to producers - one producer cannot block another
There are simple node based algorithms that achieves a similar guarantee:
https://web.archive.org/web/20240928080729/https://www.1024c...
There is also a MPMC algorithm on this site very similar to the article
https://web.archive.org/web/20220524214823/https://www.1024c...
5 replies →
The closest thing I know of, is that there was a concurrent queue algo called LCRQ
It originally required double-width CAS, but IIRC in recent years someone figured out how to remove this to make it more portable
Best reference I could find from cursory google:
https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-...
1 reply →
I suspect the search space of low-complexity, or at least what I'd consider "low-complexity", wait-free queues is pretty much exhausted at this point.
This paper [0] from 2022 is pretty good. "Low complexity" it is not, though.
[0] https://arxiv.org/pdf/2201.02179
On the topic of lock free data structures I found this one on a SPSC very interesting too https://david.alvarezrosa.com/posts/optimizing-a-lock-free-r... taking it from 12M to 305M ops/s
That looks like a rewrite of my earlier work: https://rigtorp.se/ringbuffer/
Here's my widely used implementation of this approach in C++: https://github.com/rigtorp/MPMCQueue
This was the very best bounded MPMC queue when I last looked into these things years ago, and as far as descendants of the Vyukov MPMC cycle queue go, I don't think it's possible to do much better.
I think your citation date is off, by the way. As far as I can tell, it was first published in January 2011.
Perhaps I missed it but there didn't appear to be discussion of false sharing between the N individual data slots. It might be beneficial to pad each slot to a cache line width (or at least less slots per line), and/or using some kind of bijective hashing on the slot lookup so that sequential tickets don't access adjacent slots.
You would use one of those approaches:
If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.
If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.
[flagged]
[dead]
[dead]
[flagged]
[flagged]
[flagged]
It's a play on the classic pop hit song "Girls Just Wanna Have Fun"
It's also a joke because girls definitely don't care about "Fast MPMC Queues with Bounded Waiting" at all. We can estimate the HN audience to be ≈95% male.
2 replies →
Why should anyone care what comments your agent has on code?
> Or add section to explain most common agent comments.
Shouldn't your agent explain its own comments? why would the author of a fast queue care what your agent says?
Because it would not even pass initial code review for most developers. Most people use short review prompt, with yes/no answers.
Imagine the code compilers (or some analysis tool) gives several concurrency and memory warnings. It has easy workaround (just annotate strange code, with links to explanations that this is workaround for low level bugs).
I am too tired of shitty "safe" Rust code, with 'unsafe' section around every library call (not case here, just an example)! Be clear with that, it takes 15 minutes and 10 cents!
This project could have correct concurrent code and design, but around much narrower definitions. But most people will not go too deep with review to find it!
3 replies →
Go away