31–40 of 46 posts
Seems hung up on defining a ring buffer as something non-blocking (dropping). Having used ring buffers in both software and hardware systems for 40 years, we always called them ring buffers without this distinction. We would have called them all ring buffers. One nice thing about them is that it’s very easy to pass buffers back and forth between a single producer and single consumer without any locks or fancy memory…
Earlier quoted context omitted.
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.
> 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.
> have to go out of my way
Yeah, that's exactly the annoying part. Can't mention ring buffer ever without someone bring up LMAX. "But do you know, that some Java developers somewhere once wrote something that didn't completely ruin the hardware performance?! It's stunning and amazing."
Why would you want an MPMC queue primitive, instead of just using MPSC per consumer? I don't really see a discussion of the cache contention issues. (There is some mention of contention, but it seems the author is using the word in a different way.) It looks like both enqueue and dequeue are RMWing the "epochs" variable? This can pretty easily lead to something like O(N^2) runtime if N processors are banging this cac…
The epoch isn’t CAS’d; it is FAA. The epoch is then used to determine if there is contention due to the tail meeting the head, or due to a wrap-around due to slow writes.
There’s also a back-off scheme to ease contention for a full queue.
Though, I did originally have a variant that adds a fairly straightforward ‘help’ mechanism that makes the algorithm wait-free and reduces the computational complexity.
However, the extra overhead didn’t seem worth it, so I took it out pretty quickly. Iirc, the only place where the ring in the queue wouldn’t out-perform it are on tiny queues with a huge write imbalance.
If you go run the tests in the repo associated w the article, you probably will see that a ring with only 16 entries will tend to start being non-performant at about a 4:1 writer to reader ratio. But iirc that effect goes away before 128 slots in the ring.
There, the ring still fits in a page, and even with a big imbalance I can’t remember seeing less than 1m ops per second on my Mac laptop.
Real world observational data beats worst case analysis, and I’ve never seen an issue for scenarios I consider reasonable.
But, if my unrealistic is realistic to you, let me know and I can break out the wait free version for you.
Earlier quoted context omitted.
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 th…
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).
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.
Why would you want an MPMC queue primitive, instead of just using MPSC per consumer? I don't really see a discussion of the cache contention issues. (There is some mention of contention, but it seems the author is using the word in a different way.) It looks like both enqueue and dequeue are RMWing the "epochs" variable? This can pretty easily lead to something like O(N^2) runtime if N processors are banging this cac…
For me, I’ve got use cases where it’s valuable to keep event data interleaved because it will also get used in flight. It works well enough I also use it for things where it’s not necessary like in memory debug rings (which requires a bit of additional work). The epoch isn’t CAS’d; it is FAA. The epoch is then used to determine if there is contention due to the tail meeting the head, or due to a wrap-around due to sl…
fetch_add requires taking a cache line exclusive. If producers and consumers are both doing this on the same cache line, it is very expensive and does not scale.
(withinboredom and gpderetta have raised the same or similar concerns.)
Earlier quoted context omitted.
> 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.
Right buffer is a relative obvious and simple idea. For some reason the Java-OOP crowd keeps thinking that LMAX deserves a nobel price for being neither first nor last to use it. > have to go out of my way Yeah, that's exactly the annoying part. Can't mention ring buffer ever without someone bring up LMAX. "But do you know, that some Java developers somewhere once wrote something that didn't completely ruin the hardw…
Earlier quoted context omitted.
FYI: I have made a SPSC circular buffer for swap data in a pair of process: https://github.com/starwing/kaze-core maybe that is what you want.
By a quick glance, yes, this is what I want: a channel to communicate between processes via a piece of shared memory, protected by a pair of futexes. In JS ecosystem, buffers that allow data loss is more common (aka ring buffers), but ringbuf.js [1] is the only complete implementation to my knowledge. In my use case on I/O between WASM modules where data must be transferred as-is, the process must block on buffer ove…
Btw, kaze-core uses a `used` atomic variable, to avoid reading both readPos/writePos in routine - they are not atomic at all.
Earlier quoted context omitted.
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.
> [re weak vs strong cas] But, while that’s the guidance you’ll find all over the internet, I don’t actually know which CPUs this would affect. Maybe it’s old news, I dunno. But it does still seem to make a shade of difference in real-world tests A CAS implemented with LL/SC (ARM, POWER) is weak as LL/SC an spuriously fail. So it always needs to be retried in a loop. Such a weak CAS might only be lock-free, not wait…
Without immersion in the "Why" of each technological niche it can be hard to judge whether you're reading advice that really hasn't been relevant in decades ("The ASCII character set is not supported on all computers") or that's still important to your work today ("The file naming conventions may vary from one system to another")
Strange to see a lock-free ring buffer without seeing mention of LMAX/Martin Thompson's Java Disruptor ( https://github.com/LMAX-Exchange/disruptor )