Comment by RossBencina
2 days 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?
2 days 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?
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-...
https://nikitakoval.org/publications/ppopp23-lprq.pdf seems to be the paper in question.
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.
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...
Nice to see Vyukov's MPMC queue mentioned. It's pretty neat. I have used a C implementation[1] of this in a small personal project.
[1]: https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue...
Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
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.
5 replies →
This paper [0] from 2022 is pretty good. "Low complexity" it is not, though.
[0] https://arxiv.org/pdf/2201.02179
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.