alt Hacker NewsThanks. 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?
Replies
platinumrad • today at 6:48 PM
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.
duped • today at 6:37 PM
This paper [0] from 2022 is pretty good. "Low complexity" it is not, though.
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-...