Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Girls just wanna have fast MPMC queues with bounded waiting

nahla.dev

Post reply on HN
Print view View original

1–10 of 57 posts

Re: Girls just wanna have fast MPMC queues with bounded waiting

#2

Post by scottlamb »

> 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...

Re: Girls just wanna have fast MPMC queues with bounded waiting

#3

Post by RossBencina »

scottlamb wrote: post #2

> 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 be…

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?

Re: Girls just wanna have fast MPMC queues with bounded waiting

#4

Post by RossBencina »

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.

Re: Girls just wanna have fast MPMC queues with bounded waiting

#5

Post by duped »

RossBencina wrote: post #3
scottlamb wrote: post #2

> 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 be…

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?

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

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

Re: Girls just wanna have fast MPMC queues with bounded waiting

#6

Post by platinumrad »

RossBencina wrote: post #3
scottlamb wrote: post #2

> 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 be…

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?

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.

Re: Girls just wanna have fast MPMC queues with bounded waiting

#7

Post by gavinray »

RossBencina wrote: post #3
scottlamb wrote: post #2

> 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 be…

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-...

Post reply on HN