atomic operation cost

by

I have looked for actual data for the past days, and found nothing.
However, I did some research, which compares the cost of atomic ops with the costs of cache misses.

The cost of the x86 LOCK prefix, (including lock cmpxchg for atomic CAS), before PentiumPro (as described in the doc), is a memory access (like a cache miss), + stopping memory operations by other processors, + any contention with other processors trying to LOCK the bus. However, since PentiumPro, for normal Writeback cacheable memory (all memory an app deals with, unless you talk directly with hardware), instead of blocking all memory operations, only the relevant cache line is blocked (based on the link in @osgx’s answer).

i.e. the core delays answering MESI share and RFO requests for the line until after the store part of the actual locked operation. This is called a “cache lock”, and only affects that one cache line. Other cores can be loading / storing or even CASing other lines at the same time.

Actually, the CAS case can be more complicated, as explained on this page, with no timings but an insightful description by a trustworthy engineer. (At least for the normal use-case where you do a pure load before the actual CAS.)

Before going into too much detail, I’ll say that a LOCKed operation costs one cache miss + the possible contention with other processor on the same cacheline, while CAS + the preceding load (which is almost always required except on mutexes, where you always CAS 0 and 1) can cost two cache misses.

He explains that a load + CAS on a single location can actually cost two cache misses, like Load-Linked/Store-Conditional (see there for the latter). His explaination relies on knowledge of the MESI cache coherence protocol. It uses 4 states for a cacheline: M(odified), E(xclusive), S(hared), I(nvalid) (and therefore it’s called MESI), explained below where needed. The scenario, explained, is the following:

  • the LOAD causes a cache miss – the relevant cacheline is loaded from memory in Shared state (i.e. other processors are still allowed to keep that cacheline in memory; no changes are allowed in this state). If the location is in memory, this cache miss is skipped. Possible cost: 1 cache miss. (skipped if the cacheline is in Shared, Exclusive or Modified state, i.e. the data is in this CPU’s L1 cache).
  • the program calculates the new values to store,
  • and it runs an atomic CAS instruction.
    • It has to avoid concurrent modification, so it must remove copies of the cacheline from the cache of other CPUs, to move the cacheline to the Exclusive state. Possible cost: 1 cache miss. This is not needed if it is already exclusively owned, i.e. in the Exclusive or Modified state. In both states, no other CPUs hold the cacheline, but in the Exclusive state it has not been modified (yet).
    • After this communication, the variable is modified in our CPU’s local cache, at which point it is globally visible to all other CPUs (because their caches are coherent with ours). It will eventually be written to main memory according to usual algorithms.
    • Other processors trying to read or modify that variable will first have to obtain that cacheline in Shared or Exclusive mode, and to do so will contact this processor and receive the updated version of the cacheline.
      A LOCKed operation, instead, can only cost a cache miss (because the cacheline will be requested directly in Exclusive state).

In all cases, a cacheline request can be stalled by other processors already modifying the data.

More Related Contents:

  1. Why is the loop instruction slow? Couldn’t Intel have implemented it efficiently?
  2. Enhanced REP MOVSB for memcpy
  3. How many CPU cycles are needed for each assembly instruction?
  4. Adding a redundant assignment speeds up code when compiled without optimization
  5. Is performance reduced when executing loops whose uop count is not a multiple of processor width?
  6. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  7. Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths
  8. How are x86 uops scheduled, exactly?
  9. Why does breaking the “output dependency” of LZCNT matter?
  10. What happens after a L2 TLB miss?
  11. What setup does REP do?
  12. Are there any modern CPUs where a cached byte store is actually slower than a word store?
  13. 32-byte aligned routine does not fit the uops cache
  14. Size of store buffers on Intel hardware? What exactly is a store buffer?
  15. Avoid stalling pipeline by calculating conditional early
  16. Lost Cycles on Intel? An inconsistency between rdtsc and CPU_CLK_UNHALTED.REF_TSC
  17. Why is a conditional move not vulnerable to Branch Prediction Failure?
  18. Assembly – How to score a CPU instruction by latency and throughput
  19. Why is division more expensive than multiplication?
  20. Latency bounds and throughput bounds for processors for operations that must occur in sequence
  21. Cycles/cost for L1 Cache hit vs. Register on x86?
  22. Why is my Rust program slower than the equivalent Java program?
  23. Clear file cache to repeat performance testing
  24. What’s the (hidden) cost of Scala’s lazy val?
  25. Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
  26. Is Mongodb Aggregation framework faster than map/reduce?
  27. Fast vectorized rsqrt and reciprocal with SSE/AVX depending on precision
  28. Speed-efficient classification in Matlab
  29. Performance of using static methods vs instantiating the class containing the methods
  30. Is a memory barrier required to read a value that is atomically modified?

Leave a Comment