21–30 of 46 posts
Earlier quoted context omitted.
Also this Nim library: https://github.com/nim-works/loony Which is based on: https://ieeexplore.ieee.org/document/9490347
The paper is annoyingly difficult to locate but the author's implementation is at https://github.com/oliver-giersch/looqueue-rs
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…
I 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
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.
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 overrun/underrun in a synchronous manner. Therefore a circular buffer is required. I could not find such a niche library written in JS, so I decided to bite the bullet and reinvent the wheel [2].
Looks 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…
https://en.wikipedia.org/wiki/False_sharing
Rather than incrementing each counter by one, dither the counters to reduce cache conflicts? So what if the dequeue becomes a bit fuzzy. Make the queue a bit longer, so everyone survives at least as long as they would have survived before.
Or simply use a prime length queue, and change what +1 means, so one's stride is longer than the cache conflict concern. Any stride will generate the full cyclic group, for a prime.
I 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
Looks 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 was surprised there was no mention of "false sharing". https://en.wikipedia.org/wiki/False_sharing Rather than incrementing each counter by one, dither the counters to reduce cache conflicts? So what if the dequeue becomes a bit fuzzy. Make the queue a bit longer, so everyone survives at least as long as they would have survived before. Or simply use a prime length queue, and change what +1 means, so one's str…
edit: the author claims the algorithm is linearizable, so I'll keep reading the article.
edit2: Right, writer acquires ticket, when done attempts to set the done flag on node. Reader acquires ticket, attempts to consume the node. On failure the writer will retry. Even if you have one producer and one consumer, might not you, theoretically, end up in a scenario where the writer never make progress? I guess as technically no node was produced, this is still technically lock-free, but still... ... oh, I should have read it further, the single writer scenario (even in the dynamic case) is special cased! It will still produce the node.
Nice, but it seems exceedingly complex.
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 cache line at the same time.
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
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 free as it might not provide global progress guarantees ; in practice some platforms give stronger progress guarantees as they might convert an LL/SC to a strong CAS via idiom recognition.
A strong CAS (x86, SPARC I thnk) is implemented directly in the architecture and it is typically strong. It also usually gives strong fairness guarantees.
If your algorithm needs to CAS in a loop might as well use a weak CAS to avoid a loop-of-loops. Otherwise a strong CAS might generate better code on some architectures.
> 32 bits is not enough space for the epoch if we are building something general-purpose.
Note that as long as your buffer can contain less than 31*2 items, 32 bits is usually enough (that's how TCP works for example) as even after overflow you can sequence before and after, unless you can have stale flight messages of more than one overflow ago.
>However, the num_cells field and last_slot field are not tagged _Atomic. That’s because these should be set by one thread during initialization, and then never changed. As long as the memory has synced before other threads start to use these fields, we definitely don’t need them to be treated specially. Usually, if we do initialization in a proper function, the call boundary is going to be a memory barrier that makes sure they’re sync’d when other threads start getting a handle on our ring.
Your threading library likely guarantees that anything sequenced before the start of your thread happens-before the first instruction of the new thread is executed. So you do not need explicit memory barriers. In any case, a function call is at best a compiler barrier, not a full barrier as required on many architectures.
[sorry, I wasn't really going to do a review, these were my notes when reading the algo].
The algo is quite interesting, a lot of corner cases covered. The biggest issue is that the ticketing system is a single memory location where all producers and consumers attempt to write, so it is never going to scale.
If you really really need a lock-free MPMC queue that guarantees a total order, then it can be useful, but outside some hard-realtime scenarios, I can't really see the benefits. Wouldn't a collection of SPSC queues work for the logging scenario given in the introduction?