[C++] atomics

Reference:
https://www.youtube.com/watch?v=ZQFzMfHIxng

• Lock-free means 'FAST'
• Algorithm rules supreme
• 'Wait-free' has nothing to do with time
• Wait-free refers to the number of compute 'steps'
• Steps do not have to be of the same duration
• Atomic operations do not guarantee good performance

What types can be made atomic?

• Any trivially copyable type can be made atomic
• Continuous chunk of memory
• Copying the object means copying all bits(memcpy)
• No virtual functions, noexcept constructor
  

Operation:

std::atomic<int> x{0}; 
++x;
x++;
x += 1;
x |= 2;
int y = x * 2;
x = y + 1;

x *= 2; // no atomic multiply; not compile
x = x + 1; // not atomic; atomic read x store in the register follow by atomic write x
x = x * 2; // not atomic; atomic read x store in the register follow by atomic write x

 // same compiles to IR.
++x;
x += 1;
x = x + 1;

std::atomic<T>::load

std::atomic<T>::store

std::atomic<T>::exchange
std::atomic<T>::compare_exchange_{weak, strong}

What is so special about CAS? 

• Compare-and-swap (CAS) is used in most lock-free(not wait-free) algorithms

std::atomic x{0};
int x0 = x;

while(!x.compare_exchange_strong(x0, x0+1)){}

• even:

while(!x.compare_exchange_strong(x0, x0*2)){} // x0*2 is not atomic

Spinlock as using FUTEX with pause, slower if thread number > core number

std::atomic is not always lock free;

std::atomic<T>::is_always_lock_free; compile time

Judge at run-time due to runtime memory alignment.

Padding matters.

Cache line sharing

The size of cache-line matters.

Atomic operation do wait on each other,

• in particular, write operation do
• read-only operations can scale near-perfectly.

Be aware of NUMA architecture cache-line

Spurious wake up

https://vsdmars.blogspot.com/2024/03/c-compareexchangeweak.html

Atomic queue; lock free implement

and memory-barrier plays the role; only store and release issues memory barrier operation.

reference: 

https://vsdmars.blogspot.com/2019/06/c-c-concurrency-in-action-second.html

https://vsdmars.blogspot.com/2015/10/c-concurrent-notenote-ch5-study-note.html

https://vsdmars.blogspot.com/2018/06/c-regular-type.html

https://vsdmars.blogspot.com/2018/09/concurrency-c-wrap-up-2018.html

https://vsdmars.blogspot.com/2021/10/c-memory-model-in-depth.html

There are only 2 places need barrier:

• processing invalid queue (RMB)
• write store buffer to cache. (WMB) 

That's it, period!

CAS

Read is faster than write, keep this in mind. Thus the memory order setting is different.

For read, use more relax orders.

Default memory order

Consider memory barrier usage as a contract between engineers