> 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 19 minutes 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
Title sounds like auto translated title for spicy Japanese movie (sorry, just honest feedback).
Agent had several comments (even on recent repo). I wrote much worse code, good for research project, but I would pass. The post is from march 2026 though.
Perhaps add more disclaimers about limitations. Or add section to explain most common agent comments.
RossBencina 42 minutes ago [-]
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.
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-...
[0] https://arxiv.org/pdf/2201.02179
Agent had several comments (even on recent repo). I wrote much worse code, good for research project, but I would pass. The post is from march 2026 though.
Perhaps add more disclaimers about limitations. Or add section to explain most common agent comments.