Rendered at 04:05:32 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
scottlamb 1 days ago [-]
> 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?
gavinray 1 days ago [-]
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
Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
nly 1 days ago [-]
What's important is you know the trade-offs you are making.
You can't have a bounded queue that is always non-blocking because slow consumers can block producers.
You can't have a global FIFO order + multiple producers without slow producers blocking consumers.
You can't have a global FIFO order + have have non-atomic reserve and commit without a interrupted/de-scheduled producer thread being able to block the consumer
If you want atomic commit then you lose separate reserve which means either unbounded memory or atomic fixed-size data with sentinel values, ABA problems etc.
There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
tialaramex 1 days ago [-]
> There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
platinumrad 1 days ago [-]
Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
nly 1 days ago [-]
What was the one time when you need something wait free? I'm assuming interacting with hardware?
platinumrad 1 days ago [-]
Hard real-time industrial automation. Worst job ever, by the way.
duped 1 days ago [-]
This paper [0] from 2022 is pretty good. "Low complexity" it is not, though.
Not a ton, the inexorable march to wider scalar dispatch, deeper pipelines, and ever less uniform geometries (I pine for the halcyon days of two NUMA modes with a QPI bar) has made asymmetrical fencing juicy enough to be be worth the squeeze at the margins, you weren't seeing a ton of `asm volatile ""` on one side and `membarrier()` on the other a decade ago and you'll see that now.
But I think Nathan Bronson's work out of IIRC Standford about 10 or 15 years ago is still more or less the canvas you paint on.
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.
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.
rigtorp 1 days ago [-]
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.
ThePowerOfFuet 22 hours ago [-]
>fast MPMC queues with bounded waiting
Sounds like fun.
xxs 19 hours ago [-]
It's very rare (if ever) I'd want M on both ends... and no work stealing. Usually it's one M and an S.
nttylock 1 days ago [-]
[flagged]
nicechianti 1 days ago [-]
[dead]
tingtin 1 days ago [-]
[flagged]
37738484 1 days ago [-]
[dead]
miguel10 1 days ago [-]
[flagged]
miguel10 1 days ago [-]
[flagged]
throw8384949 1 days ago [-]
[flagged]
dmoy 1 days ago [-]
It's a play on the classic pop hit song "Girls Just Wanna Have Fun"
cubefox 1 days ago [-]
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.
dmoy 6 hours ago [-]
If you wanna be pedantic, the set of people who care about fast mpmc queues with bounded waiting is very very tiny across even the whole population of HN, let alone the broader populace. I would posit that <5% of HN even knows what mpmc queues are.
So of any statement of "<X broad group> just wanna have fast mpmc queues" should be obviously taken as a parody.
At which point... why rail on this?
nahla_nee 12 hours ago [-]
Hi, author of the blog post here, that was in fact not the joke. I'm a girl, I care. I just like playing off of that song's title.
azeirah 20 hours ago [-]
All girls or most girls?
I definitely know some girls who'd love this, and see this as having fun.
cubefox 20 hours ago [-]
> I definitely know some girls who'd love this, and see this as having fun.
That's hard to believe. Then you should know at least an order of magnitude more "boys" who would love this: At an estimated 95% male ratio on HN, 20 times as many. If the "some girls" you "definitely" know are 3, then you would be expected to know about 3x20=60 males who are interested in "fast MPMC queues with bounded waiting", which sounds about equally hard to believe.
1 days ago [-]
periodjet 1 days ago [-]
[flagged]
Blackthorn 1 days ago [-]
Why should anyone care what comments your agent has on code?
bigfishrunning 1 days ago [-]
> 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?
throw74838484 1 days ago [-]
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!
bigfishrunning 15 hours ago [-]
> Most people use short review prompt, with yes/no answers
I don't. I review code by hand, like I have for 20 years. I think you might have some sample bias.
BigTTYGothGF 1 days ago [-]
> Most people use short review prompt
I don't think this is true at all.
groby_b 1 days ago [-]
This project was likely not written just to be convenient for you.
And if it's got value for you, hey, it's open source. Spend the 15 minutes and 10 cents, it's a bargain.
Classy disclaimer! matthieum's (long) reddit comment is also an informative read: https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...
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-...
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...
[1]: https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue...
You can't have a bounded queue that is always non-blocking because slow consumers can block producers.
You can't have a global FIFO order + multiple producers without slow producers blocking consumers.
You can't have a global FIFO order + have have non-atomic reserve and commit without a interrupted/de-scheduled producer thread being able to block the consumer
If you want atomic commit then you lose separate reserve which means either unbounded memory or atomic fixed-size data with sentinel values, ABA problems etc.
There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
[0] https://arxiv.org/pdf/2201.02179
But I think Nathan Bronson's work out of IIRC Standford about 10 or 15 years ago is still more or less the canvas you paint on.
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.
I think your citation date is off, by the way. As far as I can tell, it was first published in January 2011.
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.
Sounds like fun.
So of any statement of "<X broad group> just wanna have fast mpmc queues" should be obviously taken as a parody.
At which point... why rail on this?
I definitely know some girls who'd love this, and see this as having fun.
That's hard to believe. Then you should know at least an order of magnitude more "boys" who would love this: At an estimated 95% male ratio on HN, 20 times as many. If the "some girls" you "definitely" know are 3, then you would be expected to know about 3x20=60 males who are interested in "fast MPMC queues with bounded waiting", which sounds about equally hard to believe.
Shouldn't your agent explain its own comments? why would the author of a fast queue care what your agent says?
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!
I don't. I review code by hand, like I have for 20 years. I think you might have some sample bias.
I don't think this is true at all.
And if it's got value for you, hey, it's open source. Spend the 15 minutes and 10 cents, it's a bargain.