Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



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


This classic paper from 1996 describes a simple unbounded mpmc queue: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues....


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).


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.



The paper is annoyingly difficult to locate but the author's implementation is at https://github.com/oliver-giersch/looqueue-rs


Checkout the Nim-loony repo in the paper folder for the pdf.


Ah right, in the nim repo, not the authors one. Contains https://github.com/nim-works/loony/blob/main/papers/GierschE... indeed, thank you


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: