.. include:: ``atomic<>``: The C++ Memory Model ================================== .. topic:: Documentation * `Memory model (cppreference.com) `__ * `std::memory_order (cppreference.com) `__ .. topic:: See also * :doc:`/trainings/material/soup/cxx/cxx11/multithreading/index` * :doc:`/trainings/material/soup/linux/sysprog/posix-threads/index` * :doc:`/trainings/material/soup/linux/why/threads/index` Foreword -------- * A *memory model* is an attept to find a common denominator across *atomicity* and *memory order* features of different CPUs .. code-block:: c++ enum memory_order { memory_order_relaxed, memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_seq_cst }; .. _cxx-memory-model-integer-increment-single-thread: Integer Increments (Single Threaded) ------------------------------------ .. image:: single-core-memonly.svg .. literalinclude:: code/load-modify-store-single.cpp :caption: :download:`code/load-modify-store-single.cpp` :language: c++ .. code-block:: console $ ./c++11-memory-model-load-modify-store-single expected 1000000000, real 1000000000 .. _cxx-memory-model-integer-increment-not-atomic: Integer Increments? ------------------- * ``counter++`` is not *atomic* * Breaks down into multiple instructions * |longrightarrow| Load/Modify/Store (Read/Modify/Write) .. list-table:: :align: left * * Source code * What becomes of it * * .. code-block:: c++ counter++; * .. code-block:: c++ auto reg = counter; // <-- load into register reg++; // <-- increment register counter = reg; // <-- write back to memory .. _cxx-memory-model-integer-increment-mother: Integer Increment: The Mother Of Race Conditions ------------------------------------------------ .. image:: multi-core-memonly.svg .. literalinclude:: code/load-modify-store.cpp :caption: :download:`code/load-modify-store.cpp` :language: c++ .. code-block:: console $ ./c++11-memory-model-load-modify-store expected 2000000000, real 1004072808 .. _cxx-memory-model-integer-increment-lms: Load/Modify/Store Conflict -------------------------- * Physical parallelism: 2 CPUs * Virtual parallelism: single CPU + scheduler context switch * |longrightarrow| extremely rare * |longrightarrow| extremely nasty .. list-table:: :align: left * * CPU1 * CPU2 * * .. code-block:: c++ auto reg = counter; reg++; . . . counter = reg; * .. code-block:: c++ . . auto reg = counter; reg++; counter = reg; . Anti-Conflict: Mutex -------------------- .. topic:: See also * :doc:`POSIX Threads: Mutex ` .. topic:: Documentation * `std::mutex `__ * Downside: context switch on contention |longrightarrow| try to minimize contention * Upside: always safe - "If in doubt use a mutex!"* .. literalinclude:: code/load-modify-store-mutex.cpp :caption: :download:`code/load-modify-store-mutex.cpp` :language: c++ Anti-Conflict: ``std::atomic<>`` -------------------------------- .. topic:: See also * :doc:`/trainings/material/soup/linux/sysprog/posix-threads/040-mutex/topic` * :doc:`/trainings/material/soup/cxx/cxx11/multithreading/atomic-shared-ptr/topic` .. topic:: Documentation * `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 |longrightarrow| internally, a mutex is used to implement atomicity .. literalinclude:: code/load-modify-store-seq-cst.cpp :caption: :download:`code/load-modify-store-seq-cst.cpp` :language: c++ 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 (:ref:`read on `) * There are sure better implementations * Not free though Is ``std::atomic<>`` Lock Free? ------------------------------- .. topic:: Documentation * `std::atomic_flag `__ * `std::atomic::is_lock_free `__ * `std::atomic::is_always_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``) .. literalinclude:: code/atomic-lock-free.cpp :caption: :download:`code/atomic-lock-free.cpp` :language: c++ .. _cxx11-memory-model-sample-cache-multicore: Modern CPUs Are More Complex ---------------------------- * Reads are fast * Writes can take * |longrightarrow| Store buffer * |longrightarrow| Cache hierarchies .. list-table:: :align: left * * .. image:: snapdragon.webp :scale: 40% * .. image:: small_broadwell-e-die-map.webp :scale: 50% Towards Out-Of-Order Memory Access: What Matters? (Cache/Memory) ---------------------------------------------------------------- .. list-table:: :align: left * * **Full detail** .. image:: cpu-full.svg * **Cache And Memory** .. image:: cpu-main-memory-caches-encapsulate-pre.svg * * **Cache And Memory Is Transparent** .. image:: cpu-main-memory-caches-encapsulate.svg * **And Store Buffer?** .. image:: cpu-store-buffer-pre.svg Towards Out-Of-Order Memory Access: What Matters? (CPU/Store Buffer) -------------------------------------------------------------------- * *Store buffer* is where reordering is done * Cache and memory *just works* .. image:: cpu-store-buffer.svg Publishing Something -------------------- .. literalinclude:: code/publish-intro.cpp :caption: :download:`code/publish-intro.cpp` :language: c++ Store Dependencies ------------------ A reordering engine (Intel conservative, ARM/RISC-V aggressive) can consider the following store dependencies. .. list-table:: :align: left :widths: 70,30 * * .. graphviz:: 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; } .. code-block:: c++ 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) * .. image:: cpu-store-buffer-depgraph.svg Store Reordering ---------------- * ``3!==6`` possible store orderings; for example ... * Linear, as in the code .. code-block:: c++ 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", .. code-block:: c++ 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 * |longrightarrow| One core will see the effect of its own writes immediately * But multi ... .. literalinclude:: code/publish-multi-unsafe.cpp :caption: :download:`code/publish-multi-unsafe.cpp` :language: c++ .. image:: cpu-store-buffer-multicore.svg .. code-block:: console $ ./c++11-memory-model-publish-multi-unsafe foo 42, bar 666 # <-- hopefully And Volatile? ------------- .. topic:: Documentation * `The as-if rule (cppreference.com) `__ .. code-block:: c++ 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 `__ * |longrightarrow| ``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 * |longrightarrow| 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 * |longrightarrow| 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* .. literalinclude:: code/publish-multi-mutex.cpp :caption: :download:`code/publish-multi-mutex.cpp` :language: c++ Anti-Reordering: Delineating Critical Section --------------------------------------------- * Actual *critical section* is much smaller * In effect: load and store of ``shared_data`` * |longrightarrow| "The act of publication" .. literalinclude:: code/publish-multi-critical-section.cpp :caption: :download:`code/publish-multi-critical-section.cpp` :language: c++ Why Does This Work? ------------------- * We use a mutex to *linearize* access to ``shared_data`` * Actually relying on something unobvious: the mutex's *flag* * |longrightarrow| *Barriers* .. image:: cpu-store-buffer-multicore-mutex-barrier.svg Sequential Consistency Without A Mutex -------------------------------------- .. topic:: Documentation * `std::memory_order (cppreference.com) `__ **Observation** * We are protecting ``data*`` with a ``bool`` flag (the mutex?) * |longrightarrow| Why not wrap ``data*`` in ``std::atomic``? * |longrightarrow| load and store atomic *by definition* .. code-block:: c++ 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 .. image:: cpu-store-buffer-multicore-seq-cst.svg .. literalinclude:: code/publish-multi-atomic-seq-cst.cpp :caption: :download:`code/publish-multi-atomic-seq-cst.cpp` :language: c++ Isn't Sequential Consistency Too Strong For *Publish*? ------------------------------------------------------ .. topic:: Documentation * `std::memory_order (cppreference.com) `__ **Observation** * Publisher: unlike ``std::atomic::operator++()``, we only store |longrightarrow| *let-go* * Consumer: unlike "A READ from a location must return the value of the last WRITE to that location", we only want *Once shared_data is valid, I want all stores preceding that* (``foo`` and ``bar``) *to be valid* * |longrightarrow| Memory orders: *release* and *acquire* (`here `__) .. literalinclude:: code/publish-multi-atomic-acq-rel.cpp :caption: :download:`code/publish-multi-atomic-acq-rel.cpp` :language: c++ Links ----- * `Memory disambiguation (Wikipedia) `__ * `Out-of-order execution (Wikipedia) `__ * `C++ and Beyond 2012: Herb Sutter - atomic Weapons 1 of 2 `__ .. raw:: html * `C++ and Beyond 2012: Herb Sutter - atomic Weapons 2 of 2 `__ .. raw:: html * `What is RCU, Fundamentally? `__ * `A Relaxed Guide to memory_order_relaxed - Paul E. McKenney & Hans Boehm - CppCon 2020 `__ .. raw:: html * `Lightning Talk: A Spinlock Implementation - Fedor Pikus - CppNow 2022 `__ .. raw:: html * `CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced. What do they really do?” `__ .. raw:: html