3 ms·
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 c
by 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...
- gpderetta 8y agoYes I was specifically talking about x86 CAS which is wait free. Still (but don't quote me on this because I'm no Power expert), IIRC Power actually does guarantee, via idiom recognition, that specific uses of LL/SC are wait free by downgrading it internally to an actual CAS after a number of failures, so a compare_exchange_strong which loops a bounded number of times can be implemented on this architecture.