13 ms·

The article is discussing an exclusive-writer, exclusive-reader ring buffer. Interleaved writers is intentionally not considered. > A common strategy to reduce

The 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 ago
  You 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 ago
    Using 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.
    - chrisseaton 7y ago
      > Using a spinlock / mutex would improve performance if we're only talking about 2 threads. ... but that wouldn't be lock-free would it?
      - dragontamer 7y ago
        > ... but that wouldn't be lock-free would it? Why do people do lock free? 1. Lockfree is sometimes easier to understand -- This case it is not. They've added a "watermark" variable to the queue, so its more difficult to reason about now. 2. Lockfree can be faster -- This is the case most people hope for. But it is far more difficult to do in practice. Spinlocks are surprisingly fast. There's kind of an "implicit" assumption that you're going lock-free because of benefits of #1 (easier) or #2 (faster). But in this case... they built a lock-free data structure that is HARDER to understand and very clearly slower.
        chrisseaton 7y ago
        3. Lock-free cannot deadlock when one of the threads dies in the middle of an operation. 4. Lock-free will not stall all other threads if one of the threads stalls in the middle of an operation.
        dragontamer 7y ago
        3. If your writer thread dies randomly, then your reader thread has nothing to do. 3 part 2: If your reader thread dies randomly, then your writer thread eventually fills the buffer and has nothing to do. Both cases turn into a deadlock with this "lock-free" buffer. You can't afford to have either thread die, regardless of the "lock free" or "locked" implementations. > 4. Lock-free will not stall all other threads if one of the threads stalls in the middle of an operation. Same thing here. The queue will eventually fill up if there's a stall, causing the reader (and / or the writer) threads to stall as well. So in practice, neither #3 nor #4 actually help you out.
        7y ago
BubRoss 7y ago
If there is exclusive writing and exclusive reading, then it either isn't lock free or it isn't correct.

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 ago
You 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 ago
  Using 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.
  - chrisseaton 7y ago
    > Using a spinlock / mutex would improve performance if we're only talking about 2 threads. ... but that wouldn't be lock-free would it?
    - dragontamer 7y ago
      > ... but that wouldn't be lock-free would it? Why do people do lock free? 1. Lockfree is sometimes easier to understand -- This case it is not. They've added a "watermark" variable to the queue, so its more difficult to reason about now. 2. Lockfree can be faster -- This is the case most people hope for. But it is far more difficult to do in practice. Spinlocks are surprisingly fast. There's kind of an "implicit" assumption that you're going lock-free because of benefits of #1 (easier) or #2 (faster). But in this case... they built a lock-free data structure that is HARDER to understand and very clearly slower.
      - chrisseaton 7y ago
        3. Lock-free cannot deadlock when one of the threads dies in the middle of an operation. 4. Lock-free will not stall all other threads if one of the threads stalls in the middle of an operation.
        dragontamer 7y ago
        3. If your writer thread dies randomly, then your reader thread has nothing to do. 3 part 2: If your reader thread dies randomly, then your writer thread eventually fills the buffer and has nothing to do. Both cases turn into a deadlock with this "lock-free" buffer. You can't afford to have either thread die, regardless of the "lock free" or "locked" implementations. > 4. Lock-free will not stall all other threads if one of the threads stalls in the middle of an operation. Same thing here. The queue will eventually fill up if there's a stall, causing the reader (and / or the writer) threads to stall as well. So in practice, neither #3 nor #4 actually help you out.
        7y ago

BubRoss 7y ago

If there is exclusive writing and exclusive reading, then it either isn't lock free or it isn't correct.