11–20 of 46 posts
Strange to see a lock-free ring buffer without seeing mention of LMAX/Martin Thompson's Java Disruptor ( https://github.com/LMAX-Exchange/disruptor )
I wrote my first SPSC circular buffer implementation in TS upon reading the previous post on futex [0] from the same author. It was more intricate than it had seemed, until I finally sat down and wrote my own code. [0]: https://h4x0r.org/futex/ discussion: https://news.ycombinator.com/item?id=44951563
maybe that is what you want.
This isn't that new. (see: FASTER: A Concurrent Key-Value Store with In-Place Updates. 2018 ACM SIGMOD International Conference on Management of Data and related papers) However, this is well written and very easy to read.
Also this Nim library: https://github.com/nim-works/loony Which is based on: https://ieeexplore.ieee.org/document/9490347
Strange to see a lock-free ring buffer without seeing mention of LMAX/Martin Thompson's Java Disruptor ( https://github.com/LMAX-Exchange/disruptor )
Eh, I get it. I also independently came up with these MPMC approaches before hearing about LMAX. They're not entirely trivial but they do follow fairly naturally from the problem space when you really think about it. It's a good piece of engineering, but the one thing that's really unique about LMAX is the amount of advertising it gets.
Virtually zero? I have to go out of my way to remind HN it exists while everyone is 300+ comments deep into reinventing the wheel on a ~quarterly basis.
Is there any chance to modify Vyukov's MPMC queue implement ( https://www.1024cores.net/home/lock-free-algorithms/queues/b... ) to support drop handler? That work doesn't need 128 bit CAS.
Is there any chance to modify Vyukov's MPMC queue implement ( https://www.1024cores.net/home/lock-free-algorithms/queues/b... ) to support drop handler? That work doesn't need 128 bit CAS.
You can use a 64-bit CAS if you want to use a 32-bit epoch and a pointer compression scheme of any kind, or just a 32-bit index into regions that are thread specific. I think I did the later when I did the original work, using the core primitive to build ring buffers that have arbitrary sized slots instead of 64-bit slots (which requires a bit of additional gymnastics, but the basic trick is to have the ring index in…
Looks like a good write up, but I'd caution that some of the statements about memory models aren't completely accurate. The terms relaxed, acquire, and release refer to how an atomic operation is ordered against other accesses to memory. Counter to what the article states, a relaxed atomic is still atomic, meaning that it cannot tear and, for RMW atomic, no other access can go between the read and the write. But a re…
Yes, I meant to clarify the memory model discussion; I had tried to simplify and did a poor job; I got similar feedback after it was published, and never remembered to get to it. Will try to do it soon, though it's about the worst time for this to have hit, not sure when I'll be able to sit down for it, but will try to get it done in the next day. Hopefully it doesn't wait until next time it gets some views.
Looks like a good write up, but I'd caution that some of the statements about memory models aren't completely accurate. The terms relaxed, acquire, and release refer to how an atomic operation is ordered against other accesses to memory. Counter to what the article states, a relaxed atomic is still atomic, meaning that it cannot tear and, for RMW atomic, no other access can go between the read and the write. But a re…
Yes, I meant to clarify the memory model discussion; I had tried to simplify and did a poor job; I got similar feedback after it was published, and never remembered to get to it. Will try to do it soon, though it's about the worst time for this to have hit, not sure when I'll be able to sit down for it, but will try to get it done in the next day. Hopefully it doesn't wait until next time it gets some views.
<3