8 ms·

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

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.
        cesarb 7y ago
        > 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. There's an important difference between "queue full" and "queue not full, but locked". In the former case, you can either block (waiting for the queue to drain) or discard the data; in the later case, you must wait for the lock to be released before deciding. That is, if you allow data to be discarded when the queue is full, a lock-free queue can also be stall-free. (It might appear that a queue using a lock can also be stall-free, since the amount of work it does while locked is bounded; however that fails once the thread holding the lock is preempted by either a context switch or a hardware interrupt. To really avoid stalls in that case, you have to either block preemption and interrupts, or perhaps you might be able to make it work with some priority inheritance scheme. And yeah, I know that the hardware can "stall" while reading or updating a shared variable, but the amount of work the hardware does in that case is bounded.)
        dragontamer 7y ago
- forrestthewoods 7y ago
  I’d love to see a competing version with benchmarks. I’m not saying you’re wrong. But your making a lot of strong arguments without any evidence. Is 3 atomics on the same cache line a legit problem? I don’t know! But you’re gonna have to prove negative behavior for me to integrate that knowledge into my workflow.
  - dragontamer 7y ago
    > Is 3 atomics on the same cache line a legit problem? This is a commonly known problem called false sharing. https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing To be fair: I don't know how these particular atomics work, maybe they're all on their own cache lines, and 192 bytes are used up for those three atomics so that things are done properly (unlikely, but possible). But atomics in my experience usually assume the "external" programmer figures out the buffering issue to prevent false sharing. 2. These are atomics declared to be SeqCst memory ordering. That means the L1 (and probably L2) caches are flushed every time you read or write to them on ARM systems. (x86 has stricter guarantees and almost "natively" implements SeqCst, so you won't have as many flushes on x86). The cache must be flushed on EVERY operation declared SeqCst. Its absurdly slow, the absolute slowest memory model you can have. 3. Well-written spinlocks are absurdly fast. Benchmark them if you don't believe me. The assembly in x86 is Lock: while (AtomicExchange(spinlock, true) != false) hyperthread_yield(); // loop until you grab false. acquire_barrier(); // Prevent reordering of memory Unlock: release_barrier(); // Prevent reordering of memory. NOP on x86 but important in ARM / POWER9 spinlock=false; // Don't even need an atomic here actually Literally one assembly instruction to unlock, 3-assembly instructions to lock (the atomicexchange + loop) + hyperthread_yield if you wanna play nice with your siblings (reduces performance for you, but overall makes the whole system faster). From a cache-perspective, the spinlock will play nice with L1 cache (if a thread unlocks, then locks again before a new thread comes in, it all stays local to L1 and no cross-thread communication occurs). So pretty much every aspect of the hypothetical spinlock implementation is faster in my mind. I don't really need to benchmark to see which one is faster. EDIT: At bare minimum: because the Spinlock will be properly written using Acquire / Release half-barriers, they will be ABSOLUTELY faster than SeqCst Atomics. You'll need to use Acquire/Release Atomics if you want to "keep up" with the Acquire/Release based Spinlocks.
- zamalek 7y ago
  > the very specific assumptions of the blog post. Those assumptions can be encoded by the borrow checker, so the user of the library doesn't have to be concerned about them. When writing a library, you can lean on all the assumptions you want, so long as you don't share that burden/responsibility with the user. People use mutexes daily, most of those people likely have no knowledge about how the threading cooperation works in the kernel or the fact that the kernel assumes that you are in a user-space thread. > This kind of code should NOT be encouraged. Most lock-free code satisfies that constraint. Lock-free is like crypto: unless as a learning exercise, writing it should be avoided. It always requires many eyes and fine-tooth comb reviews.
  - deleted 7y ago
    [deleted]

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.
      - cesarb 7y ago
        > 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. There's an important difference between "queue full" and "queue not full, but locked". In the former case, you can either block (waiting for the queue to drain) or discard the data; in the later case, you must wait for the lock to be released before deciding. That is, if you allow data to be discarded when the queue is full, a lock-free queue can also be stall-free. (It might appear that a queue using a lock can also be stall-free, since the amount of work it does while locked is bounded; however that fails once the thread holding the lock is preempted by either a context switch or a hardware interrupt. To really avoid stalls in that case, you have to either block preemption and interrupts, or perhaps you might be able to make it work with some priority inheritance scheme. And yeah, I know that the hardware can "stall" while reading or updating a shared variable, but the amount of work the hardware does in that case is bounded.)
        dragontamer 7y ago
forrestthewoods 7y ago
I’d love to see a competing version with benchmarks. I’m not saying you’re wrong. But your making a lot of strong arguments without any evidence. Is 3 atomics on the same cache line a legit problem? I don’t know! But you’re gonna have to prove negative behavior for me to integrate that knowledge into my workflow.
- dragontamer 7y ago
  > Is 3 atomics on the same cache line a legit problem? This is a commonly known problem called false sharing. https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing To be fair: I don't know how these particular atomics work, maybe they're all on their own cache lines, and 192 bytes are used up for those three atomics so that things are done properly (unlikely, but possible). But atomics in my experience usually assume the "external" programmer figures out the buffering issue to prevent false sharing. 2. These are atomics declared to be SeqCst memory ordering. That means the L1 (and probably L2) caches are flushed every time you read or write to them on ARM systems. (x86 has stricter guarantees and almost "natively" implements SeqCst, so you won't have as many flushes on x86). The cache must be flushed on EVERY operation declared SeqCst. Its absurdly slow, the absolute slowest memory model you can have. 3. Well-written spinlocks are absurdly fast. Benchmark them if you don't believe me. The assembly in x86 is Lock: while (AtomicExchange(spinlock, true) != false) hyperthread_yield(); // loop until you grab false. acquire_barrier(); // Prevent reordering of memory Unlock: release_barrier(); // Prevent reordering of memory. NOP on x86 but important in ARM / POWER9 spinlock=false; // Don't even need an atomic here actually Literally one assembly instruction to unlock, 3-assembly instructions to lock (the atomicexchange + loop) + hyperthread_yield if you wanna play nice with your siblings (reduces performance for you, but overall makes the whole system faster). From a cache-perspective, the spinlock will play nice with L1 cache (if a thread unlocks, then locks again before a new thread comes in, it all stays local to L1 and no cross-thread communication occurs). So pretty much every aspect of the hypothetical spinlock implementation is faster in my mind. I don't really need to benchmark to see which one is faster. EDIT: At bare minimum: because the Spinlock will be properly written using Acquire / Release half-barriers, they will be ABSOLUTELY faster than SeqCst Atomics. You'll need to use Acquire/Release Atomics if you want to "keep up" with the Acquire/Release based Spinlocks.
zamalek 7y ago
> the very specific assumptions of the blog post. Those assumptions can be encoded by the borrow checker, so the user of the library doesn't have to be concerned about them. When writing a library, you can lean on all the assumptions you want, so long as you don't share that burden/responsibility with the user. People use mutexes daily, most of those people likely have no knowledge about how the threading cooperation works in the kernel or the fact that the kernel assumes that you are in a user-space thread. > This kind of code should NOT be encouraged. Most lock-free code satisfies that constraint. Lock-free is like crypto: unless as a learning exercise, writing it should be avoided. It always requires many eyes and fine-tooth comb reviews.
- deleted 7y ago
  [deleted]