Skip to content
wannacode

Atomic operations and immutable objects

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 C# they are in the class Interlocked. Interlocked.Increment(ref views) is the atomic +1 on an ordinary int field or variable and returns the new value. There are also Interlocked.Add, Interlocked.Decrement and versions for long.

See it

The page-view counter

Four threads, each with 100,000 views:

int views = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 100_000; i++)
        {
            Interlocked.Increment(ref views);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Views: {views}");
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

Count in your own place. When many threads increment the same field, they all hit one cell of memory and the processors pass it around. If the value is needed only at the end, it is faster for each thread to count in its own local variable and do one Interlocked.Add at the end. Java has a ready class for this: 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.
In C# this is Interlocked.CompareExchange(ref field, new, expected). Mind the order: the new value comes before the expected one. The method returns the value it found. If that is the expected one, the change has happened. Volatile.Read reads the field so that you see the last value written by another thread.

See it

The last three headphones

class FlashSale
{
    private int stock;


    public FlashSale(int items)
    {
        stock = items;
    }


    public bool TryBuy()
    {
        while (true)
        {
            int left = Volatile.Read(ref stock);
            if (left == 0) return false; // sold out
            int was = Interlocked.CompareExchange(
                ref stock, left - 1, left);
            if (was == left) return true;
            // someone changed stock: read again
        }
    }


    public int Stock => Volatile.Read(ref stock);
}
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: CompareExchange(…, 2, 3). "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:

var sale = new FlashSale(100);
int sold = 0, refused = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 40; i++)
        {
            if (sale.TryBuy()) Interlocked.Increment(ref sold);
            else Interlocked.Increment(ref refused);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Sold: {sold}");
Console.WriteLine($"Refused: {refused}");
Console.WriteLine($"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?

int stock = 3;
int seenByA = Volatile.Read(ref stock);
int seenByB = Volatile.Read(ref stock);
bool b = Interlocked.CompareExchange(ref stock, seenByB - 1, seenByB) == seenByB;
Console.WriteLine($"B: {b}");
bool a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A: {a}");
seenByA = Volatile.Read(ref stock);
a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A again: {a}");
Console.WriteLine($"Stock: {stock}");
Answer

Try it

Fill in

What does the CAS compare against when buying?

int was = Interlocked.CompareExchange(
    ref stock, left - 1, );

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.

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
int total = cart.Sum(item => prices[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 ImmutableDictionary (from System.Collections.Immutable) is immutable: the properties are read-only and the dictionary cannot be changed. The current price list is an ordinary variable. Volatile.Write swaps it and Volatile.Read reads it, so every thread sees the last one written. Interlocked.Exchange also swaps the reference and returns the old one.

record PriceList(int Version, ImmutableDictionary<string, int> Prices)
{
    public int Total(List<string> cart) => cart.Sum(item => Prices[item]);
}
var regular = new Dictionary<string, int> { ["headphones"] = 60, ["case"] = 15, ["cable"] = 5 }.ToImmutableDictionary();
var promo = new Dictionary<string, int> { ["headphones"] = 48, ["case"] = 12, ["cable"] = 4 }.ToImmutableDictionary();
var cart = new List<string> { "headphones", "case", "cable" };
var current = new PriceList(1, regular);
int mixed = 0;


var admin = new Thread(() =>
{
    for (int v = 2; v <= 1001; v++)
    {
        var prices = v % 2 == 0 ? promo : regular;
        Volatile.Write(ref current, new PriceList(v, prices)); // a new snapshot, one reference
    }
});
var checkout = new Thread(() =>
{
    for (int i = 0; i < 100_000; i++)
    {
        var list = Volatile.Read(ref current); // one snapshot for the whole cart
        int total = list.Total(cart);
        if (total != 80 && total != 64) Interlocked.Increment(ref mixed);
    }
});
admin.Start();
checkout.Start();
admin.Join();
checkout.Join();
Console.WriteLine("Checked totals: 100000");
Console.WriteLine($"Mixed totals: {mixed}");
Console.WriteLine($"Last version: {current.Version}, total {current.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.

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:

int stock = 10;
int reserved = 0;


void Reserve()
{
    Interlocked.Decrement(ref stock);    // each line is atomic,
    Interlocked.Increment(ref reserved); // 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 readonly object sync = new object();
    private int stock;
    private int reserved;


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


    public bool Reserve()
    {
        lock (sync) // both or none
        {
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }


    public int Audit()
    {
        lock (sync)
        {
            return stock + reserved;
        }
    }


    public string Report()
    {
        lock (sync)
        {
            return $"Stock: {stock}, reserved: {reserved}";
        }
    }
}
var warehouse = new Warehouse(10_000);
int broken = 0;
ThreadStart reserver = () =>
{
    while (warehouse.Reserve()) { }
};
ThreadStart auditor = () =>
{
    for (int i = 0; i < 50_000; i++)
    {
        if (warehouse.Audit() != 10_000) Interlocked.Increment(ref broken);
    }
};
var threads = new List<Thread> { new Thread(reserver), new Thread(reserver), new Thread(auditor) };
foreach (var thread in threads) thread.Start();
foreach (var thread in threads) thread.Join();
Console.WriteLine(warehouse.Report());
Console.WriteLine($"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 (Interlocked.CompareExchange 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 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?
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?
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?
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?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·