6 ms·

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

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.
- vardump 7y ago
  > spinlock=false; // Don't even need an atomic here actually No, you'll need a memory barrier there. On x86, sure you get away for free, because x86 memory model says stores are never reordered with other stores. On practically all other systems you'll need equivalent of C++ atomic "memory_order::release" to prevent stores from being reordered with other stores. Otherwise you're in for a surprise. Without a (half) barrier, it'll be buggy on ARM, POWER, MIPS, etc. Edit: I see you added the barriers. Sneaky. :)
  - dragontamer 7y ago
    Yes, good point. The obscure details are always hard to remember... that particular example is x86 specific. I probably should edit in the memory barriers. > Edit: I see you added the barriers. Sneaky. :) You reminded me about them. Lol. Thanks for the reminder :-)
    - vardump 7y ago
      Hmm... are you sure your unlock barrier is in the right place? ;-) Edit: I see you fixed that too.
      - dragontamer 7y ago
        Uhhh... now it is :-) This stuff is always hard...
        vardump 7y ago
        If you still wanted to fine tune it a bit further, you could have used a WeakAtomicExchange (?). Performs better on some systems, and a strong one is not required here. On x86, it's of course same.
        dragontamer 7y ago
        Ha! I think I'm finally correct against you :-) "AtomicExchange" is just a swap. It is NOT a compare-and-swap, so there's no Weak vs Strong version. A pure-swap is probably faster to implement than a compare-and-swap in microcode, but I admit that I've never actually tested this theory.
vardump 7y ago
If there's contention between multiple CPU cores (and worse, sockets), 3 atomic ops on same cache line puts the max throughput to 3-15M operations per second per system. Probably around 10M on most 2-4 core CPUs. Multi CPU-socket systems will be slower. That is, the point when the whole computer is on its knees due to cache coherency traffic between cores. Note: these are just ballpark figures based on real life experience on modernish x86-64 systems. Your mileage may vary. Always measure actual performance. Etc.
BubRoss 7y ago
64 bytes is the false sharing boundary of modern Intel CPUs. Heavily contentious variables will produce different synch behavior if they are not in the same 64 byte segment. This is documented in Intel's CPU manuals.

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.

vardump 7y ago
> spinlock=false; // Don't even need an atomic here actually No, you'll need a memory barrier there. On x86, sure you get away for free, because x86 memory model says stores are never reordered with other stores. On practically all other systems you'll need equivalent of C++ atomic "memory_order::release" to prevent stores from being reordered with other stores. Otherwise you're in for a surprise. Without a (half) barrier, it'll be buggy on ARM, POWER, MIPS, etc. Edit: I see you added the barriers. Sneaky. :)
- dragontamer 7y ago
  Yes, good point. The obscure details are always hard to remember... that particular example is x86 specific. I probably should edit in the memory barriers. > Edit: I see you added the barriers. Sneaky. :) You reminded me about them. Lol. Thanks for the reminder :-)
  - vardump 7y ago
    Hmm... are you sure your unlock barrier is in the right place? ;-) Edit: I see you fixed that too.
    - dragontamer 7y ago
      Uhhh... now it is :-) This stuff is always hard...
      - vardump 7y ago
        If you still wanted to fine tune it a bit further, you could have used a WeakAtomicExchange (?). Performs better on some systems, and a strong one is not required here. On x86, it's of course same.
        dragontamer 7y ago
        Ha! I think I'm finally correct against you :-) "AtomicExchange" is just a swap. It is NOT a compare-and-swap, so there's no Weak vs Strong version. A pure-swap is probably faster to implement than a compare-and-swap in microcode, but I admit that I've never actually tested this theory.

vardump 7y ago

If there's contention between multiple CPU cores (and worse, sockets), 3 atomic ops on same cache line puts the max throughput to 3-15M operations per second per system. Probably around 10M on most 2-4 core CPUs. Multi CPU-socket systems will be slower. That is, the point when the whole computer is on its knees due to cache coherency traffic between cores. Note: these are just ballpark figures based on real life experience on modernish x86-64 systems. Your mileage may vary. Always measure actual performance. Etc.

BubRoss 7y ago

64 bytes is the false sharing boundary of modern Intel CPUs. Heavily contentious variables will produce different synch behavior if they are not in the same 64 byte segment. This is documented in Intel's CPU manuals.