5 ms·

Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into com

Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into complex algorithms so the simple lock ends up being cheaper. 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.

gpderetta 9y ago
CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
- dragontamer 9y ago
  > CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. 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: https://imgur.com/uesh8co https://imgur.com/uesh8co 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!
  - arielweisberg 9y ago
    You pay the sharing cost regardless of whether the operation used to access the cache line is atomic or guarantees visibility. At least on x86. See false sharing. 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.
    - gpderetta 9y ago
      Exactly. Understanding how atomic instructions work and their effect (or lack of) on the system is important for optimizations.
      - dragontamer 9y ago
        I mean, that's why I'm participating in the discussion. :-) 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/perfbook/perfbook.html 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.
- saas_co_de 9y ago
  > CAS don't do cache flushes. Caches are fully coherent 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.
  - gpderetta 9y ago
    CAS has no effect on the cache (other than guaranteeing that the cacheline to be in the exclusive state for the time to perform the load+op+store). CASs and other atomic RMW ops in general, in all common architectures are purely local operations that do not affect the coherency fabric (not any more than a store would, memory barriers do not even do that). 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.
- dragontamer 9y ago
  > Also any lock implementations also use a cas or equivalent internally 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.
  - gpderetta 9y ago
    Using 20 cas to update 20 ints it is probably not the best idea. There are significantly more than two approaches (seqlocks, RCU, persistent data structures, etc). Which one works best depends on the actual use case.
chrisseaton 9y ago
> having to do a cache flush for every atomic operation I don't think it's as bad as that - I've heard it's only as expensive as hitting the L2 cache.

gpderetta 9y ago

CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).

dragontamer 9y ago
> CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. 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: https://imgur.com/uesh8co https://imgur.com/uesh8co 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!
- arielweisberg 9y ago
  You pay the sharing cost regardless of whether the operation used to access the cache line is atomic or guarantees visibility. At least on x86. See false sharing. 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.
  - gpderetta 9y ago
    Exactly. Understanding how atomic instructions work and their effect (or lack of) on the system is important for optimizations.
    - dragontamer 9y ago
      I mean, that's why I'm participating in the discussion. :-) 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/perfbook/perfbook.html 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.
saas_co_de 9y ago
> CAS don't do cache flushes. Caches are fully coherent 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.
- gpderetta 9y ago
  CAS has no effect on the cache (other than guaranteeing that the cacheline to be in the exclusive state for the time to perform the load+op+store). CASs and other atomic RMW ops in general, in all common architectures are purely local operations that do not affect the coherency fabric (not any more than a store would, memory barriers do not even do that). 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.
dragontamer 9y ago
> Also any lock implementations also use a cas or equivalent internally 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.
- gpderetta 9y ago
  Using 20 cas to update 20 ints it is probably not the best idea. There are significantly more than two approaches (seqlocks, RCU, persistent data structures, etc). Which one works best depends on the actual use case.

chrisseaton 9y ago

> having to do a cache flush for every atomic operation I don't think it's as bad as that - I've heard it's only as expensive as hitting the L2 cache.