Atomics and read-modify-write

A lost update happens because a read and a write are two turns with a gap between them. An atomic operation closes the gap: the read, the change and the write happen in one indivisible step. With it the counter is right under every schedule: 4 schedules instead of 28, and none of them wrong.

In our machine a turn runs from one yield to the next, so anything written between two yields cannot be interleaved. A function that contains no yield therefore behaves as an atomic operation. The most common one is fetch-and-add: it reads the old value, writes old + n and returns old, all inside one turn. A counter thread that calls it has one yield for the whole increment instead of two, so the two threads can no longer both read the same old value.

def fetch_add(shared, name, n):    old = shared.get(name, 0)    shared[name] = old + n    return olddef atomic_increments(k):    def thread(shared):        for _ in range(k):            yield            fetch_add(shared, "x", 1)    return threadtwo = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]for prefix in ([0, 1], [1, 0]):    print(prefix, run_prefix(two, prefix))

[0, 1] ({'x': 2}, [])
[1, 0] ({'x': 2}, [])

Both orders end at {'x': 2} and no thread is left alive. With one turn per increment the program has only the two schedules [0, 1] and [1, 0] (4 in the study, for 1 and 3 increments), and none of them can lose an update.

Fetch-and-add only adds. For anything else you need the general tool, compare-and-swap (CAS). The pattern is a loop: read the old value, compute the new one from it, and ask CAS to install it only if nobody changed the value in the meantime. If CAS fails, someone else got there first, so you read again and retry. Below, two CAS counters: when thread 1 reads before thread 0 has written, its CAS fails once, it counts a retry, and the second attempt succeeds. The update is never lost, because a stale write is refused.

def compare_and_swap(shared, name, expected, new):    if shared.get(name, 0) != expected:        return False    shared[name] = new    return Truedef cas_increments(k):    def thread(shared):        for _ in range(k):            while True:                yield                old = shared.get("x", 0)                yield                if compare_and_swap(shared, "x", old, old + 1):                    break                fetch_add(shared, "retries", 1)    return threadcas = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]print(run_prefix(cas, [0, 1, 0, 1]))print(run_prefix(cas, [0, 1, 0, 1, 1, 1]))

({'x': 1, 'retries': 1}, [1])
({'x': 2, 'retries': 1}, [])

After [0, 1, 0, 1] the shared dictionary is {'x': 1, 'retries': 1} and thread 1 is still alive: it read 0, but thread 0 had already stored 1, so its compare-and-swap was refused. Giving thread 1 its two next turns (read again, swap again) ends at x = 2. Notice the price: the loser did the work twice. Fetch-and-add never retries; CAS retries as often as threads collide.

The explorer of the last topic assumed that every thread takes a fixed number of turns, lengths. A retry loop breaks that: a thread that loses a race takes extra turns, and how many depends on the schedule. The fix is to search the schedules as a tree. From a prefix of turns, run_prefix replays the program and tells which threads are still alive; if none is, the schedule is complete and its final state is counted, and if some are, we branch on each of them. This depth-first search visits every complete schedule exactly once. values_of then reads one shared name out of all the outcomes.

def explore_all(make_threads, shared=None):    outcomes = {}    def visit(prefix):        final, alive = run_prefix(make_threads, prefix, shared)        if not alive:            key = tuple(sorted(final.items()))            outcomes[key] = outcomes.get(key, 0) + 1            return        for tid in alive:            visit(prefix + [tid])    visit([])    return outcomesdef values_of(outcomes, name):    return sorted({dict(key).get(name, 0) for key in outcomes})print(explore_all(cas))racy = lambda shared: [increments(1)(shared), increments(1)(shared)]print(values_of(explore_all(racy), "x"), values_of(explore_all(cas), "x"))

{(('x', 2),): 2, (('retries', 1), ('x', 2)): 4}
[1, 2] [2]

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:6]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]for name, factory in (("racy", increments), ("atomic", atomic_increments), ("cas", cas_increments)):    outcomes = explore_all(lambda shared, f=factory: [f(k)(shared) for k in ups])    print(name, sum(outcomes.values()), "schedules, x in", values_of(outcomes, "x"))

racy 28 schedules, x in [1, 2, 3, 4]
atomic 4 schedules, x in [4]
cas 144 schedules, x in [4]

Both repairs are correct under every schedule, and they differ in cost. Fetch-and-add does the job in one turn per increment: 4 schedules. The CAS counter has 144 schedules, because a collision adds turns, and in the worst of them a thread retries 3 times. That is the trade-off of lock-free code: nobody waits on a lock, but the winner of each race forces the loser to repeat its work.

The lab follows the lecture: fetch-and-add, compare-and-swap, a counter thread built on each, the explorer that handles threads with a varying number of turns, a helper that reads the values of a name over all outcomes, and the study of three counters on the up days of SPY.

• Function · questionBuilds on
• fetch_add(shared, name, n)Add n, and what was there before?Plain arithmetic
• compare_and_swap(shared, name, expected, new)Did the value still equal what I read?Plain arithmetic
• atomic_increments(k)A counter with no gap?fetch_add
• cas_increments(k)A counter that retries instead of losing?compare_and_swapfetch_add
• explore_all(make_threads, shared)All outcomes, whatever the number of turns?run_prefix
• values_of(outcomes, name)Which values does this name take?Plain arithmetic
• study(bars)How do the three counters compare on SPY?explore_allvalues_of

Next topic: we assumed that every thread sees every write at once and in order. A real processor does not promise that. The memory model: acquire and release adds a store buffer to the machine, shows a reader seeing a flag before the data it guards, and repairs it with the ordering that costs the least.