メモリオーダリング入門


この文書ではC++のメモリオーダリング指定についてその必要性と使い方について述べる。

## マルチスレッドでおきること

x86-64アーキテクチャにおいて基本的に`int`変数への代入、読み取りは**アトミック**である。(もちろんこれはC++の仕様ではなくプラットフォーム依存の挙動である。)

以下のようなコードが考えてみる。


```cpp:main.cpp
#include <future>
#include <cassert>

static int a = 0;
static int b = 0;

void func() {
    for(;;) {
        if (b == 20) {
            assert(a == 10);
            break;
        }
    }
}

int main(int argc, char *argv[])
{
    for (;;) {
        auto future = std::async(std::launch::async, []{func();});
        a = 10;
        b = 20;

        future.wait();
        a = 0;
        b = 0;
    }

    return 0;
}
```

`b==20`となるまで待ち続ける`func()`を別スレッド(以下「スレッド1」)で実行する。その後`a=10`,`b=20`の順番で代入する。

普通に考えれば`b==20`であればそれより前に`a`に`10`が代入されているはずであり、`assert()`に引っかかるはずはない。

しかし実際はこうだ。

```sh
$ g++ -O2 -o main main.cpp

$ ./main
main: main.cpp:11: void func(): Assertion `a == 10' failed.
[1]    2528160 IOT instruction  ./main
```

つまり、メインスレッドからは`b==20`かつ`a==0`と見える可能性があるということだ。これが「**メモリオーダリング**」と呼ばれる問題領域である。

## 補足：アトミックとは

ここでアトミックについて簡単ににおさらいしておこう。

```cpp
static std::atomic<int> a = 0;

void thread1() {
    a = 10;
}

void thread2() {
    a = 20;
}

```

`thread1()`,`thread2()`がマルチスレッドや割り込み等でどのように実行されたとしても`a`を読み取ったとき値が`0,10,20`以外の値になることはない。これを「変数`a`は代入、読み取りにたいしてアトミックである」という。

逆に言うと`a`がアトミックでないなら場合によっては`0,10,20`以外の値を取りうるということである。


## 手っ取り早い解決策

C++においてこの問題を解決するのは非常に簡単である。`int`を`std::atomic<int>`に変えれば解決だ。

```cpp
#include <atomic>

static std::atomic<int> a = 0;
static std::atomic<int> b = 0;
```

しかし、上の例では一体何が起きたのか。そしてなぜ`std::atomic`を使うと解決するのか、以下で解説していく。

## プログラムは書いたとおりに実行されない

現代のコンパイラ、プロセッサ環境において以下にあげる要因によって書いた命令がそのままの順番では実行されない可能性がある。

1. コンパイラ要因: コンパイラが最適化の過程で命令の順番を入れ替える可能性がある。
2. プロセッサ要因: プロセッサが命令実行時に「OOO(Out of Order)実行」といって記述された順序とは異なる順序で命令を実行する可能性がある。


とはいえシングルスレッド、割り込みなしで動作している限りプログラマが上記要因を気にする必要は一切ないので安心してほしい。
(コンパイラ最適化においてもプロセッサ最適化においてもシングルスレッド内の挙動が変わってしまうような最適化は決して行われない。)

問題はマルチスレッドや割り込み環境においてである。マルチスレッドや割り込み環境では上記に上げた要因により冒頭で示して例のような自体が発生し得るのである。

## メモリモデル

上記状況に対してC++ではスレッド間でのメモリアクセスの順序を明確にするためにメモリモデルを導入した。これにより、異なるスレッドが共有データにアクセスする際の順序を制御し、一貫性を保つことが可能になる。

たとえば`std::atomic`であれば代入・参照動作に様々な順序に関する制約をかけることができる。(メモリオーダー指定)

## `std::atomic`の代入・参照操作

`std::atomic`における代入(例: `a=10`)は実際は以下メソッド呼び出しのシンタックスシュガーである。

```cpp
a.store(10, std::memory_ordering_seq_cst)
```

2つ目の引数はメモリオーダー指定と呼ばれ`std::memory_ordering_seq_cst`は最も強い制約の指定となっている。

つまり裏を返すと制約を必要最小限に弱めることで最適化により速度が向上する余地が大きくなるということであり、そしてバグが入り込む余地も大きくなるということである。

以下でメモリオーダー指定にどのようなものがあるか見ていこう。

## Relaxed オーダリング

1つの変数について順序を保証するオーダリングである。

```cpp

static std::atomic<int> a=0;

void thread1() {
    a.store(10, std::memory_order_relaxed);
    a.store(20, std::memory_order_relaxed);
}
```

つまり変数`a`を別のスレッドから観察したとき`a==10`を観察したのであれば、いつかは必ず`a==20`になるということである。

当たり前のように感じるかもしれないが、実は単純な`static int a`では仕様上はこの保証すら無いことに注意が必要である。

## Release/Acquire オーダリング

冒頭の例を`std::atomic`のデフォルトメモリーダーであるSequentially Consistent(後述)よりもゆるい制約で`assert()`に引っかからないコードに書き直すにはRelease/Acquireオーダーを使用することになる。

```cpp:main.cpp
#include <atomic>
#include <future>
#include <cassert>

static std::atomic<int> a = 0;
static std::atomic<int> b = 0;

void func() {
    for(;;) {
        if (b.load(std::memory_order_acquire) == 20) {
            assert(a.load(std::memory_order_relaxed) == 10);
            break;
        }
    }
}

int main(int argc, char *argv[])
{
    for (;;) {
        auto future = std::async(std::launch::async, []{func();});
        a.store(10, std::memory_order_relaxed);
        b.store(20, std::memory_order_release);

        future.wait();
        a = 0;
        b = 0;
    }

    return 0;
}
```

Release/Acquireによる制約は意外とシンプルである。

* Releaseより前にあるメモリ操作をRelease後にリオーダすることはできない。
* Acquireより後にあるメモリ操作をAcquire前にリオーダすることはできない。

この2つにより、下図のように`b==20`であればかならず`a==10`で有ることが保証される。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39647/6aeb2313-535b-a155-e997-1ef53f08b9b0.png)

なお上図にあるように`b.store(20)`と`b.load()`がまるで通信でもしているかのように矢印で接続されている図をよく見かけるが、`store()`, `load()`が特定の相手と通信するなどということは一切ないことに注意が必要である。
あくまで「もしbが20であることが観測できたらaは必ず10と観測される」ことが保証されるだけである

## Sequentially Consistent オーダリング

Sequentially Consistent オーダリングは最も強い制約を課す。つまり、

* 全てのスレッドについてSequentially Consistent オーダリングの操作は同じ順番に見えることが保証されている。

冒頭の例で`a`を`std::atomic<int>`に変更することで解決したのはこの性質のためだ。しかし最も最適化が制限されるオーダリングであるためパフォーマンスに敏感なプロジェクトでは使用に注意が必要な可能性もある。

## タネ本紹介

今回の記事は以下の書籍を参考にして記述した。Rustに関する書籍であるがメモリオーダリングに関してはRustとC++はほぼ一緒であるためRustについて学びつつC++についても理解を深められる。

https://www.oreilly.co.jp/books/9784814400515/