7 ms·
Looking at this blog-post more carefully... I'm not convinced that this ring buffer is actually correct unfortunately. > buffer.write.store(buffer.write.load()
by dragontamer 7y ago
Looking at this blog-post more carefully... I'm not convinced that this ring buffer is actually correct unfortunately.
> buffer.write.store(buffer.write.load() + write_len)
This is... an atomic load, followed by an add, followed atomic store.
A TRUE lock-free queue would be buffer.write.AtomicAdd(write_len), (which is a singular, atomic add).
There are many other issues here, but this is the most egregious issue I was able to find. The whole thing doesn't work, its completely non-safe and incorrect from a concurrency point of view. Once this particular race condition is solved, there's at least 3 or 4 others that I was able to find that also need to be solved.
EDIT: Here's my counter-example
write = 100 (at the start)
write_len = 10 for both threads.
|-----------------------------------|
| Thread 1 | Thread 2 |
|-----------------------------------|
| write.load (100)| write.load (100)|
| 100+write_len | |
| write.store(110)| 100+write_len |
| | write.store(110)|
|-----------------------------------|
write = 110 after the two threads "added" 10 bytes each
Two items of size 10 were written to the queue, but only +10 bytes happened to the queue. The implementation is completely busted and broken. Just because you're using atomics doesn't mean that you've created an atomic transaction.
It takes great effort and study to actually build atomic transactions out of atomic parts. I would argue that this thread should be a lesson in how easy it is to get multithreaded programming dead wrong.
---------
For a talk that actually gets these details right... I have made a recent submission: https://news.ycombinator.com/item?id=20096907 https://news.ycombinator.com/item?id=20096907 . Mr. Pikus breaks down how atomics and lock-free programming needs to be done. It takes him roughly 3.5 hours to describe a lock-free concurrent queue. He's not messing around either: its a dense talk on a difficult subject.
Yeah, its not easy. But this is NOT an easy subject by any stretch of the imagination.
- ekimekim 7y agoThe article is discussing an exclusive-writer, exclusive-reader ring buffer. Interleaved writers is intentionally not considered. > A common strategy to reduce the amount of coordination that needs to happen between the two threads (writer, reader) is to associate each coordination variable (pointer) with a single thread that has exclusive write access to it.
- dragontamer 7y ago> reduce the amount of coordination Interesting premise, but it doesn't hold up to scrutiny. 1. They have three shared variables. 2. Those three shared variables are being falsly shared in that data-structure. struct ContiguousAsyncBuffer { buf: *mut u8, len: usize, read: AtomicUsize, write: AtomicUsize, watermark: AtomicUsize, } Look at that struct, all of the atomics are inside the same 64-byte cache line!! That's the worst sharing possibility imaginable! 3. Therefore: the dumb-and-simple "Mutex / Spinlock" would actually have less sharing (share only a ONE variable: the mutex), without any false-sharing of various atomic variables. --------- I kid you not: a "lock/unlock" queue probably performs better than the atomic thing they did here (and the atomic-thing they're doing doesn't even work correctly).
- lalaland1125 7y agoYou keep on stating that the their queue doesn't work but you have yet to provide any correct arguments or evidence that it doesn't work. The only argument you provided was simply incorrect as the article is only concerned with a single reader and writer. You are right that adding some padding might improve performance.
- dragontamer 7y agoUsing a spinlock / mutex would improve performance if we're only talking about 2 threads. That's the main problem. Spinlocks are also much, much, much easier to think about. Frankly, the only reason why this implementation "works" is because they're taking advantage of SeqCst, and the article spends absolutely no time talking about why SeqCst is the cornerstone of this implementation. They actually don't need to use atomics at all when restricted to 2 threads. They just need the seq-cst. Atomics entirely are irrelevant in the 2-thread case. ---------- In any case, code like: > buffer.write.store(buffer.write.load() + write_len) This is horribly, horribly, horribly bad code. This is bad, really bad, no one should be encouraged to write code like this. Yeah, it ends up being correct because of SeqCst and the very specific assumptions of the blog post. But is that really a victory worth talking about? This kind of code should NOT be encouraged. The reason why its "correct" is incredibly subtle and complicated. Its incredibly difficult for me to even put it to words why this seems like it'd work... without giving a ton of links to various memory-consistency talks and papers.
- forrestthewoods 7y agoThe article stipulates there is a single reader and a single writer. The actual API enforces this constraint. https://docs.rs/spsc-bip-buffer/0.1.1/spsc_bip_buffer/fn.bip_buffer.html https://docs.rs/spsc-bip-buffer/0.1.1/spsc_bip_buffer/fn.bip...
- cesarb 7y agoThat's only an issue if there are multiple producers. That code works fine when there's a single producer, since nothing else will modify the "write" value between the load and the store. Given that this is in Rust, it's easy to encapsulate this data structure in a way that makes the compiler enforce this invariant.
- userbinator 7y agoJust because you're using atomics doesn't mean that you've created an atomic transaction. Raymond Chen of Microsoft has a much simpler example of that: https://devblogs.microsoft.com/oldnewthing/20040915-00/?p=37863 https://devblogs.microsoft.com/oldnewthing/20040915-00/?p=37... Yeah, its not easy. But this is NOT an easy subject by any stretch of the imagination. Having had to debug many difficult race conditions before, I can say that anything related to concurrency is extremely difficult to reason about, and needs to be done with a lot of careful thought.