41–46 of 46 posts
A good write up, but a preallocated MPMC queue can be built without using CAS on every push and without fixed size slots and without multiple rings. While even SPSC ring buffers are simple they are not particularly efficient in the case where the consumer is keeping up with the producer (the ideal case for a queue) due to all the cacheline ping pong. They are not the lowest latency solution
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 th…
> [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…
From my reading of the article I think they understood why we'd want these two primitives for CAS, but they weren't clear (whereas your answer is better here) on whether that's a thing we care about today in 2025. ARM vs x86-64 matters for many people today whereas if we only wanted the other primitive for the M68k well, sorry Amiga fans but who cares. Without immersion in the "Why" of each technological niche it can…
Good question actually! ARM64 has a proper CAS it seems, but I think smaller ARMs still have only LL/SC and that's still relevant for embedded. I can't find a definitive answer for POWER, it is possible that is till only has LL/SC (I leave it to you whether POWER is still relevant, but certainly IBM cares that the standard support it, and it was still relevant during C++11 standardization). Can't find a definite answer for RISC-V: it seems that originally it only had LL/SC, but there are AMO extensions that add RISC-V.
I think most GPUs have native CAS instructions.
There are probably other embedded processors that are still relevant for C++, who knows what they support.
A good write up, but a preallocated MPMC queue can be built without using CAS on every push and without fixed size slots and without multiple rings. While even SPSC ring buffers are simple they are not particularly efficient in the case where the consumer is keeping up with the producer (the ideal case for a queue) due to all the cacheline ping pong. They are not the lowest latency solution
For those of us not up to date with the state of the art, can you provide references? Very interested!
Earlier quoted context omitted.
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…
After a quick glance, it seems that you don’t maintain the reading/writing status in the shared memory. That means you have to make a syacall in every read/write call. You could look into the kaze-core for an alternative implementation, which doesn’t require any syscall if possible. Btw, kaze-core uses a `used` atomic variable, to avoid reading both readPos/writePos in routine - they are not atomic at all.
In JavaScript, atomic operations are relatively lightweight, so their overhead is likely acceptable. Given that, I am open to adjusting my code to your suggested approach and seeing how it performs in practice.
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…