[dead]
Girls just wanna have fast MPMC queues with bounded waiting
31–40 of 57 posts
Re: Girls just wanna have fast MPMC queues with bounded waiting
#32[flagged]
Re: Girls just wanna have fast MPMC queues with bounded waiting
#33[flagged]
Re: Girls just wanna have fast MPMC queues with bounded waiting
#34Earlier quoted context omitted.
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 consum…
> There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
Re: Girls just wanna have fast MPMC queues with bounded waiting
#35Earlier quoted context omitted.
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 consum…
> There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem. That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
Re: Girls just wanna have fast MPMC queues with bounded waiting
#36Earlier quoted context omitted.
> There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem. That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
What was the one time when you need something wait free? I'm assuming interacting with hardware?
Re: Girls just wanna have fast MPMC queues with bounded waiting
#37Surprised nobody here nor on the reddit thread caught this one: https://github.com/nahla-nee/wfqueue/blob/main/src/lib.rs#L3...
unsafe impl Sync for WFQueue {}
unsafe impl Send for WFQueue {}
The fix is straightforward:
unsafe impl Sync for WFQueue {}
unsafe impl Send for WFQueue {}
Actually, later on, the code makes a similar mistake, but only for one impl.
unsafe impl Send for DrivableWFEnqueue where T: Send {}
unsafe impl Send for DrivableWFDequeue {}Re: Girls just wanna have fast MPMC queues with bounded waiting
#38Earlier quoted context omitted.
Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
What was the one time when you need something wait free? I'm assuming interacting with hardware?
Hard real-time industrial automation. Worst job ever, by the way.
Re: Girls just wanna have fast MPMC queues with bounded waiting
#39> 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?
Not a ton, the inexorable march to wider scalar dispatch, deeper pipelines, and ever less uniform geometries (I pine for the halcyon days of two NUMA modes with a QPI bar) has made asymmetrical fencing juicy enough to be be worth the squeeze at the margins, you weren't seeing a ton of `asm volatile ""` on one side and `membarrier()` on the other a decade ago and you'll see that now.
But I think Nathan Bronson's work out of IIRC Standford about 10 or 15 years ago is still more or less the canvas you paint on.
Re: Girls just wanna have fast MPMC queues with bounded waiting
#40[flagged]