Put a ring on it: a lock-free MPMC ring buffer
1–10 of 46 posts
Re: Put a ring on it: a lock-free MPMC ring buffer
#2This 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.
Re: Put a ring on it: a lock-free MPMC ring buffer
#3This 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.
Well, when I was doing the original work on it (about 5 years ago now), I spent a lot of time trying to find something else in the literature. I couldn't find anything that wasn't SPMC or MPSC, unless it had severe limitations, like not actually having a drop policy when full.
However, I definitely did not see the paper you've sited, but just spent a few minutes with the paper you cited. Section 5.2 seems to cover their version. It's far from clear what their algorithm is, but they are talking about page eviction; it doesn't seem like they're using even a single fixed array for the ring, but I'm not 100% sure because it's pretty light on any detail. a
Re: Put a ring on it: a lock-free MPMC ring buffer
#4Strange to see a lock-free ring buffer without seeing mention of LMAX/Martin Thompson's Java Disruptor (https://github.com/LMAX-Exchange/disruptor)
Re: Put a ring on it: a lock-free MPMC ring buffer
#5I 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
Re: Put a ring on it: a lock-free MPMC ring buffer
#6This 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
Re: Put a ring on it: a lock-free MPMC ring buffer
#7Looks 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 relaxed atomic does not order other accesses, which can lead to unintuitive outcomes.
By contrast, once you've observed another thread's release store with an acquire load, you're guaranteed that your subsequent memory accesses "happen after" all of the other thread's accesses from before that release store -- which is what you'd intuitively expect, it's just that in modern systems (which are really highly distributed systems even on a single chip) there's a cost to establishing this kind of guarantee, which is why you can opt out of it with relaxed atomics if you know what you're doing.
Re: Put a ring on it: a lock-free MPMC ring buffer
#8Strange to see a lock-free ring buffer without seeing mention of LMAX/Martin Thompson's Java Disruptor ( https://github.com/LMAX-Exchange/disruptor )
I don't think I even saw this until I published the article. I don't think it was academically published, or googled well back in 2000. Nor did it match my needs for a ring buffer at the time, which was to drop stale data (I think in that algorithm, write operations fail when the buffer is full), so if I did see it, I wouldn't have payed enough attention to notice if it even had users. It's good work for sure, but that's why it didn't get mentioned.
Re: Put a ring on it: a lock-free MPMC ring buffer
#9This 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
So that work came after mine, and seems to be a FIFO not a ring buffer. The library I built at the time also had FIFOs and LIFOs that were tweaks on previous algorithms, but nothing earth shaking. I'll check this one out when I can though.
Re: Put a ring on it: a lock-free MPMC ring buffer
#10Looks 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.