5 ms·
Girls just wanna have fast MPMC queues with bounded waiting
- throw8384949 4mo ago[flagged]
- dmoy 4mo agoIt's a play on the classic pop hit song "Girls Just Wanna Have Fun"
- cubefox 4mo agoIt'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 4mo ago[deleted]
- periodjet 4mo ago[flagged]
- azeirah 4mo agoAll girls or most girls? I definitely know some girls who'd love this, and see this as having fun.
- cubefox 4mo ago> I definitely know some girls who'd love this, and see this as having fun. That's hard to believe. Then you should know at least an order of magnitude more "boys" who would love this: At an estimated 95% male ratio on HN, 20 times as many. If the "some girls" you "definitely" know are 3, then you would be expected to know about 3x20=60 males who are interested in "fast MPMC queues with bounded waiting", which sounds about equally hard to believe.
- nahla_nee 4mo agoHi, author of the blog post here, that was in fact not the joke. I'm a girl, I care. I just like playing off of that song's title.
- cubefox 4mo agoNo offense, but from the mentioned base rates (HN male to female ratio) I would be surprised if you were biologically female.
- nahla_nee 4mo agoYou can't fathom the idea of women being smarter and more capable than you so you have to resort to shifting the goal post over and over. "No women would ever enjoy this", "No one actually knows a woman that would enjoy this", "Even if you know a woman I bet she's not a biological woman". Glancing over your post history I can see that it's nothing more than posting other people's work, which considering your miserable understanding of statistics, is a blessing that spares the world from having to bear your idiocy. I'm not going to be talked down to by some good-for-nothing man who has never created anything of value in his life. I'm not an HN user because this website sucks, I was informed that someone shared my post here by email so I went to check it out and remember why I don't use this site. You're a woman-repellent and this place is full of the likes of you, that's the reason you don't see many women here, and it's the same reason you don't see women in real life. In summary, since I know you can't handle too many words and summaries are all you read: Go fuck yourself.
- dmoy 4mo agoIf you wanna be pedantic, the set of people who care about fast mpmc queues with bounded waiting is very very tiny across even the whole population of HN, let alone the broader populace. I would posit that <5% of HN even knows what mpmc queues are. So of any statement of "<X broad group> just wanna have fast mpmc queues" should be obviously taken as a parody. At which point... why rail on this?
- cubefox 4mo ago> the set of people who care about fast mpmc queues with bounded waiting is very very tiny across even the whole population of HN Yes, but even of those who do care the vast majority will obviously be male.
- dmoy 4mo agoSure, so what? If OP is a girl and is obviously writing an article about her own interests, what does it matter?
- Blackthorn 4mo agoWhy should anyone care what comments your agent has on code?
- bigfishrunning 4mo ago> 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?
- throw74838484 4mo agoBecause 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 around every library call (not case here, just an example)! Be clear with that, it takes 15 minutes and 10 cents! This project could have correct concurrent code and design, but around much narrower definitions. But most people will not go too deep with review to find it!
- brcmthrowaway 4mo agoHow to get access to your agent?
- groby_b 4mo agoThis 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.
- BigTTYGothGF 4mo ago> Most people use short review prompt I don't think this is true at all.
- bigfishrunning 4mo ago> Most people use short review prompt, with yes/no answers I don't. I review code by hand, like I have for 20 years. I think you might have some sample bias.
- mohamedkoubaa 4mo ago[flagged]
- scottlamb 4mo 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_wanna_have_fast_waitfree_mpmc_queues/ovx8yfz/ https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...
- RossBencina 4mo agoThanks. 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?
- duped 4mo agoThis paper [0] from 2022 is pretty good. "Low complexity" it is not, though. [0] https://arxiv.org/pdf/2201.02179 https://arxiv.org/pdf/2201.02179
- platinumrad 4mo agoI 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.
- gavinray 4mo agoThe 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-State-of-the-Art-LCRQ-Concurrent-Queue-Algorithm-Does-NOT-Require-CAS2?utm_source=chatgpt.com https://ppopp23.sigplan.org/details/PPoPP-2023-papers/2/The-...
- RossBencina 4mo agoPerhaps 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.
- rigtorp 4mo agoYou 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.
- nttylock 4mo ago[flagged]
- duttish 4mo agoOn 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-ring-buffer/ https://david.alvarezrosa.com/posts/optimizing-a-lock-free-r... taking it from 12M to 305M ops/s
- rigtorp 4mo agoHere's my widely used implementation of this approach in C++: https://github.com/rigtorp/MPMCQueue https://github.com/rigtorp/MPMCQueue
- platinumrad 4mo agoThis 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.
- 37738484 4mo ago[dead]
- nicechianti 4mo ago[dead]
- miguel10 4mo ago[flagged]
- miguel10 4mo ago[flagged]
- Human-Cabbage 4mo agoSurprised nobody here nor on the reddit thread caught this one: https://github.com/nahla-nee/wfqueue/blob/main/src/lib.rs#L377 https://github.com/nahla-nee/wfqueue/blob/main/src/lib.rs#L3... unsafe impl<T, const N: usize> Sync for WFQueue<T, N> {} unsafe impl<T, const N: usize> Send for WFQueue<T, N> {} These impls are unsound, because neither constrains `T` to be `Sync`/`Send`. As-written this would let you declare a `WFQueue<Rc<T>, N>` and pass non-atomic-refcount pointers between threads. The fix is straightforward: unsafe impl<T: Sync, const N: usize> Sync for WFQueue<T, N> {} unsafe impl<T: Send, const N: usize> Send for WFQueue<T, N> {} I.e., WFQueue is only Sync if T is Sync, and likewise for Send. Actually, later on, the code makes a similar mistake, but only for one impl. unsafe impl<'a, T, const N: usize> Send for DrivableWFEnqueue<'a, T, N> where T: Send {} unsafe impl<'a, T, const N: usize> Send for DrivableWFDequeue<'a, T, N> {}
- lpage 4mo agoWFQueue isn't handing out &T, so Send is sufficient: unsafe impl<T: Send, const N: usize> Sync for WFQueue<T, N> {} unsafe impl<T: Send, const N: usize> Send for WFQueue<T, N> {}
- tingtin 4mo ago[flagged]
- ThePowerOfFuet 4mo ago>fast MPMC queues with bounded waiting Sounds like fun.
- xxs 4mo agoIt's very rare (if ever) I'd want M on both ends... and no work stealing. Usually it's one M and an S.