4 ms·

This seems extremely suspicious. Of course it depends on the nature of the data structure, but in the presentation he compares an atomic increment with a non-at

This seems extremely suspicious. Of course it depends on the nature of the data structure, but in the presentation he compares an atomic increment with a non-atomic increment guarded by a spinlock and comes to the conclusion that the latter is faster for at least on one micro-architecture. Can anybody actually explain this result? The spinlock needs at least one atomic operation and a write (for lock + unlock) and one non-atomic read-modify-write per iteration while the atomic increment needs only a single atomic operation per iteration and no other memory access. How on Earth can the latter variant be slower? The only thing I can think of right now is that due to some micro-architectural idiosyncracies, the relevant cache lines end up migrating between cores more often in the atomic increment case, while in the spinlock case, the same core ends up winning the lock back-to-back more often (and so cachelines migrate less frequently which reduces the overall running time). That seems like it would most likely only ever be relevant to this kind of extremely micro benchmark, but I'd be interested to hear if there are other explanations (I haven't watched the whole talk, but at least the slides don't seem to make an attempt to explain this).

dragontamer 8y ago
Ink x86, ALL synchronization primitives are "LOCK" prefixed. That is: for the FULL Read-modify-write, the cache line is held in exclusive mode (or equivalent). Its just how the assembly code works. Furthermore, ALL loads / stores are almost strictly ordered on x86. http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.p... > Intel 64 memory ordering obeys the following principles: > 1. Loads are not reordered with other loads. > 2. Stores are not reordered with other stores. > 3. Stores are not reordered with older loads. > 4. Loads may be reordered with older stores to different locations but not with older stores to the same location. > 5. In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility). > 6. In a multiprocessor system, stores to the same location have a total order. > 7. In a multiprocessor system, locked instructions have a total order. > 8. Loads and stores are not reordered with locked instructions. As such, "relaxed atomics" DO NOT EXIST on x86. Almost everything on x86 is innately an acquire / release semantics (even non-locked stuff). ------------ As such, the optimal spinlock-unlock implementation on x86 doesn't use the LOCK prefix at all! You rely upon the memory-ordering consistently guaranteed by the x86 processor, and let the cache-coherence mechanism handle everything for you. You'll still need the "lock" to obtain the lock (writing 1 into the memory location AND reading the old value). But unlocking the lock (writing 0 into the memory location) can be done x86-LOCK-prefix free. In contrast, a CAS-atomic on x86 needs to "LOCK" the memory bus, which under x86 is specified as: > Causes the processor’s LOCK# signal to be asserted during execution of the accompanying instruction (turns the instruction into an atomic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted. So when you do a CAS-atomic on x86, in REALITY, the LOCK-prefix will be asserted, locking out all other cores from interacting with your cache line. ------------ So the cache-coherence mechanism on x86 seems sufficiently robust and well optimized by Intel / AMD, at least with our current 28-core Xeons and 32-core EPYCS. Future scaling may be an issue for Intel/AMD, and ARM / Power9 (which have true relaxed memory) may scale better eventually.
- nhaehnle 8y ago
  That's all well and good, but: > As such, the optimal spinlock implementation on x86 doesn't use the LOCK prefix at all! You rely upon the memory-ordering consistently guaranteed by the x86 processor, and let the cache-coherence mechanism handle everything for you. That's just not true. Spinlocks are not magic; they need to be implemented, and all the implementations I know of use a (atomic and therefore locked!) cmpxchg. Which makes sense. Spinlocks are a synchronization primitive, and you wrote yourself that ALL synchronization primitives on x86 are "LOCK" prefixed. So let's rephrase the original question: why should a locked cmpxchg + additional memory accesses be more efficient than a single locked increment?
  - dragontamer 8y ago
    You're right and you responded before I realized my herp-derp and made an edit. Sorry for not catching it in time! > So let's rephrase the original question: why should a locked cmpxchg + additional memory accesses be more efficient than a single locked increment? The ideal spinlock on x86 isn't a cmpxchg btw. Its a pure locked-swap. And I think there-in lies the answer. A locked-swap on x86 can theoretically execute faster (its a pure write and a pure read to the cache), while the uOps generated for a cmpxchg would include a comparison. From a cache-coherency perspective: the pure-write of a locked-swap can be implemented by invalidating the caches of every other core. So there's a "race" between cores to send out the "invalidate cache" message to everybody. Everyone who loses to the invalidate-message needs to stall and re-read the new value. But otherwise, the "winner" of locked-swap executes incredibly efficiently. The winner instantly transitions into the "Owner" state and continues to execute. But a cmpxchg is a far more complicated order of events. I'd imagine that the underlying, undocumented, cache-coherence mechanisms struggle under a LOCKed cmpxchg (which is far more common with atomic-based lockless programming). Remember, the "LOCK" prefix is implemented by the MESI protocol (or something more complicated, like MESIF on Intel or MEOSI on AMD) in reality. Even then, modern processors probably implement something far more complicated, and its unfortunate that its undocumented. Still, LOCK swap is clearly more efficient under MESI than LOCK cmpxchg. --------- A locked-increment would probably be roughly the same speed as a cmpxchg btw. Both a locked-increment and locked-cmpxchg require a full read/modify/write cycle. While a locked-swap is just a read / invalidate+write instead.

dragontamer 8y ago

Ink x86, ALL synchronization primitives are "LOCK" prefixed. That is: for the FULL Read-modify-write, the cache line is held in exclusive mode (or equivalent). Its just how the assembly code works. Furthermore, ALL loads / stores are almost strictly ordered on x86. http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.p... > Intel 64 memory ordering obeys the following principles: > 1. Loads are not reordered with other loads. > 2. Stores are not reordered with other stores. > 3. Stores are not reordered with older loads. > 4. Loads may be reordered with older stores to different locations but not with older stores to the same location. > 5. In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility). > 6. In a multiprocessor system, stores to the same location have a total order. > 7. In a multiprocessor system, locked instructions have a total order. > 8. Loads and stores are not reordered with locked instructions. As such, "relaxed atomics" DO NOT EXIST on x86. Almost everything on x86 is innately an acquire / release semantics (even non-locked stuff). ------------ As such, the optimal spinlock-unlock implementation on x86 doesn't use the LOCK prefix at all! You rely upon the memory-ordering consistently guaranteed by the x86 processor, and let the cache-coherence mechanism handle everything for you. You'll still need the "lock" to obtain the lock (writing 1 into the memory location AND reading the old value). But unlocking the lock (writing 0 into the memory location) can be done x86-LOCK-prefix free. In contrast, a CAS-atomic on x86 needs to "LOCK" the memory bus, which under x86 is specified as: > Causes the processor’s LOCK# signal to be asserted during execution of the accompanying instruction (turns the instruction into an atomic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted. So when you do a CAS-atomic on x86, in REALITY, the LOCK-prefix will be asserted, locking out all other cores from interacting with your cache line. ------------ So the cache-coherence mechanism on x86 seems sufficiently robust and well optimized by Intel / AMD, at least with our current 28-core Xeons and 32-core EPYCS. Future scaling may be an issue for Intel/AMD, and ARM / Power9 (which have true relaxed memory) may scale better eventually.

nhaehnle 8y ago
That's all well and good, but: > As such, the optimal spinlock implementation on x86 doesn't use the LOCK prefix at all! You rely upon the memory-ordering consistently guaranteed by the x86 processor, and let the cache-coherence mechanism handle everything for you. That's just not true. Spinlocks are not magic; they need to be implemented, and all the implementations I know of use a (atomic and therefore locked!) cmpxchg. Which makes sense. Spinlocks are a synchronization primitive, and you wrote yourself that ALL synchronization primitives on x86 are "LOCK" prefixed. So let's rephrase the original question: why should a locked cmpxchg + additional memory accesses be more efficient than a single locked increment?
- dragontamer 8y ago
  You're right and you responded before I realized my herp-derp and made an edit. Sorry for not catching it in time! > So let's rephrase the original question: why should a locked cmpxchg + additional memory accesses be more efficient than a single locked increment? The ideal spinlock on x86 isn't a cmpxchg btw. Its a pure locked-swap. And I think there-in lies the answer. A locked-swap on x86 can theoretically execute faster (its a pure write and a pure read to the cache), while the uOps generated for a cmpxchg would include a comparison. From a cache-coherency perspective: the pure-write of a locked-swap can be implemented by invalidating the caches of every other core. So there's a "race" between cores to send out the "invalidate cache" message to everybody. Everyone who loses to the invalidate-message needs to stall and re-read the new value. But otherwise, the "winner" of locked-swap executes incredibly efficiently. The winner instantly transitions into the "Owner" state and continues to execute. But a cmpxchg is a far more complicated order of events. I'd imagine that the underlying, undocumented, cache-coherence mechanisms struggle under a LOCKed cmpxchg (which is far more common with atomic-based lockless programming). Remember, the "LOCK" prefix is implemented by the MESI protocol (or something more complicated, like MESIF on Intel or MEOSI on AMD) in reality. Even then, modern processors probably implement something far more complicated, and its unfortunate that its undocumented. Still, LOCK swap is clearly more efficient under MESI than LOCK cmpxchg. --------- A locked-increment would probably be roughly the same speed as a cmpxchg btw. Both a locked-increment and locked-cmpxchg require a full read/modify/write cycle. While a locked-swap is just a read / invalidate+write instead.