`atomic<>`: The C++ Memory Model#

Foreword#

A memory model is an attept to find a common denominator across atomicity and memory order features of different CPUs

enum memory_order
{
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
};

Integer Increments (Single Threaded)#

../../../../../../../_images/single-core-memonly.svg

code/load-modify-store-single.cpp#

#include <array>
#include <print>

int main()
{
    const unsigned long numtimes = 1000*1000*1000UL;
    unsigned long counter = 0;

    auto inc = [&counter]() {
        unsigned long n = numtimes;
        while (n--)
            counter++;
    };

    inc();

    std::println("expected {}, real {}", 1*numtimes, counter);

    return 0;
}

$ ./c++11-memory-model-load-modify-store-single
expected 1000000000, real 1000000000

Integer Increments?#

counter++ is not atomic
Breaks down into multiple instructions
⟶ Load/Modify/Store (Read/Modify/Write)

Source code	What becomes of it
counter++;	auto reg = counter; // <-- load into register reg++; // <-- increment register counter = reg; // <-- write back to memory

Integer Increment: The Mother Of Race Conditions#

../../../../../../../_images/multi-core-memonly.svg

code/load-modify-store.cpp#

#include <thread>
#include <array>
#include <print>

int main()
{
    const unsigned long numtimes = 1000*1000*1000UL;
    unsigned long counter = 0;

    auto inc = [&counter]() {
        unsigned long n = numtimes;
        while (n--)
            counter++;
    };

    std::array threads{
        std::thread(inc),
        std::thread(inc),
    };
    for (auto& t: threads)
        t.join();

    std::println("expected {}, real {}", threads.size()*numtimes, counter);

    return 0;
}

$ ./c++11-memory-model-load-modify-store
expected 2000000000, real 1004072808

Load/Modify/Store Conflict#

Physical parallelism: 2 CPUs
Virtual parallelism: single CPU + scheduler context switch
- ⟶ extremely rare
- ⟶ extremely nasty

CPU1	CPU2
auto reg = counter; reg++; . . . counter = reg;	. . auto reg = counter; reg++; counter = reg; .

Anti-Conflict: Mutex#

Downside: context switch on contention ⟶ try to minimize contention
Upside: always safe - “If in doubt use a mutex!”*

code/load-modify-store-mutex.cpp#

#include <thread>
#include <mutex>
#include <array>
#include <print>

int main()
{
    const unsigned long numtimes = 1000*1000*1000UL;
    unsigned long counter = 0;
    std::mutex lock;                                   // <-- used to protect unsafe operator++

    auto inc = [&counter, &lock]() {
        unsigned long n = numtimes;
        while (n--) {
            lock.lock();                               // <-- "acquire"
            counter++;
            lock.unlock();                             // <-- "release"
        }
    };

    std::array threads{
        std::thread(inc),
        std::thread(inc),
    };
    for (auto& t: threads)
        t.join();

    std::println("expected {}, real {}", threads.size()*numtimes, counter);

    return 0;
}

Anti-Conflict: `std::atomic<>`#

Upside: all kinds of fast atomicity on flags, counters, …
Downside: only fast for certain kinds of data types, under certain circumstances. If not fast ⟶ internally, a mutex is used to implement atomicity

code/load-modify-store-seq-cst.cpp#

#include <atomic>
#include <thread>
#include <array>
#include <print>

int main()
{
    const unsigned long numtimes = 1000*1000*1000UL;
    std::atomic<unsigned long> counter = 0;            // <-- operator++ is atomic

    auto inc = [&counter]() {
        unsigned long n = numtimes;
        while (n--)
            counter++;
    };

    std::array threads{
        std::thread(inc),
        std::thread(inc),
    };
    for (auto& t: threads)
        t.join();

    std::println("expected {}, real {}", threads.size()*numtimes, 
                 static_cast<unsigned long>(counter)); // <-- operator unsigned long

    return 0;
}

Sequential Consistency#

Note

Guarantee given

A READ from a location must return the value of the last WRITE to that location

Possible implementation: flush all memory caches through to main memory (read on)
There are sure better implementations
Not free though

Is `std::atomic<>` Lock Free?#

Standard says: only std::atomic_flag is guaranteed to be lock free (see std::atomic_flag)
Other std::atomic<> specialization could be (tested on x86_64)

code/atomic-lock-free.cpp#

#include <atomic>
#include <print>


struct foo
{
    int a;
    int b;
    int c;
    int d;
    int e;
    int f;
};

int main()
{
    std::atomic<int> i;
    std::println("int: {}", i.is_lock_free());         // <-- true
    std::atomic<int*> pi;
    std::println("int*: {}", pi.is_lock_free());       // <-- true
    std::atomic<foo> f;
    std::println("foo: {}", f.is_lock_free());         // <-- false

    return 0;
}
 

Modern CPUs Are More Complex#

Reads are fast
Writes can take
⟶ Store buffer
⟶ Cache hierarchies

../../../../../../../_images/snapdragon.webp

../../../../../../../_images/small_broadwell-e-die-map.webp

Towards Out-Of-Order Memory Access: What Matters? (Cache/Memory)#

Full detail	Cache And Memory
Cache And Memory Is Transparent	And Store Buffer?

Towards Out-Of-Order Memory Access: What Matters? (CPU/Store Buffer)#

Store buffer is where reordering is done
Cache and memory just works

../../../../../../../_images/cpu-store-buffer.svg

Publishing Something#

code/publish-intro.cpp#

#include <thread>
#include <print>

struct data
{
    int foo;
    int bar;
};
data* shared_data = nullptr;

int main()
{
    // **produce**
    data* local_data = new data;                       // <-- write #1
    local_data->foo = 42;                              // <-- write #2
    local_data->bar = 666;                             // <-- write #3

    // **publish: shared_data valid from here on**
    shared_data = local_data;                          // <-- write #4

    // **consume**
    std::println("foo {}, bar {}", shared_data->foo, shared_data->bar);

    return 0;
}

Store Dependencies#

A reordering engine (Intel conservative, ARM/RISC-V aggressive) can consider the following store dependencies.

$digraph G { w_local_data[label="local_data = \nnew data;"] w_local_data_foo[label="...->foo = 42;"] w_local_data_bar[label="...->bar = 666;"] w_shared_data[label="shared_data =\nlocal_data;", style=filled, fillcolor="#69db7c"] w_shared_data -> w_local_data; w_local_data_foo -> w_local_data; w_local_data_bar -> w_local_data; }$

local_data = new data;     // <-- write #1 (stack)
local_data->foo = 42;      // <-- write #2 (heap)
local_data->bar = 666;     // <-- write #3 (heap)
shared_data = local_data;  // <-- write #4 (global/publish)

../../../../../../../_images/cpu-store-buffer-depgraph.svg

Store Reordering#

3!==6 possible store orderings; for example …

Linear, as in the code

local_data = new data;
local_data->foo = 42;
local_data->bar = 666;
shared_data = local_data;         // <-- publish

Another legal order. For some reason: “Stores to global memory currently preferred because other stores to the same cache line are already waiting”,
```
local_data = new data;
shared_data = local_data;         // <-- publish
local_data->foo = 42;
local_data->bar = 666;
```

Store Reordering On Multicore#

Single: not a problem at all
⟶ One core will see the effect of its own writes immediately
But multi …

code/publish-multi-unsafe.cpp#

#include <thread>
#include <print>

struct data
{
    int foo;
    int bar;
};
data* shared_data;

int main()
{
    std::thread announcer([](){
        sleep(2);

        data* local_data = new data;                   // <-- write #1
        local_data->foo = 42;                          // <-- write #2
        local_data->bar = 666;                         // <-- write #3
        shared_data = local_data;                      // <-- write #4
    });

    while (true)
        if (shared_data) {
            std::println("foo {}, bar {}", shared_data->foo, shared_data->bar);
            break;
        }

    announcer.join();
    delete shared_data;
    return 0;
}

../../../../../../../_images/cpu-store-buffer-multicore.svg

$ ./c++11-memory-model-publish-multi-unsafe
foo 42, bar 666           # <-- hopefully

And Volatile?#

volatile data* shared_data;

Prevents the compiler from reordering across any access to shared_data
However in the single threaded case this is irrelevent
- As-if rule: compiler must not reorder in a way that could change the observed behavior (see here
  - ⟶ volatile only enforces this once more
- CPU reads what it last wrote
- Ideally, recently written data is taken from the cache closest to the CPU
- Maybe not even out in main memory yet
- ⟶ only breaks performance
Multicore
- Not that we are discussing hardware based (CPU side) reordering
- Compiler does similar things, at a different stage
- volatile is long gone
- ⟶ does not help at this point either

Note

Any use of volatile (other than to keep the compiler away from device registers) is pointless at most.

Anti-Reordering: Mutex#

Remember: “If in doubt use a mutex!”
Important: delineation if critical section

code/publish-multi-mutex.cpp#

#include <thread>
#include <mutex>
#include <print>

struct data
{
    int foo;
    int bar;
};
data* shared_data;
std::mutex shared_data_lock;

int main()
{
    std::thread announcer([](){
        sleep(2);

        {
            std::scoped_lock _(shared_data_lock);      // <-- protect all and more

            data* local_data = new data;
            local_data->foo = 42;
            local_data->bar = 666;
            shared_data = local_data;
        }
    });

    while (true)
    {
        std::scoped_lock _(shared_data_lock);          // <-- protect all and more
        if (shared_data) {
            std::println("foo {}, bar {}", shared_data->foo, shared_data->bar);
            break;
        }
    }

    announcer.join();
    delete shared_data;
    return 0;
}

Anti-Reordering: Delineating Critical Section#

Actual critical section is much smaller
In effect: load and store of shared_data
⟶ “The act of publication”

code/publish-multi-critical-section.cpp#

#include <thread>
#include <mutex>
#include <print>

struct data
{
    int foo;
    int bar;
};
data* shared_data;
std::mutex shared_data_lock;

int main()
{
    std::thread announcer([](){
        sleep(2);

        data* local_data = new data;
        local_data->foo = 42;
        local_data->bar = 666;
        {
            std::scoped_lock _(shared_data_lock);      // <-- protect store
            shared_data = local_data;
        }
    });

    while (true)
    {
        data* local_data;
        {
            std::scoped_lock _(shared_data_lock);      // <-- protect load
            local_data = shared_data;
        }
        if (local_data) {
            std::println("foo {}, bar {}", local_data->foo, local_data->bar);
            break;
        }
    }

    announcer.join();
    delete shared_data;
    return 0;
}

Why Does This Work?#

We use a mutex to linearize access to shared_data
Actually relying on something unobvious: the mutex’s flag
⟶ Barriers

../../../../../../../_images/cpu-store-buffer-multicore-mutex-barrier.svg

Sequential Consistency Without A Mutex#

Observation

We are protecting data* with a bool flag (the mutex?)
⟶ Why not wrap data* in std::atomic<data*>?
⟶ load and store atomic by definition

shared_data = local_data;
shared_data.store(local_data, std::memory_order_seq_cst);  // <-- same

local_data = shared_data;
local_data = shared_data.load(std::memory_order_seq_cst);  // <-- same

../../../../../../../_images/cpu-store-buffer-multicore-seq-cst.svg

code/publish-multi-atomic-seq-cst.cpp#

#include <thread>
#include <atomic>                                      // <-- 
#include <print>

struct data
{
    int foo;
    int bar;
};
std::atomic<data*> shared_data;                        // <-- data type: std::atomic<>

int main()
{
    std::thread announcer([](){
        sleep(2);

        data* local_data = new data;
        local_data->foo = 42;
        local_data->bar = 666;
        shared_data.store(
            local_data, 
            std::memory_order_seq_cst);                // <-- much like i++
    });

    while (true)
    {
        data* local_data = shared_data.load(
            std::memory_order_seq_cst);                // <-- much like i++
        if (local_data) {
            std::println("foo {}, bar {}", local_data->foo, local_data->bar);
            break;
        }
    }

    announcer.join();
    delete shared_data;
    return 0;
}

Isn’t Sequential Consistency Too Strong For Publish?#