3 ms·

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 cons

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.
- nhaehnle 8y ago
  Okay, it's a fair point that '(lock) xchg' can potentially be faster than 'lock cmpxchg'. I wouldn't say it's really an ideal spinlock, because under real loads there are other considerations. That's why the Linux kernel uses queued spinlocks, for example. For various reasons I still suspect that some other factor is at play, but I also don't really know how to tease that out. Maybe there are some performance counters one could look at, but I'm just speculating.
- gpderetta 8y ago
  IIRC the reason that xchg is faster than a CAS is that the idiomatic CAS code would read the current value of the cell and then execute a CAS. This causes the cacheline to first be brought in shared mode, and then to be upgraded to exclusive, requiring an additional coherency transaction. A plain exchange would simply bring the cacheline in exclusive mode directly. If the lock is uncontenced thus can be noticeably faster. But note that this is not a property of the operation itself but simply of the surrounding code: issuing a blind cas with a speculative initial value can have similar performance characteristics of a xchg. On the other hand, if the spin lock is contended, avoiding an unconditionally acquiring the cacheline in exclusive mode is beneficial as it will mitigate cacheline ping pong. Thus the test-and-test-and-set idiom. On the third hand,if the lock is contended, a spin lock is probably inappropriate... Also I want to mention that CAS can fail, while xchg always succeeds, but the performance implications are not clear cut: for example a spin lock will issue xchg in a loop (failure is encoded at higher level), while wait free algos can issue cas outside of loops as a failed cas implies that another cas succeded and thus carries information.
  - dragontamer 8y ago
    > while wait free algos can issue cas outside of loops as a failed cas implies that another cas succeded and thus carries information. You almost had a perfect post IMO :-) But this last line is incorrect on some systems. x86 CAS seems to be strong as you imply. But apparently, Power9 or ARM CAS can have spurious failures. Or more appropriately, Power9 and ARM implement "Load Linked / Store Conditional", which can have spurious failures, and thus compare-and-swap (at a higher-level, like in C++ or C) will look like a CAS failed spuriously. Which is why atomic_compare_exchange_weak and atomic_compare_exchange_strong exists. Weak doesn't "hold information" due to the potential of spurious failures, but can be a more efficient implementation in the case of LL/SC instructions. http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_family#POWERPC http://liblfds.org/mediawiki/index.php?title=Article:CAS_and...

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.

nhaehnle 8y ago
Okay, it's a fair point that '(lock) xchg' can potentially be faster than 'lock cmpxchg'. I wouldn't say it's really an ideal spinlock, because under real loads there are other considerations. That's why the Linux kernel uses queued spinlocks, for example. For various reasons I still suspect that some other factor is at play, but I also don't really know how to tease that out. Maybe there are some performance counters one could look at, but I'm just speculating.
gpderetta 8y ago
IIRC the reason that xchg is faster than a CAS is that the idiomatic CAS code would read the current value of the cell and then execute a CAS. This causes the cacheline to first be brought in shared mode, and then to be upgraded to exclusive, requiring an additional coherency transaction. A plain exchange would simply bring the cacheline in exclusive mode directly. If the lock is uncontenced thus can be noticeably faster. But note that this is not a property of the operation itself but simply of the surrounding code: issuing a blind cas with a speculative initial value can have similar performance characteristics of a xchg. On the other hand, if the spin lock is contended, avoiding an unconditionally acquiring the cacheline in exclusive mode is beneficial as it will mitigate cacheline ping pong. Thus the test-and-test-and-set idiom. On the third hand,if the lock is contended, a spin lock is probably inappropriate... Also I want to mention that CAS can fail, while xchg always succeeds, but the performance implications are not clear cut: for example a spin lock will issue xchg in a loop (failure is encoded at higher level), while wait free algos can issue cas outside of loops as a failed cas implies that another cas succeded and thus carries information.
- dragontamer 8y ago
  > while wait free algos can issue cas outside of loops as a failed cas implies that another cas succeded and thus carries information. You almost had a perfect post IMO :-) But this last line is incorrect on some systems. x86 CAS seems to be strong as you imply. But apparently, Power9 or ARM CAS can have spurious failures. Or more appropriately, Power9 and ARM implement "Load Linked / Store Conditional", which can have spurious failures, and thus compare-and-swap (at a higher-level, like in C++ or C) will look like a CAS failed spuriously. Which is why atomic_compare_exchange_weak and atomic_compare_exchange_strong exists. Weak doesn't "hold information" due to the potential of spurious failures, but can be a more efficient implementation in the case of LL/SC instructions. http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_family#POWERPC http://liblfds.org/mediawiki/index.php?title=Article:CAS_and...