7 ms·

> 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

> 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_wanna_have_fast_waitfree_mpmc_queues/ovx8yfz/ https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...

RossBencina 2mo ago
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?
- duped 2mo ago
  This paper [0] from 2022 is pretty good. "Low complexity" it is not, though. [0] https://arxiv.org/pdf/2201.02179 https://arxiv.org/pdf/2201.02179
- platinumrad 2mo ago
  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.
- gavinray 2mo 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 Best reference I could find from cursory google: https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-State-of-the-Art-LCRQ-Concurrent-Queue-Algorithm-Does-NOT-Require-CAS2?utm_source=chatgpt.com https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-...
  - yxhuvud 2mo ago
    https://nikitakoval.org/publications/ppopp23-lprq.pdf https://nikitakoval.org/publications/ppopp23-lprq.pdf seems to be the paper in question.
- nly 2mo ago
  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.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue 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.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue https://web.archive.org/web/20220524214823/https://www.1024c...
  - platinumrad 2mo ago
    Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
    - nly 2mo 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 2mo 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.
- reinitctxoffset 2mo ago
  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.

RossBencina 2mo ago

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?

duped 2mo ago
This paper [0] from 2022 is pretty good. "Low complexity" it is not, though. [0] https://arxiv.org/pdf/2201.02179 https://arxiv.org/pdf/2201.02179
platinumrad 2mo ago
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.
gavinray 2mo 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 Best reference I could find from cursory google: https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-State-of-the-Art-LCRQ-Concurrent-Queue-Algorithm-Does-NOT-Require-CAS2?utm_source=chatgpt.com https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-...
- yxhuvud 2mo ago
  https://nikitakoval.org/publications/ppopp23-lprq.pdf https://nikitakoval.org/publications/ppopp23-lprq.pdf seems to be the paper in question.
nly 2mo ago
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.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue 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.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue https://web.archive.org/web/20220524214823/https://www.1024c...
- platinumrad 2mo ago
  Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
  - nly 2mo 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 2mo 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.
reinitctxoffset 2mo ago
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.