Atomics and memory ordering

std::atomic<T> guarantees two things about the variable itself: every access is indivisible, so no thread sees half a write, and accesses from different threads do not form a data race. For T up to 8 bytes (16 on some platforms), atomics compile to ordinary instructions or locked instructions with no lock object; is_lock_free() tells you.

What an atomic says about other memory, the quote in the slot, depends on the memory order you choose. That is the part interviews are about.

Quote slot;
std::atomic<bool> ready{false};

// producer                              // consumer
slot = q;                                while (!ready.load(/* ? */)) {}
ready.store(true, /* ? */);              use(slot);

The danger: either the compiler or the processor could make the store to ready visible before the store to slot, or let the consumer's read of slot happen before its read of ready. The consumer would then see ready == true and read an old or half-written quote.

The fix is a matching pair:

slot = q;
ready.store(true, std::memory_order_release);   // nothing before this may move after it

while (!ready.load(std::memory_order_acquire)) {}   // nothing after this may move before it
use(slot);

A release store guarantees that every read and write the thread made before it becomes visible no later than the store itself. An acquire load guarantees that every read and write after it happens after the load. When an acquire load reads the value written by a release store, the two synchronise: everything the producer did before the store is visible to the consumer after the load. That is exactly the publication guarantee, and it is all most lock-free code needs.

(memory_order_consume exists but compilers treat it as acquire; ignore it.)

seq_cst is what you get if you write ready = true or ready.load() without arguments. It is the easiest to reason about and the strongest. The extra guarantee matters in patterns like Dekker's mutual exclusion, where each thread stores to its own flag and then loads the other's: with release and acquire only, both threads can read the other's flag as false.

On x86, ordinary loads already behave as acquire and ordinary stores as release (the hardware model is called total store order). So acquire loads, release stores and relaxed accesses all compile to plain mov instructions, and the orderings only constrain the compiler. The one expensive case is a seq_cst store, which compiles to xchg or mov plus mfence to stop it being reordered with a later load. Read-modify-writes like fetch_add are lock-prefixed instructions at any ordering.

On ARM and POWER, the hardware reorders much more freely, so acquire and release compile to special load and store instructions or barriers, and the difference between relaxed and stronger orders is real.

That has a practical consequence: a race with the wrong ordering may never show up on an x86 development machine and fail on ARM. Get the ordering right by reasoning, not by testing on x86.

Most lock-free algorithms need to update a value only if it has not changed since they read it:

std::atomic<std::int64_t> best_bid{0};

void offer(std::int64_t px) {
    std::int64_t cur = best_bid.load(std::memory_order_relaxed);
    while (px > cur &&
           !best_bid.compare_exchange_weak(cur, px, std::memory_order_release, std::memory_order_relaxed)) {
        // on failure, cur has been reloaded with the current value; the loop re-tests px > cur
    }
}

compare_exchange_weak may fail spuriously even if the value matched, which lets it compile to a cheaper instruction pair on ARM; it belongs in a loop. compare_exchange_strong fails only on a real mismatch, for single attempts. Under heavy contention, many threads retrying a CAS on one cache line scale badly, which is a reason to avoid shared hot atomics altogether (Module 5).

The producer's store to ready must be a release, so the write of the slot cannot become visible after it. The consumer's load must be an acquire, so the read of the slot cannot happen before it. When the acquire reads the release's value, everything written before the release is visible after the acquire. On x86 both are plain moves and only stop compiler reordering; on ARM they emit the needed barriers. seq_cst would also be correct, just stronger than needed.