Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
But if you have a data-structure with say, 20 ints... you have two approaches.
1. Use a mutex (which may be CAS-based under the hood) at the beginning and end: 1 lock and 1 unlock. The 20-ints are then accessed with non-atomic operations.
2. Use atomic operations on those 20-ints. But in this case, you pay the "atomics cost" each time.
In many cases, #1 may be faster than #2.
-----
Sorry for the 2nd response, but this is a different idea than what I was talking in my 1st response.
Not in the sense of flushing from cache to memory, but yes in the sense of data from a local core cache needing to be sent to another core.
Caches may be coherent but coherency is definitely not free, especially on multi-processor systems, which you probably care about if you are writing this kind of code.
The only thing that can be said to be 'flushed' by a CAS (at least on a x86 where it has full barrier semantic) is the store buffer (which is not a cache), but even there the only thing it does is simply prevent more recent loads [1] to complete before any store older or equal than the cas has completed. The store buffer is not really flushed and is still drained at the same speed it would without at cas.
[1] or any other operation for simplicity of implementation.
Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty.
I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment.
"Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty.
If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it.
----------------
Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4)
Again, I'm not an expert, but that's my understanding of how modern systems work.
-------
I looked up the Intel Architecture Manual, and they have the following table:
If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed)
In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!
The extra penalty introduced by common atomic operations that make strong guarantees about ordering is waiting for the store buffer to flush all prior stores before the result of the atomic operation is flushed out of the store buffers to L1 and then the atomic operation is flushed.
I hesitate to make generalizations about memory visibility requirements and costs as it is very API and hardware specific. Weaker guarantees exist and would have different costs.
TL;DR The total memory overhead is the same the difference is the atomic operation stalls the CPU that is performing the atomic operation unless it can speculate past it.
Also blind stores can be resolved in the background and don't block the CPU from continuing as long as the cache line is never read from.
Understanding how atomic instructions work and their effect (or lack of) on the system is important for optimizations.
Ultimately, I'm basing my viewpoint from this PDF: the "Is parallel programming Hard" free online book.
https://www.kernel.org/pub/linux/kernel/people/paulmck/perfb...
> Line 1 defines an atomic variable, line 5 atomically increments it, and line 10 reads it out. Because this is atomic, it keeps perfect count. However, it is slower: on a Intel Core Duo laptop, it is about six times slower than non-atomic increment when a single thread is incrementing, and more than ten times slower if two threads are incrementing.
The PDF changes over time. But this line can be found on page 42 at the moment.
--------
So according to the tests done by the author here, atomic operations are CERTAINLY slower, even in single-threaded cases.
I can't say I understand why they're slower, but something is definitely going on.
[1] atomic stores and loads are extremely cheap on x86.
[2] you can see that from the cost: a RMW or membar is around 20-30 clock cycles, while cross core communication costs in the order of 100s cycles.
edit: s/buffer/barrier/
I don't think it's as bad as that - I've heard it's only as expensive as hitting the L2 cache.
An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.