Atomic operations & CAS

Why count++ breaks

Compile count++ and you get roughly three machine steps. Line them up for two threads on the unluckiest possible schedule and the damage is obvious:

• T1 reads count → its private copy holds 0.
• T2 reads count → its private copy also holds 0. Both threads now have the same stale snapshot.
• T1 adds 1 in its own copy → 1. T2 adds 1 in its own copy → 1. Neither has touched shared memory yet.
• T1 writes 1. T2 writes 1 — on top of it. Two increments happened, count says 1. One update is gone, and nothing crashed, so nothing tells you.

The CAS retry loop

CAS on its own only reports a conflict — it doesn't resolve one. The pattern that resolves it is a tiny loop, and it is the same four lines in every language:

// The canonical CAS retry loop — this IS what incrementAndGet() does inside.
while (true) {
    int current = count.get();                     // 1. READ  ("I'm on version 7")
    int next    = current + 1;                     // 2. COMPUTE (private, no sharing)
    if (count.compareAndSet(current, next)) {      // 3. SWAP IF UNCHANGED (atomic)
        return next;                               //    won the race — done
    }
    // 4. someone wrote first: the swap did nothing.
    //    Loop, re-read the FRESH value, redo the work on top of it.
}

Read that loop against the wiki analogy and every line has a twin: get() is opening the page and noting version 7, current + 1 is typing your edit into your own copy, compareAndSet is hitting Save with "based on version 7", and the loop is being shown the fresh page and redoing your edit. The crucial detail is step 4: on failure you must re-read. Retrying with the same stale current would fail forever.

Lock-free and optimistic

This style is called optimistic because it assumes conflicts are rare and only checks for one at write time — the opposite of a lock, which pessimistically blocks everyone up front just in case. It is also lock-free: no thread is ever parked, no thread ever waits on another, and the operating system never has to suspend and re-schedule anyone. Two consequences fall straight out of that. First, no deadlock — you can't deadlock if nobody ever holds anything. Second, no priority inversion or convoying — a thread that gets descheduled mid-loop cannot block anyone else, because it holds nothing. The system as a whole always makes progress: every failed CAS means some other thread succeeded.

When CAS beats a lock — and when it loses

• CAS wins for short updates to a single variable — counters, sequence numbers, flags, a head pointer — under low-to-moderate contention. The whole operation is a handful of instructions with no trip into the kernel, so it's dramatically cheaper than acquiring a mutex.
• CAS loses under heavy contention. Every failed attempt is thrown-away work, and it burns CPU while spinning. With dozens of threads hammering one counter, a lock (which parks losers instead of spinning them) or a striped counter like LongAdder (which spreads writes across many cells) wins comfortably.
• CAS can't do multi-variable updates. It protects exactly one memory word. If you must move money from balanceA to balanceB, or keep head and size consistent, two atomics are not an atomic pair — another thread can observe the state between them. Use a lock, or pack the fields into one immutable object and CAS the reference to it (AtomicReference).
• CAS loses when the work is long. If computing the new value is expensive, a failed retry wastes a lot of it. Locks are better when the critical section is big.

The ABA problem

CAS compares values, not histories — and that gap has a name. Suppose T1 reads a value A and then gets descheduled. While it sleeps, T2 changes the value to B, does some work, and then changes it back to A. T1 wakes up, does its compareAndSet(A, C), sees A sitting there, concludes "nothing changed", and succeeds — even though the world moved on underneath it. For a plain integer counter that's usually harmless; for a pointer in a lock-free stack it's a real bug, because the A you're looking at may be a recycled node that's already been freed and reallocated.

Atomics also fix visibility

Lost updates aren't the only hazard. Without synchronisation, a value one thread writes may sit in a CPU cache or register and simply never become visible to another thread — the reader can spin forever on a stale copy. Atomic classes solve this too: in Java, reads and writes on an AtomicInteger have the same memory-ordering guarantees as volatile, so a write by one thread happens-before a subsequent read by another. In C++ you can even choose the strength (memory_order_seq_cst by default, relaxed if you only need atomicity and not ordering). So an atomic gives you two things at once: an indivisible update and a guarantee that everyone sees it.

Reach for an atomic when...

• One variable, short update — a hit counter, a sequence/ID generator, a running total, a shutdown flag. AtomicLong, std::atomic<int>, atomic.Int64: cheaper than a mutex and impossible to deadlock.
• Contention is low to moderate — most attempts succeed on the first try, so you almost never pay for a retry.
• You need lock-free progress — real-time or latency-sensitive code where a thread being descheduled while holding a lock would stall everyone else.
• You're doing optimistic concurrency higher up — a version column, an ETag, a document revision. Same loop, bigger scale.

Take a lock instead when...

• Several fields must change together — two atomics are not an atomic pair. Transfer between two balances, or keep head and size in step, and you need one critical section (or one immutable object CAS'd through an AtomicReference).
• Contention is heavy — dozens of threads on one hot word means mostly wasted retries and burnt CPU. Use a lock, or stripe with LongAdder / per-thread counters.
• The update is expensive — a long computation thrown away on every failed CAS costs far more than briefly blocking.
• Correctness depends on recycled identity — lock-free pointer structures need an ABA guard (AtomicStampedReference, tagged pointers, hazard pointers). If that sounds fiddly, that's the signal to use a battle-tested concurrent collection instead of hand-rolling one.