Girls Just Wanna Have Fast MPMC Queues with Bounded Waiting

scottlamb•about 2 hours 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!

Classy disclaimer! matthieum's (long) reddit comment is also an informative read: https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...

RossBencina•about 1 hour 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?

gavinray•37 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

Best reference I could find from cursory google:

https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-...

platinumrad•44 minutes 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.

duped•about 1 hour ago

This paper [0] from 2022 is pretty good. "Low complexity" it is not, though.

[0] https://arxiv.org/pdf/2201.02179

duttish•13 minutes ago

On the topic of lock free data structures I found this one on a SPSC very interesting too https://david.alvarezrosa.com/posts/optimizing-a-lock-free-r... taking it from 12M to 305M ops/s

RossBencina•about 1 hour 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.

throw8384949•33 minutes ago

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.

Girls Just Wanna Have Fast MPMC Queues with Bounded Waiting

⚡ Community Insights

Discussion (11 Comments)Read Original on HackerNews