Windyland serving my blog

Some notes on atomic operations

Atomic operations are quite useful in concurrent programming, notably in the implementations of lock-free algorithms. Many times when the locking algorithms goes to the performance bottleneck, atomic operations come to save.

Atomic ordering

  • NotAtomic (regular load and store)
  • Unordered (to match java safe language memory model)
  • Monotinic (or memory_order_relaxed)
  • Acquire (or memory_order_acquire and memory_order_consume)
  • Release (or memory_order_release)
  • AcuireRelease (or memory_oder_acq_rel)
  • SquentiallyConsistent (or memory_order_seq_cst)

Platforms implementations

X86

all atomic loads generate a MOV and SquentiallyConsistent stores generate an XCHG, other stores generate a MOV.

on ARM (before v8) and MIPS

Acquire, Release and SquentiallyConsistent requires barrier instructions for every such operation. Loads and stores generate normal instructions.

Language Standard and Compiler, library implementations

  • The new C++11 atomic header and C11 stdatomic.h header
  • Java-style volatile variables (match SquentiallyConsistent)
  • gcc __sync_* builtins (match SquentiallyConsistent)

if you want to use atomic operations before sticking to the new standards, there are compiler builtins functions and libraries availabe to call proper asm instructions to do these atomic operations.

gcc atomic operations Built-in Functions:

__atomic_init
__atomic_thread_fence
__atomic_signal_fence
__atomic_is_lock_free
__atomic_store
__atomic_load
__atomic_exchange
__atomic_compare_exchange_strong
__atomic_compare_exchange_weak
__atomic_fetch_add
__atomic_fetch_sub
__atomic_fetch_and
__atomic_fetch_or
__atomic_fetch_xor

A Small Benchmark

I wrote a small program to benchmark the performance of atomic operations against mutexes and spinlocks. It is hosted at GitHub.. You can clone the repository and execute make. It requires a modern c++ compiler with c++11 support.

this sample output is on my 4-cores 2013-late Macbook Pro:

jobs:  1 total time:  614932094 ns average time:  6149 ns (Mutex)
jobs:  1 total time:    5132226 ns average time:    51 ns (SpinLock)
jobs:  1 total time:    4172785 ns average time:    41 ns (Atomic)
jobs:  2 total time:  746401303 ns average time:  7464 ns (Mutex)
jobs:  2 total time:   15983439 ns average time:   159 ns (SpinLock)
jobs:  2 total time:    9356120 ns average time:    93 ns (Atomic)
jobs:  4 total time:   42609222 ns average time:   426 ns (SpinLock)
jobs:  4 total time:   13734551 ns average time:   137 ns (Atomic)
jobs:  8 total time:  107958834 ns average time:  1079 ns (SpinLock)
jobs:  8 total time:   30681228 ns average time:   306 ns (Atomic)
jobs: 16 total time:  213277915 ns average time:  2132 ns (SpinLock)
jobs: 16 total time:   52189737 ns average time:   521 ns (Atomic)

Future Reading