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

21–30 of 57 posts

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

#21

Post by groby_b »

throw74838484 wrote: post #15
bigfishrunning wrote: post #13

Earlier quoted context omitted.

> Or add section to explain most common agent comments. Shouldn't your agent explain its own comments? why would the author of a fast queue care what your agent says?

Because it would not even pass initial code review for most developers. Most people use short review prompt, with yes/no answers. Imagine the code compilers (or some analysis tool) gives several concurrency and memory warnings. It has easy workaround (just annotate strange code, with links to explanations that this is workaround for low level bugs). I am too tired of shitty "safe" Rust code, with 'unsafe' section aro…

This project was likely not written just to be convenient for you.

And if it's got value for you, hey, it's open source. Spend the 15 minutes and 10 cents, it's a bargain.

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

#22

Post by nly »

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

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

#24

Post by [deleted] »

cubefox wrote: post #20
dmoy wrote: post #11

Earlier quoted context omitted.

It's a play on the classic pop hit song "Girls Just Wanna Have Fun"

It's also a joke because girls definitely don't care about "Fast MPMC Queues with Bounded Waiting" at all. We can estimate the HN audience to be ≈95% male.

[deleted]

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

#25

Post by periodjet »

cubefox wrote: post #20
dmoy wrote: post #11

Earlier quoted context omitted.

It's a play on the classic pop hit song "Girls Just Wanna Have Fun"

It's also a joke because girls definitely don't care about "Fast MPMC Queues with Bounded Waiting" at all. We can estimate the HN audience to be ≈95% male.

[flagged]

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

#26

Post by platinumrad »

nly wrote: post #22
RossBencina wrote: post #3

Earlier quoted context omitted.

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

Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.

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

#27

Post by platinumrad »

rigtorp wrote: post #18

Here's my widely used implementation of this approach in C++: https://github.com/rigtorp/MPMCQueue

This was the very best bounded MPMC queue when I last looked into these things years ago, and as far as descendants of the Vyukov MPMC cycle queue go, I don't think it's possible to do much better.

I think your citation date is off, by the way. As far as I can tell, it was first published in January 2011.

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

#28

Post by BigTTYGothGF »

throw74838484 wrote: post #15
bigfishrunning wrote: post #13

Earlier quoted context omitted.

> Or add section to explain most common agent comments. Shouldn't your agent explain its own comments? why would the author of a fast queue care what your agent says?

Because it would not even pass initial code review for most developers. Most people use short review prompt, with yes/no answers. Imagine the code compilers (or some analysis tool) gives several concurrency and memory warnings. It has easy workaround (just annotate strange code, with links to explanations that this is workaround for low level bugs). I am too tired of shitty "safe" Rust code, with 'unsafe' section aro…

> Most people use short review prompt

I don't think this is true at all.

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

#29

Post by rigtorp »

RossBencina wrote: post #4

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.

You would use one of those approaches:

If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.

If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.

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

#30

Post by nly »

platinumrad wrote: post #26
nly wrote: post #22

Earlier quoted context omitted.

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

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.

Post reply on HN