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 JavaScript atomic operations are in Atomics and work on an Int32Array (or another array of integers) over a SharedArrayBuffer: the memory that several Workers see. Atomics.add(array, index, 1) is the atomic +1. You saw it in the lesson on threads. In ordinary async code on one thread you need nothing: there nobody can interrupt views++.

See it

The page-view counter

Four threads, each with 100,000 views:

import { Worker, isMainThread, workerData } from "node:worker_threads";
import { once } from "node:events";


if (isMainThread) {
  const views = new Int32Array(new SharedArrayBuffer(4));
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: views }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Views: ${views[0]}`);
} else {
  for (let i = 0; i < 100_000; i++) {
    Atomics.add(workerData, 0, 1);
  }
}
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

Atomics works only on arrays of integers over a SharedArrayBuffer. Ordinary objects, arrays and numbers are not shared between Workers: postMessage copies them. So in JavaScript shared state exists only where you have asked for it explicitly.

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 JavaScript this is Atomics.compareExchange(array, index, expected, new). It returns the value it found. If that is the expected one, the change has happened.

See it

The last three headphones

// cells: Int32Array over a SharedArrayBuffer
const STOCK = 0, SOLD = 1, REFUSED = 2;


function tryBuy(cells) {
  while (true) {
    const left = Atomics.load(cells, STOCK);
    if (left === 0) return false; // sold out
    const was = Atomics.compareExchange(
      cells, STOCK, left, left - 1);
    if (was === left) return true;
    // someone changed stock: read again
  }
}
Step by step, in words
  1. The last 3 headphones: stock is 3. Workers 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(…, 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 Worker 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:

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 100;
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: cells }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Sold: ${cells[SOLD]}`);
  console.log(`Refused: ${cells[REFUSED]}`);
  console.log(`Stock: ${cells[STOCK]}`);
} else {
  for (let i = 0; i < 40; i++) {
    if (tryBuy(workerData)) Atomics.add(workerData, SOLD, 1);
    else Atomics.add(workerData, REFUSED, 1);
  }
}
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?

const stock = new Int32Array(new SharedArrayBuffer(4));
stock[0] = 3;
let seenByA = Atomics.load(stock, 0);
const seenByB = Atomics.load(stock, 0);
const b = Atomics.compareExchange(stock, 0, seenByB, seenByB - 1) === seenByB;
console.log(`B: ${b}`);
let a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A: ${a}`);
seenByA = Atomics.load(stock, 0);
a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A again: ${a}`);
console.log(`Stock: ${Atomics.load(stock, 0)}`);
Answer

Try it

Fill in

What does the CAS compare against when buying?

const was = Atomics.compareExchange(
  cells, 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;
await saveToLog(); // a pause between two changes
prices.case = 12;
prices.cable = 4;


// checkout, during the pause
const total = cart.reduce((sum, item) => sum + prices[item], 0);

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 €). In JavaScript there is one thread, but an await in the middle of the change lets other code read the half-changed object.

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.

Between Workers no objects are shared at all. postMessage sends a copy, so "publishing" a new price list is a message to every checkout. In one thread Object.freeze guards against changing it by mistake. Trying to change a frozen object in a module throws a TypeError.

function priceList(version, prices) {
  return Object.freeze({ version, prices: Object.freeze({ ...prices }) });
}


function total(list, cart) {
  return cart.reduce((sum, item) => sum + list.prices[item], 0);
}
import { Worker, isMainThread, parentPort } from "node:worker_threads";
import { once } from "node:events";


const cart = ["headphones", "case", "cable"];


if (isMainThread) {
  const regular = { headphones: 60, case: 15, cable: 5 };
  const promo = { headphones: 48, case: 12, cable: 4 };
  const checkout = new Worker(new URL(import.meta.url));
  for (let v = 1; v <= 3; v++) {
    checkout.postMessage(priceList(v, v % 2 === 0 ? promo : regular));
    const [line] = await once(checkout, "message");
    console.log(line);
  }
  checkout.postMessage(null);
  await once(checkout, "exit");
  const last = priceList(3, regular);
  try {
    last.prices.headphones = 1;
  } catch (error) {
    console.log(`Frozen: ${error.constructor.name}`);
  }
} else {
  parentPort.on("message", (list) => {
    if (list === null) return parentPort.close();
    parentPort.postMessage(`Version ${list.version}: ${total(list, cart)} €`);
  });
}
Output
Version 1: 80 €
Version 2: 64 €
Version 3: 80 €
Frozen: TypeError
Every checkout gets its own copy and computes with it. Nobody else can change that copy, so there cannot be mixed totals.
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 Object.freeze is also on the nested object prices: freeze is only one level deep.

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:

function reserve(cells) {
  Atomics.sub(cells, STOCK, 1);    // each line is atomic,
  Atomics.add(cells, RESERVED, 1); // 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:

// cells: [lock, stock, reserved] in a SharedArrayBuffer
const LOCK = 0, STOCK = 1, RESERVED = 2;


function lock(cells) {
  while (Atomics.compareExchange(cells, LOCK, 0, 1) !== 0) {
    Atomics.wait(cells, LOCK, 1);
  }
}


function unlock(cells) {
  Atomics.store(cells, LOCK, 0);
  Atomics.notify(cells, LOCK, 1);
}


function reserve(cells) {
  lock(cells); // both or none
  try {
    if (cells[STOCK] === 0) return false;
    cells[STOCK]--;
    cells[RESERVED]++;
    return true;
  } finally {
    unlock(cells);
  }
}


function audit(cells) {
  lock(cells);
  try {
    return cells[STOCK] + cells[RESERVED];
  } finally {
    unlock(cells);
  }
}
if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 10_000;
  const roles = ["reserver", "reserver", "auditor"];
  const workers = roles.map(
    (role) => new Worker(new URL(import.meta.url), { workerData: { cells, role } }),
  );
  const report = once(workers[2], "message");
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const [broken] = await report;
  console.log(`Stock: ${cells[STOCK]}, reserved: ${cells[RESERVED]}`);
  console.log(`Broken audits: ${broken}`);
} else if (workerData.role === "reserver") {
  while (reserve(workerData.cells)) {}
} else {
  let broken = 0;
  for (let i = 0; i < 50_000; i++) {
    if (audit(workerData.cells) !== 10_000) broken++;
  }
  parentPort.postMessage(broken);
}
Output
Stock: 0, reserved: 10000
Broken audits: 0
JavaScript has no locks, so here one is written with Atomics: compareExchange takes the lock (0 → 1), and Atomics.wait sleeps while it is taken. That is what lock does in the other languages.
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 tryUse(cells) 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 ·