atomics and CAS

the picture

two people editing one shared doc with a "save only if nobody else saved since you opened it" button. you open version 5, make your edit, hit save. if it's still version 5, your save goes through. if someone else saved version 6 in the meantime, the button refuses, and you reopen and redo your edit on top of theirs. nobody ever waits for a lock on the doc, and nobody's work silently disappears.

that button is CAS. on x86 it's lock cmpxchg; on ARM it's cas (or a load-exclusive / store-exclusive pair). the hardware makes the compare and the swap one indivisible step.

the CAS loop

last time, count++ lost updates because the write blindly overwrote whatever was there. here's the same three steps with the blind write swapped for compareAndSet:

written out by hand, that's this loop. it's lock-free: some thread always makes progress, because a CAS only fails when another thread's CAS succeeded.

import java.util.concurrent.atomic.AtomicInteger;
 
int increment(AtomicInteger count) {
    while (true) {
        int current = count.get();
        int next = current + 1;
        if (count.compareAndSet(current, next)) {
            return next;
        }
        // someone else changed it between get() and compareAndSet(): go again
    }
}
 
void main() throws InterruptedException {
    AtomicInteger count = new AtomicInteger();
    Runnable work = () -> {
        for (int i = 0; i < 1_000_000; i++) increment(count);
    };
    Thread a = new Thread(work);
    Thread b = new Thread(work);
    a.start();
    b.start();
    a.join();
    b.join();
    IO.println(count.get());
}

2000000

you'd never write that loop for a counter, because AtomicInteger already has it. the API is small:

import java.util.concurrent.atomic.AtomicInteger;
 
void main() {
    AtomicInteger n = new AtomicInteger(5);
    IO.println(n.incrementAndGet());              // 6: add, then return
    IO.println(n.getAndIncrement());              // 6: return, then add
    IO.println(n.compareAndSet(7, 100));          // true: it was 7
    IO.println(n.compareAndSet(7, 200));          // false: it's 100 now
    IO.println(n.updateAndGet(x -> x * 2));       // 200
    IO.println(n.accumulateAndGet(5, Math::max)); // 200
}

6
6
true
false
200
200

updateAndGet and accumulateAndGet run your function inside the retry loop, which means your function can run more than once. keep it pure: no printing, no I/O, no side effects.

the family, quickly:

every atomic read and write also has volatile semantics, so everything from the memory model chapter applies: a successful CAS publishes whatever the thread wrote before it.

when CAS gets crowded: LongAdder

a CAS loop is cheap when it usually succeeds. with eight threads hammering one AtomicLong, every core is fighting over the same cache line: it bounces between cores on every update, and the more threads, the more of them are waiting for it at any moment.

LongAdder cheats. it keeps a base plus an array of cells. while there's no contention, it CASes base like an AtomicLong. the first time a CAS on base fails, it creates the cells, and from then on each thread adds into its own cell (picked by a per-thread hash). collide with someone in a cell, and the thread rehashes to a different one; keep colliding, and the array doubles, up to about the number of cores. sum() adds them all up.

the real thing, measured. each thread increments 10 million times, median of 7 runs on jdk 25 on a 14-core arm mac (plain wall-clock timing, not a JMH benchmark, so read the ratios, not the digits):

with one thread the order flipped: synchronized 9 ms, AtomicLong 16 ms, LongAdder 42 ms. no contention means no reason for cells, just more work per increment. so:

• many writers, rare reads (request counters, metrics): LongAdder.
• you need the exact current value in a decision (if (count.incrementAndGet() > limit)), or a sequence number: AtomicLong. LongAdder.sum() is a moving target while writers are still writing.

the ABA problem

CAS asks "is it still A?", not "has anything happened since I looked?". if a value goes A → B → A while you weren't looking, your CAS can't tell, and succeeds. for an int counter that's harmless. for a pointer in a lock-free data structure, it can be a disaster:

the fix is to compare a version along with the value. AtomicStampedReference pairs the reference with an int stamp, and you bump the stamp on every change. A with stamp 0 and A with stamp 2 are not equal:

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;
 
void main() {
    AtomicReference<String> top = new AtomicReference<>("A");
    String seen = top.get();                         // T1 reads A, then stalls
    top.set("B");                                    // meanwhile: A → B
    top.set("A");                                    //            B → A
    IO.println(top.compareAndSet(seen, "C"));        // T1's CAS can't tell
 
    AtomicStampedReference<String> stamped = new AtomicStampedReference<>("A", 0);
    int[] stamp = new int[1];
    String seen2 = stamped.get(stamp);               // reads A and stamp 0
    stamped.compareAndSet("A", "B", 0, 1);           // A → B, stamp 1
    stamped.compareAndSet("B", "A", 1, 2);           // B → A, stamp 2
    IO.println(stamped.compareAndSet(seen2, "C", stamp[0], stamp[0] + 1));
}

true
false

in practice java dodges most of ABA for free: the classic version needs a node to be freed and reused, and the garbage collector won't recycle a node while T1 still holds a reference to it. it bites when you pool and reuse objects yourself, or CAS on values (like ints) that can legitimately come back around.