4 ms·

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 relate

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.

viega 10mo ago
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
- binarycoffee 10mo ago
  I hope you won't mind my picking your brain: which MPSC ring buffer implementations did you find that does drop old items when full? I could only found implementations that are basically re-purposed MPMC, or that cannot deal with non-POD data (seqlock-based).
  - nly 10mo ago
    Generally I find it's best to implement push operations as try_push operations and let the caller decide if they want to drop, or spin. There are definitely designs that can deal with non-POD data of variable size, although that does imply heterogeneous types, which will need some sort of type erasure to destroy safely.
- jcalvinowens 10mo ago
  This classic paper from 1996 describes a simple unbounded mpmc queue: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues....
auxym 10mo ago
Also this Nim library: https://github.com/nim-works/loony https://github.com/nim-works/loony Which is based on: https://ieeexplore.ieee.org/document/9490347 https://ieeexplore.ieee.org/document/9490347
- viega 10mo ago
  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.
- JonChesterfield 10mo ago
  The paper is annoyingly difficult to locate but the author's implementation is at https://github.com/oliver-giersch/looqueue-rs https://github.com/oliver-giersch/looqueue-rs
  - elcritch 10mo ago
    Checkout the Nim-loony repo in the paper folder for the pdf.
    - JonChesterfield 10mo ago
      Ah right, in the nim repo, not the authors one. Contains https://github.com/nim-works/loony/blob/main/papers/GierschEtAl.pdf https://github.com/nim-works/loony/blob/main/papers/GierschE... indeed, thank you

viega 10mo ago

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

binarycoffee 10mo ago
I hope you won't mind my picking your brain: which MPSC ring buffer implementations did you find that does drop old items when full? I could only found implementations that are basically re-purposed MPMC, or that cannot deal with non-POD data (seqlock-based).
- nly 10mo ago
  Generally I find it's best to implement push operations as try_push operations and let the caller decide if they want to drop, or spin. There are definitely designs that can deal with non-POD data of variable size, although that does imply heterogeneous types, which will need some sort of type erasure to destroy safely.
jcalvinowens 10mo ago
This classic paper from 1996 describes a simple unbounded mpmc queue: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues....

auxym 10mo ago

Also this Nim library: https://github.com/nim-works/loony https://github.com/nim-works/loony Which is based on: https://ieeexplore.ieee.org/document/9490347 https://ieeexplore.ieee.org/document/9490347

viega 10mo ago
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.
JonChesterfield 10mo ago
The paper is annoyingly difficult to locate but the author's implementation is at https://github.com/oliver-giersch/looqueue-rs https://github.com/oliver-giersch/looqueue-rs
- elcritch 10mo ago
  Checkout the Nim-loony repo in the paper folder for the pdf.
  - JonChesterfield 10mo ago
    Ah right, in the nim repo, not the authors one. Contains https://github.com/nim-works/loony/blob/main/papers/GierschEtAl.pdf https://github.com/nim-works/loony/blob/main/papers/GierschE... indeed, thank you