Counting Without a Lock

Processors have an instruction for it. Compare-and-swap.

It takes three things: a memory location, the value you expect to find there, and the value you want to write. It reads, compares, and writes only if they match, and it reports whether it wrote. No other core can touch that memory in the middle.

AtomicInteger v = new AtomicInteger(5);

v.compareAndSet(5, 6);    // true.  Value was 5, now it is 6
v.compareAndSet(5, 7);    // false. Value is 6 now, so nothing happened

Verified exactly.

Which gives you a counter with no lock:

AtomicInteger counter = new AtomicInteger();
counter.incrementAndGet();

atomic counter : 800000 (wanted 800000)

Correct, and no thread ever blocked.

Inside, it is a retry loop:

A thread that loses is never parked. It reads again and retries, still running the whole time.

That is what lock-free means: no thread is ever stopped by another. One thread being descheduled cannot hold anyone else up, because nobody was waiting for it.

The family of atomic classes:

Now the measurement, and it is not what the word lock-free suggests. Eight million increments in total, split across the threads:

At one thread the atomic is fastest. At two it beats both locks comfortably. At eight it loses to ReentrantLock, 326 ms against 179 ms.

The retry loop is why. With eight threads hammering one value, most compare-and-swaps fail, and every failure is real work thrown away on a core that could have been idle. A lock parks the losers, which sounds worse and means they stop competing for the memory.

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

1. What does compare-and-swap actually do, and why can it not be written in Java?

   Show the answer

   Three things as one unbreakable step: read the current value, compare it with what you expected, and write the new value only if they match. It reports whether it wrote.

   Written out in Java it is if (value == expected) { value = next; return true; }, which is exactly the read-change-write from Section 14.4 and has the same race in it. Two threads can both pass the comparison before either writes.

   It cannot be built out of ordinary reads and writes at all. It is a processor instruction, lock cmpxchg on x86, and the processor guarantees no other core can touch that memory in the middle.

   That single instruction is what every lock in Section 14.7 is built on.

2. How does an atomic counter work when nothing ever waits?

   Show the answer

   It tries, and if it lost the race it tries again. incrementAndGet is a loop: read the value, work out value plus one, compare-and-swap. If the swap fails, some other thread changed it, so read the new value and go round again.

   Nothing blocks. A thread that loses is not parked or queued, it just repeats, and it is still running the whole time.

   That is what lock-free means. It does not mean no waiting ever happened. It means no thread is ever stopped by another, so one thread being descheduled cannot hold everyone else up.

3. Eight threads, one counter. Why did `AtomicInteger` lose to `ReentrantLock`?

   Show the answer

   Because at eight threads most of the compare-and-swaps fail, and every failure is wasted work on a core that could have been idle.

   Measured, 8 million increments in total: at one thread Atomic was fastest at 57 ms. At two it was 148 ms against 333 for synchronized. At eight it was 326 ms while ReentrantLock was 179 ms.

   All eight threads are hammering the same memory, so that cache line bounces between cores constantly and most attempts have to be redone. A lock parks the losers, which sounds worse and means they stop competing.

   LongAdder took 24 ms at eight threads by not sharing one value at all.

Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.

4 exercises115 pointsabout 110 minutes

import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;

public class FourWays {
    public static void main(String[] args) throws Exception {
        // TODO: count to 8 million four ways: synchronized, ReentrantLock,
        //       AtomicInteger, LongAdder
        // TODO: do it at 1 thread, 2 threads and 8 threads, keeping the TOTAL
        //       work the same so the numbers compare
        // TODO: warm everything up first
        // TODO: confirm all four give exactly 8000000
        // TODO: write down which wins at each thread count, and explain the shape
    }
}

import java.util.concurrent.atomic.*;

public class MyIncrement {
    static final AtomicInteger value = new AtomicInteger();
    static final AtomicLong failures = new AtomicLong();

    static int myIncrementAndGet() {
        // TODO: read, add one, compareAndSet. Retry on failure. Count failures.
        return 0;
    }

    public static void main(String[] args) throws Exception {
        // TODO: eight threads x 200_000 through your version. Check the total.
        // TODO: print how many compareAndSet calls FAILED
        // TODO: compare that count at 2 threads and at 8
        // TODO: add Thread.onSpinWait() after a few failures. Does anything change?
    }
}

import java.util.*;
import java.util.concurrent.atomic.*;

public class NotEnough {
    static final AtomicInteger balance = new AtomicInteger(1000);
    static final List<String> history = Collections.synchronizedList(new ArrayList<>());

    static void withdraw(int amount) {
        balance.addAndGet(-amount);          // atomic
        history.add("withdrew " + amount);   // also atomic
    }

    public static void main(String[] args) throws Exception {
        // TODO: run withdraw from several threads and have another thread
        //       repeatedly check that balance and history AGREE.
        //       Show that they disagree sometimes.
        // TODO: also show the balance going negative even though each step is atomic
        // TODO: fix it with one AtomicReference holding an immutable record of both
        // TODO: fix it again with a lock, and say which you would ship
    }
}

import java.util.concurrent.atomic.*;

public class Stack<T> {
    static class Node<T> {
        final T value; Node<T> next;
        Node(T value) { this.value = value; }
    }

    private final AtomicReference<Node<T>> top = new AtomicReference<>();

    public void push(T item) {
        // TODO: build a node, point it at the current top,
        //       compareAndSet the top from that to your node, retry on failure
    }

    public T pop() {
        // TODO: read the top, work out the new top, compareAndSet, retry
        //       Return null when it is empty.
        return null;
    }

    public static void main(String[] args) throws Exception {
        // TODO: eight threads pushing 100_000 each, then eight popping.
        //       Confirm nothing is lost and nothing is duplicated.
    }
}