Atomic operations and immutable objects

Code in:JavaC#PythonJavaScript

In short: An atomic operation runs all at once, without another thread interrupting it; Python has no atomic integer or compare-and-set, so you protect data with a lock, and an immutable object never changes.

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.

Python has no atomic integer. views += 1 is several steps for the interpreter, with the GIL and without it. So Python has three honest ways:

• a lock around the increment, as in the lesson on locks;
• a queue into which the threads send the events while one thread counts (in the later lessons);
• every thread counts in its own place, and at the end the places are added up. Then nothing is shared and nothing needs protecting.

Here is the third way.

See it

The page-view counter

Four threads, each with 100,000 views:

counts = [0] * 4


def visitor(slot):
    for _ in range(100_000):
        counts[slot] += 1  # only this thread writes here


threads = [threading.Thread(target=visitor, args=(slot,))
           for slot in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(f"Views: {sum(counts)}")

Output

Views: 400000

400,000 on every run. Each thread writes only to its own counts[slot], so nobody gets in anybody's way. sum(counts) is called only after join, when the threads have finished.

More precisely, if you are curious

In other people's code you will meet next(counter) on itertools.count() as an "atomic" counter. In CPython with the GIL it really does not lose values, but that is a detail of the implementation, not a promise of the language. In Python 3.13 without the GIL (free-threaded) do not rely on it. In Java this idea (count separately, add up at the end) is a ready class: LongAdder.

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.

Python has no CAS. So that you can see the idea, AtomicCell below is a small stand-in: compare_and_set does the check and the change under a Lock. A real CAS is one processor instruction, without a lock.

See it

The last three headphones

class AtomicCell:
    """Python has no CAS: a small stand-in with a Lock"""

    def __init__(self, value):
        self._value = value
        self._lock = threading.Lock()

    def get(self):
        return self._value

    def compare_and_set(self, expected, new):
        with self._lock:
            if self._value != expected:
                return False
            self._value = new
            return True


class FlashSale:
    def __init__(self, items):
        self.stock = AtomicCell(items)

    def try_buy(self):
        while True:
            left = self.stock.get()
            if left == 0:
                return False  # sold out
            if self.stock.compare_and_set(left, left - 1):
                return True
            # someone changed stock: read again

Step by step, in words

1. The last 3 headphones: stock is 3. Threads A and B call try_buy() at the same time.
2. A reads the stock: left = 3.
3. B reads it before A has changed anything: also 3.
4. B: compare_and_set(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:

sale = FlashSale(100)
results = []  # list.append is safe to call from many threads


def buyers():
    for _ in range(40):
        results.append(sale.try_buy())


threads = [threading.Thread(target=buyers) for _ in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Sold:", results.count(True))
print("Refused:", results.count(False))
print("Stock:", sale.stock.get())

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.

More precisely, if you are curious

In real Python code you do not write AtomicCell. You put a lock around the check and the decrease, and it does the same:

class FlashSale:
    def __init__(self, items):
        self.stock = items
        self.lock = threading.Lock()

    def try_buy(self):
        with self.lock:
            if self.stock == 0:
                return False  # sold out
            self.stock -= 1
            return True

Output

Sold: 100
Refused: 60
Stock: 0

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?

AtomicCell is the class from the scene.

stock = AtomicCell(3)
seen_by_a = stock.get()
seen_by_b = stock.get()
print("B:", stock.compare_and_set(seen_by_b, seen_by_b - 1))
print("A:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
seen_by_a = stock.get()
print("A again:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
print("Stock:", stock.get())

Answer

B: True
A: False
A again: True
Stock: 1

B: True
A: True
A again: True
Stock: 0

B: True
A: True
A again: False
Stock: 1

Check

Try it

Fill in

What does the CAS compare against when buying?

if self.stock.compare_and_set(, 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.

1def try_buy(self):2 if self.stock > 0:3 with self.lock:4 self.stock -= 15 return True6 return False

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["headphones"] = 48
prices["case"] = 12
prices["cable"] = 4

# checkout, at the same time
total = sum(prices[item] for item in cart)

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 €).

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.

@dataclass(frozen=True) forbids changing the fields. The dictionary inside can still change, though, so it is a MappingProxyType: a read-only view of the dictionary. The swap is an ordinary assignment: current = PriceList(...). Assigning a name in Python is one step, so the checkout reads either the old or the new object.

@dataclass(frozen=True)
class PriceList:
    version: int
    prices: MappingProxyType  # read-only

    def total(self, cart):
        return sum(self.prices[item] for item in cart)

regular = MappingProxyType({"headphones": 60, "case": 15, "cable": 5})
promo = MappingProxyType({"headphones": 48, "case": 12, "cable": 4})
cart = ["headphones", "case", "cable"]
current = PriceList(1, regular)
mixed = 0


def admin():
    global current
    for v in range(2, 1002):
        prices = promo if v % 2 == 0 else regular
        current = PriceList(v, prices)  # a new snapshot, one reference


def checkout():
    global mixed
    for _ in range(20_000):
        price_list = current  # one snapshot for the whole cart
        total = price_list.total(cart)
        if total not in (80, 64):
            mixed += 1


threads = [threading.Thread(target=admin), threading.Thread(target=checkout)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Checked totals: 20000")
print("Mixed totals:", mixed)
print(f"Last version: {current.version}, total {current.total(cart)} €")

Output

Checked totals: 20000
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 frozen=True is not enough and the dictionary is a MappingProxyType.

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:

stock = 10
reserved = 0


def reserve():
    global stock, reserved
    stock -= 1     # in Python not even one line is atomic,
    reserved += 1  # let alone the two together

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:
    def __init__(self, stock):
        self.stock = stock
        self.reserved = 0
        self.lock = threading.Lock()

    def reserve(self):
        with self.lock:  # both or none
            if self.stock == 0:
                return False
            self.stock -= 1
            self.reserved += 1
            return True

    def audit(self):
        with self.lock:
            return self.stock + self.reserved

    def report(self):
        with self.lock:
            return f"Stock: {self.stock}, reserved: {self.reserved}"

warehouse = Warehouse(10_000)
broken = 0


def reserver():
    while warehouse.reserve():
        pass


def auditor():
    global broken
    for _ in range(20_000):
        if warehouse.audit() != 10_000:
            broken += 1


threads = [threading.Thread(target=f) for f in (reserver, reserver, auditor)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(warehouse.report())
print("Broken audits:", broken)

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. 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 try_use() so that the coupon is never used more than 50 times. With a lock around the check and the decrease. 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