The Memory Model

The previous lesson showed how to protect shared data with a lock, and that the cost of a lock is determined by how many times it is acquired: for four threads, forty thousand lock acquisitions could fall to four with a local total. A lock does everything at once: it ties the data to a single thread and makes what was written visible to the next acquirer. This lesson separates those two. std::atomic makes a single operation on a variable indivisible; and the memory order determines when the writes around that operation become visible to others. The question the course measures is the same again: where does a mechanism move the cost? The answer falls under the kind wait, and here too the measure counts not actual waiting but how many synchronization points a data publish asks for. The count is a tool of evidence; the lesson is answered with the name of the kind.

Indivisibility and Ordering Are Not the Same Thing

A read or a write on a std::atomic<int> cannot be seen half done: another thread sees either the old value or the new value, nothing in between. Read-modify-write operations such as fetch_add extend this indivisibility over all three steps: reading the value, incrementing it and writing it back are a single operation, and no other increment can slip in between. For this reason, incrementing a counter without a lock is not a data race once the variable is a std::atomic.

But indivisibility says nothing about what happens to other variables. Every atomic operation takes a memory order, and four orders matter in this lesson. std::memory_order_seq_cst is the default: all seq_cst operations appear in one common order for all threads. memory_order_release is given to a store and memory_order_acquire to a load, and the two work together. memory_order_relaxed gives only indivisibility and orders nothing else.

The relation between release and acquire is expressed as the happens-before relation. If one thread stores to an atomic variable with release and another thread loads that stored value with acquire, all writes before the release become visible to all reads after the acquire. Plain, non-atomic variables are included in this; the publish flag may be atomic while the published data is plain.

A Publish: A Thousand Plain Values, One Release Store

The producer writes a thousand plain values into an array, then writes only once to an atomic flag with release. The consumer loads the flag with acquire, and once it sees the flag it sees all thousand values. The synchronization point is the number of release stores made on the producer side; the mechanism asks for one point per store. We do not write the counter by hand: right after each release store, the producer side increments its own plain counter, and the counter is read only after join().

// publish.hpp — two publish forms: a single flag and every element atomic
#pragma once
#include <atomic>
#include <thread>

constexpr int ELEMENTS = 1000;

struct SingleFlag {
    int data[ELEMENTS];
    std::atomic<int> ready{0};
    long sync_points = 0;
    long total = 0;
};

inline void produce_single(SingleFlag& p) {
    for (int i = 0; i < ELEMENTS; ++i) p.data[i] = i;
    p.ready.store(1, std::memory_order_release);
    ++p.sync_points;
}

inline void consume_single(SingleFlag& p) {
    while (p.ready.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) t += p.data[i];
    p.total = t;
}

struct EveryElement {
    std::atomic<int> cells[ELEMENTS];
    long sync_points = 0;
    long total = 0;
    EveryElement() {
        for (auto& e : cells) e.store(-1, std::memory_order_relaxed);
    }
};

inline void produce_all(EveryElement& p) {
    for (int i = 0; i < ELEMENTS; ++i) {
        p.cells[i].store(i, std::memory_order_release);
        ++p.sync_points;
    }
}

inline void consume_all(EveryElement& p) {
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) {
        int v;
        while ((v = p.cells[i].load(std::memory_order_acquire)) == -1) std::this_thread::yield();
        t += v;
    }
    p.total = t;
}

The SingleFlag array is a plain int array; the ready flag is atomic. The producer writes before the flag, and the consumer touches no element of the array until it has seen the flag. EveryElement is the second form and will be read in The Bounding Measurement section. The array is initialized before the threads are started: constructing a std::thread makes everything done up to the call of the constructor visible to the new thread.

What Relaxed Does Not Give

The relaxed order gives nothing except indivisibility. This means that a relaxed fetch_add counter still gives the correct total: if four threads each call fetch_add(1, std::memory_order_relaxed) ten thousand times, the result is forty thousand, because indivisibility protects every increment. But if the same relaxed operation is used as a publish flag, the producer’s plain writes may not be visible to the consumer; the flag may be seen as 1 while the thousand values remain as they were. This is a data race and its behavior is undefined, so we do not run it. The fix is to use release and acquire on the publish flag.

The Difference Between seq_cst and release/acquire

If we had written the publish above without specifying an order, every operation would be seq_cst. The result is the same: the side that loads the flag with acquire sees what was written. The difference is that seq_cst adds one more thing: there is a single total order for all seq_cst operations, and every thread obeys this order. Release/acquire establishes only the relation between a store and the load that reads it; it does not require two observers to agree on which of two unrelated flags was written first. Consider two independent writers and two readers: one of the readers may see x written before y, and the other may see the opposite. Release/acquire does not forbid this; if both stores and both loads are all seq_cst, this outcome is forbidden. We do not run this case, because which outcome is seen depends on the schedule and the hardware; the lesson only separates the scope of the guarantee.

This extra guarantee comes at a price: providing the common total order requires extra barriers on some hardware. The synchronization point you count does not change, though; it is still a store. So rather than choosing seq_cst deliberately, going down to release/acquire is a choice when you can see that the publish rests on only one store and one load. If you are not sure, the default seq_cst is correct; this is a preference for correctness, not a claim about speed.

// ordering.hpp — the same publish, with the default seq_cst order
#pragma once
#include <atomic>
#include <thread>

#include "publish.hpp"

struct DefaultPublish {
    int data[ELEMENTS];
    std::atomic<int> ready{0};
    long sync_points = 0;
    long total = 0;
};

inline void produce_default(DefaultPublish& p) {
    for (int i = 0; i < ELEMENTS; ++i) p.data[i] = i;
    p.ready.store(1);
    ++p.sync_points;
}

inline void consume_default(DefaultPublish& p) {
    while (p.ready.load() == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) t += p.data[i];
    p.total = t;
}

Read-Modify-Write and compare_exchange

fetch_add always increments the value. Sometimes the store has to be conditional: “write if the value is still the one I read”. compare_exchange_strong(expected, desired) does this as a single indivisible operation. If the atomic value equals expected, desired is written and true is returned; if it is not equal, nothing is written, false is returned, and expected is updated with the atomic’s value at that moment. If four threads try to turn the same flag from 0 to 1, only one wins; the others see the failure. No lock is needed to choose the winner.

The weak form of the operation can fail even when the values are equal; for this reason it is always used inside a loop. In return, it is cheaper on some hardware. The typical pattern is to read the value, compute a candidate and try to write with compare_exchange_weak; on failure expected has already been refreshed with the new value, so the loop does not read again. The example below finds the largest value seen by four threads without a lock: if the candidate is larger than the current value it tries to write, and if not it leaves the loop at once.

// rmw.hpp — a single winner and the largest value with compare_exchange
#pragma once
#include <atomic>
#include <thread>
#include <vector>

inline int single_winner(int thread_count) {
    std::atomic<int> flag{0};
    std::atomic<int> winner{0};
    std::vector<std::thread> workers;
    for (int t = 0; t < thread_count; ++t) {
        workers.emplace_back([&] {
            int expected = 0;
            if (flag.compare_exchange_strong(expected, 1)) winner.fetch_add(1);
        });
    }
    for (auto& worker : workers) worker.join();
    return winner.load();
}

inline int largest(int thread_count, int per_thread) {
    std::atomic<int> biggest{0};
    std::vector<std::thread> workers;
    for (int t = 0; t < thread_count; ++t) {
        workers.emplace_back([&, t] {
            for (int k = 0; k < per_thread; ++k) {
                int candidate = k * thread_count + t;
                int current = biggest.load(std::memory_order_relaxed);
                while (candidate > current && !biggest.compare_exchange_weak(current, candidate)) {
                }
            }
        });
    }
    for (auto& worker : workers) worker.join();
    return biggest.load();
}

How many times the loop turns depends on the schedule, so it is not printed. The result, however, does not depend on the schedule: the largest candidate is written under every condition.

Reading the Happens-Before Chain Step by Step

The happens-before relation is transitive. Suppose there are three threads: A writes a plain value and writes to flag1 with release; B sees flag1 with acquire, writes its own plain value and writes to flag2 with release; C sees flag2 with acquire. What C sees comes through a flag that A never touched; even so, it sees A’s write as well. We read the chain as follows.

1. A’s plain write happens before A’s release store to flag1 (order within one thread).
2. The release store to flag1 happens before B’s acquire load that sees it (a release/acquire pair).
3. B’s acquire load happens before B’s plain write and B’s release store to flag2 (order within one thread).
4. The release store to flag2 happens before C’s acquire load (the second pair).
5. Transitivity: A’s write happens before C’s read, and so does B’s.

Every link in the chain is either the order within one thread or a release/acquire pair. If a link breaks, for example if B loads the flag with relaxed, step 2 is not established and there is no guarantee left that C sees A’s write.

// chain.hpp — a happens-before chain across three threads
#pragma once
#include <atomic>
#include <thread>

struct Chain {
    int a = 0;
    int b = 0;
    std::atomic<int> flag1{0};
    std::atomic<int> flag2{0};
    int seen_a = 0;
    int seen_b = 0;
};

inline void chain_a(Chain& c) {
    c.a = 10;
    c.flag1.store(1, std::memory_order_release);
}

inline void chain_b(Chain& c) {
    while (c.flag1.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    c.b = c.a + 5;
    c.flag2.store(1, std::memory_order_release);
}

inline void chain_c(Chain& c) {
    while (c.flag2.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    c.seen_a = c.a;
    c.seen_b = c.b;
}

Measurement: How Many Synchronization Points

// publish_measurement.cpp — two publish forms and a relaxed counter
#include <atomic>
#include <functional>
#include <iostream>
#include <thread>
#include <vector>

#include "chain.hpp"
#include "ordering.hpp"
#include "publish.hpp"
#include "rmw.hpp"

int main() {
    SingleFlag single;
    {
        std::thread producer(produce_single, std::ref(single));
        std::thread consumer(consume_single, std::ref(single));
        producer.join();
        consumer.join();
    }
    std::cout << "release/acquire publish wait sync=" << single.sync_points
              << " total=" << single.total << "\n";

    EveryElement every;
    {
        std::thread producer(produce_all, std::ref(every));
        std::thread consumer(consume_all, std::ref(every));
        producer.join();
        consumer.join();
    }
    std::cout << "every element atomic wait sync=" << every.sync_points
              << " total=" << every.total << "\n";

    std::atomic<long> counter{0};
    std::vector<std::thread> workers;
    for (int i = 0; i < 4; ++i) {
        workers.emplace_back([&counter] {
            for (int k = 0; k < 10000; ++k) counter.fetch_add(1, std::memory_order_relaxed);
        });
    }
    for (auto& worker : workers) worker.join();
    std::cout << "relaxed counter wait value=" << counter.load() << "\n";

    DefaultPublish plain;
    {
        std::thread producer(produce_default, std::ref(plain));
        std::thread consumer(consume_default, std::ref(plain));
        producer.join();
        consumer.join();
    }
    std::cout << "seq_cst publish wait sync=" << plain.sync_points
              << " total=" << plain.total << "\n";

    std::cout << "compare exchange wait winner=" << single_winner(4) << "\n";
    std::cout << "cas loop wait largest=" << largest(4, 1000) << "\n";

    Chain chain;
    {
        std::thread c(chain_c, std::ref(chain));
        std::thread b(chain_b, std::ref(chain));
        std::thread a(chain_a, std::ref(chain));
        a.join();
        b.join();
        c.join();
    }
    std::cout << "happens-before chain wait a=" << chain.seen_a
              << " b=" << chain.seen_b << "\n";
    return 0;
}

release/acquire publish wait sync=1 total=499500
every element atomic wait sync=1000 total=499500
relaxed counter wait value=40000
seq_cst publish wait sync=1 total=499500
compare exchange wait winner=1
cas loop wait largest=3999
happens-before chain wait a=10 b=15

CP7. The first line shows that a thousand plain values were published with a single release store: sync=1. When the consumer saw the flag with its acquire load, it read all thousand elements and the total came out as 499500, which is the sum of the numbers from zero to nine hundred ninety-nine. How many times the consumer turned before seeing the flag is not printed, because that number depends on the schedule; what is measured is not the loop count but the number of release stores written.

CP8. The third line shows that the relaxed fetch_add counter still gives 40000. Although the order is relaxed, the result is correct; because indivisibility is not ordering, and no increment breaks into another. A relaxed counter is correct use only where just the final value is read and no other data is published.

CP9. The fourth line shows that the same publish with the default seq_cst order also consists of one store and one load: sync=1, total=499500. The number of synchronization points did not change when the order changed; the seq_cst difference cannot be read from this line, because the difference appears only in how observers order two mutually independent publishes.

CP10. With compare_exchange_strong, four threads tried to turn the same flag from 0 to 1 and winner=1 came out. Had it been possible for all four to succeed at once, the number would have come out greater than one; the indivisible compare and write prevented this. Which thread won was not printed, because it depends on the schedule.

CP11. The value largest=3999 is the largest of the candidates produced by the four threads: 999 * 4 + 3 for the last step k=999 and the last thread t=3. When another thread slipped in and changed the value, compare_exchange_weak failed and updated current; the loop compared the candidate with the new value again. No larger value was written after a smaller one and lost.

CP12. On the last line, thread C saw both a=10 and b=15. The a that came through flag1, which C never read, became visible thanks to the transitivity of the chain. Even though the threads were started out of order (C was started first), the result did not change, because C stayed in its loop until it saw the flag.

The Bounding Measurement

The mechanism this lesson measured is that the memory order determines the number of synchronization points. The second line publishes the same thousand values, this time making each element a separate atomic. Every store is a release, every load an acquire; correctness was not broken, total=499500. But sync=1000: a thousand times more synchronization points.

This difference comes not from the data itself but from how finely the publish is divided. While one flag protects a thousand values, a thousand atomics protect each value one by one. The happens-before relation is cheap for a single release-acquire pair and covers all the writes before the pair; for this, the data to be published must first be collected and then opened from a single point. The limit is this: if the consumer has to use the data without waiting for the other half, a single flag is not enough and a piecewise publish becomes unavoidable. Relaxing the order is not enough to reduce the cost; the number of points the publish is divided into must be reduced.

Summary

• The mechanism this lesson measured moves the cost to the kind wait: the memory order determines how many synchronization points a data publish asks for; the measure is the number of these points, not actual waiting.
• std::atomic gives indivisibility; read-modify-write operations such as fetch_add turn three steps into one operation. Indivisibility is not ordering.
• A release store and an acquire load establish the happens-before relation: when the acquire reads the value the release wrote, all writes before the release become visible to all reads after the acquire.
• seq_cst is the default and makes all seq_cst operations visible in a single common order; relaxed gives only indivisibility, and using it as a publish flag is a data race.
• release/acquire publish published a thousand values at one point, and the every element atomic mechanism at a thousand points; both gave the same total.

Next Step

Reducing synchronization points is half the work; the other half is how the data is laid out in memory. The next lesson opens the cache line and locality: with the question of how many jumps a data layout skips, we will compare an array of structures with a structure of arrays.