Atomic operations and immutable objects

Code in:JavaC#PythonJavaScript

In short: An atomic operation (such as +1 or compare-and-set) runs all at once, without another thread interrupting it, and protects shared data without a lock; an immutable object never changes at all.

Problem

A lock for one +1

A flash sale: 100 headphones at half price, at 10:00. The product page is opened thousands of times a second, and every opening increments the page-view counter. From the lesson on locks you know how not to lose increments: a lock around views++.

That is correct. But every thread queues in front of the lock for one single +1. A thread that does not get the lock is often put to sleep and later woken up by the operating system. That costs much more than the addition itself.

The second problem is worse. The last item is bought with "if there is one, decrease by 1". Those are two steps, and between them another thread can take the same item.

The idea

An indivisible step

The processor has instructions that read, change and write one cell of memory in one indivisible step. No other thread can get in the middle. This is an atomic operation. There is no lock, nobody queues and nobody sleeps.

In Java they are in java.util.concurrent.atomic. AtomicInteger holds one int, and incrementAndGet() is the atomic +1 and returns the new value. There are also addAndGet, getAndIncrement, and AtomicLong for long.

See it

The page-view counter

Four threads, each with 100,000 views:

AtomicInteger views = new AtomicInteger();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Views: " + views.get());

Output

Views: 400000

400,000 on every run. Without the atomic +1 it would be less and different every time, as in the lesson on race conditions.

More precisely, if you are curious

LongAdder. When many threads increment the same AtomicInteger, they all hit one cell of memory and the processors pass it around. LongAdder counts in several cells (one per group of threads) and adds them up only at sum(). It is faster under heavy load, but it does not give the value after every increment. It suits counters that are only read at the end:

LongAdder views = new LongAdder();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.increment();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Views: " + views.sum());

Output

Views: 400000

How much faster than a lock is it? It depends on the machine and on how many threads fight for one cell. Without a fight an atomic +1 is a few nanoseconds. A lock without a fight is close to it. The difference comes with many threads: then the lock puts threads to sleep, while the atomic operation only repeats.

The idea

Check and change: compare-and-set

Buying is not just −1. It is "if there is at least one, decrease by 1". The check and the change must be one step.

There is a more general atomic operation for this: compare-and-set (CAS). You give it two numbers: what you think is there and what you want there. It changes the value only if it is still what you think, and tells you whether it succeeded. If another thread has changed it in the meantime, CAS touches nothing and answers "no".

Then buying is a loop:

1. read the stock;
2. if it is 0, refuse;
3. CAS: "if it is still this much, make it one less";
4. if CAS fails, someone has bought in the meantime: go back to 1.

In Java this is compareAndSet(expected, new), which returns true or false.

See it

The last three headphones

class FlashSale {
    private final AtomicInteger stock;

    FlashSale(int items) {
        stock = new AtomicInteger(items);
    }

    boolean tryBuy() {
        while (true) {
            int left = stock.get();
            if (left == 0) return false; // sold out
            if (stock.compareAndSet(left, left - 1)) {
                return true;
            }
            // someone changed stock: read again
        }
    }

    int stock() {
        return stock.get();
    }
}

Step by step, in words

1. The last 3 headphones: stock is 3. Threads A and B call tryBuy() at the same time.
2. A reads the stock: left = 3.
3. B reads it before A has changed anything: also 3.
4. B: compareAndSet(3, 2). "If it is still 3, make it 2." It is still 3, so 2 is written. B has bought.
5. A tries the same: "if it is still 3…". It is 2 now, so nothing is written and the answer is false. Nothing is lost.
6. A does not wait and does not give up: the loop goes round and A reads again: 2. No thread has slept.
7. A: "if it is still 2, make it 1". It is still 2: 1 is written. A has bought too.
8. Two buyers, two sold, stock 1. There is no lock: the processor checks and writes in one step, and the one who loses only repeats the loop.

Nobody waits: the thread that lost only repeats two lines. This is called lock-free. A hundred items for 160 attempts:

FlashSale sale = new FlashSale(100);
AtomicInteger sold = new AtomicInteger();
AtomicInteger refused = new AtomicInteger();
Runnable buyers = () -> {
    for (int i = 0; i < 40; i++) {
        if (sale.tryBuy()) sold.incrementAndGet();
        else refused.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(buyers);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Sold: " + sold.get());
System.out.println("Refused: " + refused.get());
System.out.println("Stock: " + sale.stock());

Output

Sold: 100
Refused: 60
Stock: 0

How many times the loop went round is different on every run, so the program does not print it. The totals are always the same: 100 sold, 60 refused, 0 in stock.

Try it

Predict the output

Here the two "threads" are written one after the other in one thread, so that the order is the same as in the scene on every run. What will it print?

AtomicInteger stock = new AtomicInteger(3);
int seenByA = stock.get();
int seenByB = stock.get();
System.out.println("B: " + stock.compareAndSet(seenByB, seenByB - 1));
System.out.println("A: " + stock.compareAndSet(seenByA, seenByA - 1));
seenByA = stock.get();
System.out.println("A again: " + stock.compareAndSet(seenByA, seenByA - 1));
System.out.println("Stock: " + stock.get());

Answer

B: true
A: false
A again: true
Stock: 1

B: true
A: true
A again: false
Stock: 1

B: true
A: true
A again: true
Stock: 0

Check

Try it

Fill in

What does the CAS compare against when buying?

if (stock.compareAndSet(, left - 1)) {

Check

Try it

Find the bug

A colleague has simplified buying. Every line on its own is safe, and yet in the sale 103 headphones out of 100 are sold. Which line is the bug on?

Pick the line with the bug.

1boolean tryBuy() {2 if (stock.get() > 0) {3 stock.decrementAndGet();4 return true;5 }6 return false;7}

Check

Problem

The price list that changes halfway

At 10:00 the admin starts the promotion: headphones from 60 to 48 €, case from 15 to 12 €, cable from 5 to 4 €. At the same time the checkouts compute carts. If the prices are in one shared dictionary and change one by one, a checkout can read the new price of the headphones and the old price of the case:

// admin
prices.put("headphones", 48);
prices.put("case", 12);
prices.put("cable", 4);

// checkout, at the same time
int total = 0;
for (String item : cart) total += prices.get(item);

The cart comes to 68 €: a total that was not right at any moment. Not at the old prices (80 €), not at the new ones (64 €). And a HashMap or Dictionary changed by one thread while another reads it can even throw an exception or return a wrong value.

The idea

Do not change it, replace it whole

The price list is read many times and changed rarely. Then never change it. Make it an immutable object: once created, it stays the same. For the promotion the admin makes a new price list and swaps one reference: "the current price list is this one".

• An object that nobody changes can be read by as many threads as you like, without any protection.
• The only shared thing is the reference, and swapping it is one atomic step.
• The checkout takes the reference once, at the start of the cart, and computes the whole cart with it. It sees the whole old or the whole new price list, never a mix.

A record with Map.copyOf is immutable: the fields are final, and Map.copyOf makes a copy that cannot be changed. AtomicReference holds the current price list: set swaps it and get reads it, so every thread sees the last one written.

record PriceList(int version, Map<String, Integer> prices) {
    PriceList {
        prices = Map.copyOf(prices); // an unmodifiable copy
    }

    int total(List<String> cart) {
        int sum = 0;
        for (String item : cart) sum += prices.get(item);
        return sum;
    }
}

Map<String, Integer> regular = Map.of("headphones", 60, "case", 15, "cable", 5);
Map<String, Integer> promo = Map.of("headphones", 48, "case", 12, "cable", 4);
List<String> cart = List.of("headphones", "case", "cable");
AtomicReference<PriceList> current =
        new AtomicReference<>(new PriceList(1, regular));
AtomicInteger mixed = new AtomicInteger();

Thread admin = new Thread(() -> {
    for (int v = 2; v <= 1001; v++) {
        Map<String, Integer> prices = v % 2 == 0 ? promo : regular;
        current.set(new PriceList(v, prices)); // a new snapshot, one reference
    }
});
Thread checkout = new Thread(() -> {
    for (int i = 0; i < 100_000; i++) {
        PriceList list = current.get(); // one snapshot for the whole cart
        int total = list.total(cart);
        if (total != 80 && total != 64) mixed.incrementAndGet();
    }
});
admin.start();
checkout.start();
admin.join();
checkout.join();
PriceList last = current.get();
System.out.println("Checked totals: 100000");
System.out.println("Mixed totals: " + mixed.get());
System.out.println("Last version: " + last.version() + ", total " + last.total(cart) + " €");

Output

Checked totals: 100000
Mixed totals: 0
Last version: 1001, total 80 €

The checkout has checked tens of thousands of carts while the price list changed a thousand times, and not one total is mixed. How many carts went by the old and how many by the new list is different on every run, so the program does not print it.

More precisely, if you are curious

This is also how "copy on write" collections work: CopyOnWriteArrayList in Java, ImmutableList in C#. Every change makes a new copy, and reading needs no lock. It pays off when there are many reads and few writes. If writes are frequent, the copying gets expensive.

Immutability is honest only if it goes all the way down. An object with a final field that points to a changeable list is not immutable: the list can be changed from outside. That is why it is Map.copyOf, not the Map that was passed in.

How it is in the other languages: record and Map.copyOf with AtomicReference in Java; record with ImmutableDictionary and Volatile or Interlocked.Exchange in C#; a frozen dataclass, a tuple or MappingProxyType and assignment in Python; Object.freeze and messages between Workers in JavaScript.

The idea

When atomic is not enough

A reservation moves an item from the stock to the reserved count. The rule is that the two together are always 10,000. Two atomic variables do not keep it:

AtomicInteger stock = new AtomicInteger(10);
AtomicInteger reserved = new AtomicInteger(0);

void reserve() {
    stock.decrementAndGet();    // each line is atomic,
    reserved.incrementAndGet(); // the two together are not
}

Between the two lines the auditor sees 9,999 in total. Atomic protects one value. When the rule is about several values together, you need a lock around all the changes and around the check:

class Warehouse {
    private final Object lock = new Object();
    private int stock;
    private int reserved;

    Warehouse(int stock) {
        this.stock = stock;
    }

    boolean reserve() {
        synchronized (lock) { // both or none
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }

    int audit() {
        synchronized (lock) {
            return stock + reserved;
        }
    }

    String report() {
        synchronized (lock) {
            return "Stock: " + stock + ", reserved: " + reserved;
        }
    }
}

Warehouse warehouse = new Warehouse(10_000);
AtomicInteger broken = new AtomicInteger();
Runnable reserver = () -> {
    while (warehouse.reserve()) { }
};
Runnable auditor = () -> {
    for (int i = 0; i < 50_000; i++) {
        if (warehouse.audit() != 10_000) broken.incrementAndGet();
    }
};
List<Thread> threads = List.of(new Thread(reserver), new Thread(reserver), new Thread(auditor));
for (Thread thread : threads) thread.start();
for (Thread thread : threads) thread.join();
System.out.println(warehouse.report());
System.out.println("Broken audits: " + broken.get());

Output

Stock: 0, reserved: 10000
Broken audits: 0

More precisely, if you are curious

Another way without a lock: both values in one immutable object (stock, reserved), and the swap with a CAS on the reference (AtomicReference.compareAndSet). A new object with both new values replaces the old one at once. That combines the two ideas of this lesson, but the lock is usually clearer.

What to use when:

• one value, a counter or a flag: an atomic operation;
• check and change one value: a CAS loop;
• data that is read a lot and changed rarely: an immutable object and a swap of the reference;
• several related values: a lock.

Exercise

A coupon with limited uses

Solve the task in your editor.

The coupon "SPRING20" can be used 50 times. Eight threads, each with 10 customers, try to use it at the same time. Write Coupon with tryUse() so that the coupon is never used more than 50 times. Without a lock: with a compare-and-set loop. Print how many times it was used, how many refusals there were and how many uses are left:

Output

Used: 50
Refused: 30
Left: 0

More tasks

• The maximum. Keep the largest order of the day while many threads add orders. Hint: a CAS loop that writes only if the new one is larger.
• Two promotions. Give the price list a version and run two admins who publish at the same time. How do you keep one admin's promotion from being lost? (Hint: swap the reference with CAS only if the version is still the one you read.)
• The auditor without a lock. Put the stock and the reserved count in one immutable object and swap it with CAS. Check that the auditor still always sees 10,000.

Test

Check yourself

1. The stock is 6. A thread calls CAS "if it is 5, make it 4". What happens?

4 is writtenThe thread sleeps until the value becomes 5Nothing is written and the answer is "failed": the thread has to read again

2. tryBuy has "if the stock is > 0" and then "decrease by 1". Both lines are atomic. Why does it still sell more than there is?

Between the check and the decrease another thread can take the last item: each step is indivisible, but the two together are notIt cannot: if every line is atomic, the whole method is safeBecause atomic operations sometimes lose increments

3. The checkouts read the price list thousands of times a second, and it changes once a day. What is the best way to share it?

An immutable object: the admin makes a new price list and swaps one reference; every checkout reads the whole old or the whole new oneA lock around every read of a priceOne shared dictionary in which the admin changes the prices one by one

4. You reserve an item: the stock drops by 1 and the reserved count grows by 1. The auditor checks that the sum is always 10,000. What do you need?

Nothing: the sum is computed at the endA lock around both changes and around the checkTwo atomic variables

Check

Start the lesson over

Related lessons

• Builds on: Threads · Why threads · Race condition · Locking
• Continues in: Deadlock · Producer and consumer · Testing concurrent code
• Tasks on this topic: Concurrency and race conditions