Atomics and lock-free thinking

A lock makes other threads wait. An atomic makes them retry. For a single variable — a counter, a flag, a reference — that difference is the difference between a queue of parked threads and a tight loop that almost always succeeds on the first try. The mechanism underneath is one CPU instruction, and once you see it, AtomicInteger, ConcurrentHashMap, LongAdder and every lock-free structure make sense. This lesson is that instruction, what it costs when many cores fight over one cache line, and the two traps (non-pure update functions, and ABA) that lock-free code has and locked code does not.

#Compare-and-swap

CAS(address, expected, newValue):
    atomically: if *address == expected { *address = newValue; return true } else { return false }

Every modern CPU has this instruction (lock cmpxchg on x86, ldxr/stxr load-linked/store-conditional on ARM). It reads a memory location, compares it to a value you expected, and writes a new value only if the comparison held — all in one uninterruptible step. If another thread changed the value in between, the CAS fails and you learn it did.

An increment built on CAS:

int incrementAndGet(AtomicInteger a) {
    while (true) {
        int current = a.get();
        int next = current + 1;
        if (a.compareAndSet(current, next)) return next;   // succeeded: nobody interfered
        // failed: someone else wrote; loop and try again with the fresh value
    }
}

No lock, no parking, no OS involvement. Under low contention the loop runs once. Under heavy contention threads spin and retry — which is why "lock-free" is not "free": it trades blocking for wasted work, and at extreme contention a lock can win.

#Under the hood: what the CPU does

A CAS is only atomic because the core performing it takes exclusive ownership of the cache line for the duration. The cache coherence protocol (MESI and its relatives) lets one core hold a line in Modified state at a time; every other core's copy is invalidated, and a core that wants the line next must fetch it from the owner, which costs 40 to 100 nanoseconds across a socket. So the true unit of contention is not the variable but the 64-byte line it lives in, and this has three consequences:

• A contended atomic ping-pongs one line between cores. Sixteen cores incrementing one AtomicLong spend most of their time waiting for the line to arrive. Throughput per core falls as cores are added; total throughput can be lower than with one core.
• False sharing. Two unrelated atomics in adjacent fields share a line, and threads updating different variables contend as if they were the same one. @jdk.internal.vm.annotation.Contended (used inside the JDK; -XX:-RestrictContended lets applications use it) pads a field out to its own line. LongAdder pads every cell for this reason.
• getAndAdd is not a CAS loop on x86. AtomicInteger.getAndIncrement() compiles to lock xadd, a fetch-and-add instruction that always succeeds; there is no retry. The CAS loop is what updateAndGet and accumulateAndGet use, because an arbitrary function cannot be expressed as one instruction. On ARM both are LL/SC loops.

All of this reaches Java through VarHandle (Java 9), which replaced the sun.misc.Unsafe calls the atomics were originally built on. AtomicInteger.compareAndSet is a VarHandle.compareAndSet on the value field; you can write the same thing against any field of your own class, which is how the JDK's own structures avoid an AtomicInteger object per field.

#The atomic classes

AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference<V>, and array variants. All give volatile visibility plus atomic read-modify-write:

AtomicLong requests = new AtomicLong();
requests.incrementAndGet();
requests.addAndGet(5);
requests.getAndSet(0);                                    // read and reset, atomically
requests.updateAndGet(n -> Math.min(n + 1, LIMIT));        // arbitrary function, retried on conflict
requests.accumulateAndGet(delta, Long::sum);
 
AtomicReference<Config> config = new AtomicReference<>(initial);
config.updateAndGet(c -> c.withTimeout(Duration.ofSeconds(5)));   // swap an immutable snapshot

updateAndGet is the CAS loop from above with your function in the middle. The function may run more than once if there is contention, so it must be pure — no side effects, no I/O, nothing you would mind repeating. AtomicReference with an immutable value is the lock-free version of "replace the whole snapshot", and it composes with records: state.updateAndGet(s -> s.withCount(s.count() + 1)).

#Walkthrough: the counter that got slower with more cores

A metrics endpoint counted requests in an AtomicLong and reported it every ten seconds. Fine at 4 cores. At 32 cores under load, the service's CPU went up and throughput went down, and the profiler showed 12% of all cycles in AtomicLong.incrementAndGet. What happened, in order:

1. Thirty-two threads increment one field. Each lock xadd needs the cache line exclusively; the line moves between cores at roughly 70 ns per hop.
2. At a million increments per second, the line hops a million times: 70 ms of every second, spread across cores that each stall while waiting. Each core also stalls its pipeline on the lock prefix.
3. The number itself was read once every ten seconds. A million contended writes to serve one read.
4. LongAdder replaced it. Each thread now increments its own padded cell (the class starts with one and adds cells when it detects contention through failed CASes). No line moves between cores on the write path. sum() reads all cells once every ten seconds and adds them, which is the cheap direction.
5. CPU in the counter dropped below 0.1%. The count is still exact; what changed is that sum() is not atomic with respect to concurrent increments, which for a metric is irrelevant.

The rule that generalises: write-heavy, read-rare counters want striping; read-heavy or exact-on-read values want a single atomic.

#When a counter is hot: LongAdder

LongAdder spreads the value across several cells — each thread hits a different one — and sums them on sum(). Increments scale; reads are slightly more expensive and not atomic with respect to concurrent increments. It is the right type for metrics counters, hit/miss counts, anything written often and read rarely. LongAccumulator is the same idea with a custom operation (max, say). Micrometer's counters and ConcurrentHashMap.size() are both built on this idea.

#The ABA problem

A CAS checks value, not history. If a thread reads A, another thread changes it to B and back to A, the first thread's CAS succeeds even though the world changed underneath. For counters this does not matter. For lock-free linked structures where the value is a node reference, it can corrupt the structure: a node popped, freed, reused and pushed back looks identical to the CAS and is not. AtomicStampedReference pairs the value with a version stamp so that A→B→A is detectable, and AtomicMarkableReference pairs it with a boolean. Java's garbage collector removes the most common cause (a freed node cannot be reused while a thread still holds its reference), which is why ABA is rarer in Java than in C. You will not write such a structure in application code; you will recognise the term when it comes up.

#What lock-free actually means

A structure is lock-free if some thread always makes progress — no thread can block all the others by being descheduled while holding a lock. Wait-free is stronger: every thread finishes in a bounded number of steps (getAndAdd on x86 is wait-free; a CAS loop is lock-free). It is a property of the algorithm, not of a class name; ConcurrentHashMap uses CAS for most operations and locks a bucket for some. Practically: lock-free structures avoid deadlock and priority inversion, and behave well when threads are preempted. They do not automatically mean faster.

#Choosing

The last-but-one row is the trap. An AtomicInteger per field does not make an object thread-safe if an invariant spans fields; each is individually atomic, together they are not.

#Try it yourself

AtomicInteger n = new AtomicInteger();
n.updateAndGet(v -> { log.info("computing"); return v + 1; });

AtomicReference<Node> head = new AtomicReference<>();
void push(T v) {
    Node n = new Node(v);
    do { n.next = head.get(); } while (!head.compareAndSet(n.next, n));
}

#Misconceptions

• "Lock-free means faster." It means guaranteed progress. Under heavy contention a CAS loop spins and a lock parks; the lock can win. Measure.
• "An atomic is a lightweight lock." It covers one variable and one operation. Two atomics do not make a two-field invariant atomic.
• "updateAndGet runs the function once." It runs it until the CAS succeeds. Side effects inside it happen a nondeterministic number of times.
• "AtomicLong is fine for a counter." For a few threads, or when the exact value is read after each update. For a hot metric, it is the slowest thing on the box.
• "volatile on the field would do the same." volatile gives visibility; count++ on it still loses updates. The atomic exists because the read-modify-write must be one step.

#Going deeper

• java.util.concurrent.atomic package Javadoc, the overview, for the exact memory-ordering guarantees.
• LongAdder and Striped64 source: the cell-striping logic and the @Contended padding, a few hundred readable lines.
• Intel's manual on the LOCK prefix, or Aleksey Shipilëv, "JVM Anatomy Quark #4 / #17" on allocation and cache lines; Martin Thompson's "Mechanical Sympathy" posts on false sharing.
• VarHandle Javadoc: compareAndSet, getAndAdd, and the weak-CAS variants.
• Treiber, "Systems Programming: Coping with Parallelism" (1986), the original lock-free stack.