C++11のmemory_orderの使い分け (4)
前回まででアトミック変数とフェンスの memory_order の基本的な使い方を全て解説しました。今回はメモリバリアを減らして高速化する手法について解説します。ただし、consume を使った高速化に関しては扱いません。また、今回の内容はあくまでメモリバリアの理解のために解説しています。これから紹介する内容を実際に高速化のために用いる場合は、パフォーマンステストを行って効果を確かめてから使うようにしてください。
まずはバリアの負荷の大きさを解説します。
メモリバリアの種類による負荷の違い
store命令
relaxed < release < seq_cst
load命令
relaxed < acquire < seq_cst
read-modify-write命令
relaxed < release/acquire < acq_rel < seq_cst
fence
relaxed < release/acquire < acq_rel < seq_cst
近接したメモリバリア
メモリバリアは、メモリ読み書きの順番を入れ替えるような最適化を制限します。そのため、メモリ読み書きを最適化できる場所でメモリバリアを使うと速度が大きく落ちることがあります。その後、その近くに同じ種類のバリアを追加しても、既に最適化が制限されているため、大きな速度変化は起こりにくいです。
バリア無し <<< バリア1つ < 複数のバリア(同種) << 複数のバリア(異種)
フェンスとアトミック命令
フェンスとアトミック命令の負荷は、一般的には次のような関係になります。
releaseバリア
release store < release fence + relaxed store
acquireバリア
acquire load < relaxed load + acquire fence
seq_cstバリア
seq_cst load < seq_cst store < seq_cst fence
seq_cst store + seq_cst load < relaxed store + seq_cst fence + relaxed load
以上の関係を意識しながらメモリバリアの実行回数を減らす方法を考えていきます。
if文の中と外
下のコードを見てください。
// 初期値
int data;
std::atomic_int x(0);
// スレッド 1
data = 100;
x.store(10, std::memory_order_release);
// スレッド 2
int r = x.load(std::memory_order_acquire);
if (r == 10) {
data; // data == 100 が保証される
} else {
// data == 100 とは限らない
}
このコードでは、スレッド 1 の x への書き込み (10) をスレッド 2 が読み取れた時、スレッド 2 は スレッド 1 の data への書き込み (100) が読み取れます。もし、スレッド 1 の x への書き込み (10) をスレッド 2 がまだ読み取れなければ、フェンスの有無に関わらず data の値が何になるのかは分かりません。ということは、フェンスは if 文の中に入れても保証は変わりません。
// 初期値
int data;
std::atomic_int x(0);
// スレッド 1
data = 100;
x.store(10, std::memory_order_release);
// スレッド 2
int r = x.load(std::memory_order_relaxed);
if (r == 10) {
std::atomic_thread_fence(std::memory_order_acquire);
data; // data == 100 が保証される
} else {
// data == 100 とは限らない
}
if 文の条件を満たさなかった時、フェンスが実行されないので高速化できるかもしれません。ただし、relaxed load + acquire fence よりも acquire load の方が一般的に速いので、必ずしも速くなるとは限りません。else 節の最適化をコンパイラがどこまで出来るかにかかっています。
下のコードでは if 文が複数あるので、全ての if 文の中にフェンスを入れるより、if 文の外でまとめた方が良さそうです。
// 初期値
int data1, data2;
std::atomic_int x(0);
// スレッド 1
data1 = 100;
x.store(1, std::memory_order_release);
// スレッド 2
data2 = 200;
x.store(2, std::memory_order_release);
// スレッド 3
int r = x.load(std::memory_order_acquire);
if (r == 1) {
data1; // data1 == 100 が保証される
}
if (r == 2) {
data2; // data2 == 200 が保証される
}
ループの外に出す
下のコードを見てください。
// 初期値
int data;
std::atomic_int x(0);
// スレッド 1
data = 100;
x.store(10, std::memory_order_release);
// スレッド 2
int r;
do {
r = x.load(std::memory_order_acquire);
} while (r != 10);
data; // data == 100 が保証される
（他のスレッドの処理が終わるのを待つ時点で高速化してもほとんど意味が無いのですが、そこは目をつぶってください。）このコードではループの中で acquire フェンスを何度も実行しています。しかし、acquire フェンスが必要なのは data の読み取りだけです。そして、data はループの外でしか読み取られていません。なので、acquire フェンスはループの外に出せます。
// 初期値
int data;
std::atomic_int x(0);
// スレッド 1
data = 100;
x.store(10, std::memory_order_release);
// スレッド 2
int r;
do {
r = x.load(std::memory_order_relaxed);
} while (r != 10);
std::atomic_thread_fence(std::memory_order_acquire);
data; // data == 100 が保証される
上記のケースではループ中で x 以外の値を読み取っていないので、ループ内に acquire フェンスを書いてもコンパイラの最適化でフェンスだけループの外に出されると思います。ですが、コンパイラにはどの値にフェンスが必要なのか分からないので、ループ内で全然関係ない値を読み取るだけでも最適化されなくなる可能性があります。実際、ループ内でメモリバリアが必要なケースもあります。
// 初期値
int data1, data2;
std::atomic<int*> x(nullptr);
// スレッド 1
data1 = 100;
data2 = 10;
x.store(&data2, std::memory_order_release);
// スレッド 2
int* r;
do {
r = x.load(std::memory_order_acquire);
} while (r == nullptr || *r != 10);
data1; // data1 == 100 が保証される
上記のコードはループ内で acquire の効果が無いと do-while 文の条件の *r の読み取りで保証が無くなります。 ちなみに、nullptr の可能性が無い場合、スレッド 2 は下のような書き方もできます。
// スレッド 2 while (*x.load(std::memory_order_acquire) != 10); data1; // data1 == 100 が保証される
* より . の方が優先順位が高いので、 x.load の戻り値に * が付きます。
この場合 load には acquire 以上のバリアが必要なのは明らかです。
releaseバリアを減らす
下のコードを見てください。
// 初期値
int data;
std::atomic_int x(0), y(0);
// スレッド 1
data = 100;
x.store(10, std::memory_order_release);
y.store(20, std::memory_order_release);
// スレッド 2
int r = x.load(std::memory_order_acquire);
if (r == 10) {
data; // data == 100 が保証される
}
// スレッド 3
int r = y.load(std::memory_order_acquire);
if (r == 20) {
data; // data == 100 が保証される
// x == 10 も保証されている
}
上記のコードでは、スレッド 1 の x への書き込み (10) が読み取れれば data (100) も読み取れます。そして、スレッド 1 の y への書き込み (20) が読み取れれば data (100) だけでなく、 x (10) も読み取れます。もし、y を読み取れた時に x を読み取る必要が無いのであればメモリバリアを減らせます。
// 初期値
int data;
std::atomic_int x(0), y(0);
// スレッド 1
data = 100;
std::atomic_thread_fence(std::memory_order_release);
x.store(10, std::memory_order_relaxed);
y.store(20, std::memory_order_relaxed);
// スレッド 2
int r = x.load(std::memory_order_acquire);
if (r == 10) {
data; // data == 100 が保証される
}
// スレッド 3
int r = y.load(std::memory_order_acquire);
if (r == 20) {
data; // data == 100 が保証される
// x == 10 とは限らない
}
一般的に release fence + relaxed store より release store の方が速いので、release store + release store より release fence + relaxed store + relaxed store の方が速いという保証はありませんが、速くなる可能性は高いです。
acquireバリアを減らす
下のコードを見てください。
// 初期値 int data1, data2; std::atomic_int x(0), y(0); // スレッド 1 data1 = 100; x.store(10, std::memory_order_release); // スレッド 2 data2 = 200; y.store(20, std::memory_order_release); // スレッド 3 while (x.load(std::memory_order_acquire) != 10); // この時点で data1 == 100 が保証される while (y.load(std::memory_order_acquire) != 20); // この時点で data2 == 200 が保証される data1 + data2; // data1 + data2 == 300 が保証される
上記のコードでは、x == 10 が読み取れた時 data1 == 100 が読み取れ、y == 20 が読み取れた時 data2 == 200 が読み取れます。ですが、x == 10 が読み取れた時点では data1 を読み取れる必要が無いので、フェンスを使って y == 20 が読み取れた後にまとめることができます。
// 初期値 int data1, data2; std::atomic_int x(0), y(0); // スレッド 1 data1 = 100; x.store(10, std::memory_order_release); // スレッド 2 data2 = 200; y.store(20, std::memory_order_release); // スレッド 3 while (x.load(std::memory_order_relaxed) != 10); // この時点では data1 == 100 とは限らない while (y.load(std::memory_order_relaxed) != 20); // この時点では data2 == 200 とは限らない std::atomic_thread_fence(std::memory_order_acquire); // この時点で data1 == 100 と data2 == 200 が保証される data1 + data2; // data1 + data2 == 300 が保証される
seq_cstバリアを減らす
seq_cst バリアは順序一貫性のために必要でした。下のコードを見てください。
// 初期値 std::atomic_int x(0), y(0); // スレッド 1 x.store(1, std::memory_order_seq_cst); // スレッド 2 y.store(1, std::memory_order_seq_cst); // スレッド 3 int rx = x.load(std::memory_order_seq_cst); int ry = y.load(std::memory_order_seq_cst); // スレッド 4 int ry = y.load(std::memory_order_seq_cst); int rx = x.load(std::memory_order_seq_cst);
このコードでは seq_cst バリアが正しく使われているのでスレッド 1 の x への書き込み (1) とスレッド 2 の y への書き込み (1) はどのスレッドからも同じ順序で書き込まれたように見えます。例えば、スレッド 3 で rx == 1, ry == 0 という結果になった時、スレッド 1 の x.store が先、スレッド 2 の y.store が後という順序が確定するため、スレッド 4 で ry == 1, rx == 0 という結果になることはありません。
上記のコードはフェンスを使うと、下のように書き換えられます。
// 初期値 std::atomic_int x(0), y(0); // スレッド 1 x.store(1, std::memory_order_relaxed); // スレッド 2 y.store(1, std::memory_order_relaxed); // スレッド 3 int rx = x.load(std::memory_order_relaxed); std::atomic_thread_fence(std::memory_order_seq_cst); int ry = y.load(std::memory_order_relaxed); // スレッド 4 int ry = y.load(std::memory_order_relaxed); std::atomic_thread_fence(std::memory_order_seq_cst); int rx = x.load(std::memory_order_relaxed);
上記のコードではフェンスに順序一貫性が成り立ちます。
スレッド 3 のフェンスが先、スレッド 4 のフェンスが後だった場合、スレッド 3 で rx == 1 ならスレッド 4 の rx == 1 が確定します。
スレッド 4 のフェンスが先、スレッド 3 のフェンスが後だった場合、スレッド 4 で ry == 1 ならスレッド 3 の ry == 1 が確定します。
どちらの場合でも、スレッド 3 で rx == 1, ry == 0、スレッド 4 で ry == 1, rx == 0 という結果が同時に起こることはありません。
スレッド 1 とスレッド 2 にはメモリバリアが無いですが、順序一貫性があるのと同じ結果になります。この場合、スレッド 1 とスレッド 2 は間違いなく高速化されてます。スレッド 3 とスレッド 4 はメモリバリアの数は減っていますが、逆に遅くなっている可能性が高いです。全体の負荷はどうなるか分かりません。書き込み側の負荷と読み取り側の負荷のバランスを調整したい時に使えます。
この解説について
これまでの解説は C++11 の仕様書 (に最も近いドラフト N3337(pdf) ) を参考にしました。この仕様書は用語定義と解説が分かれているのですが、既に定義された用語に後からいろいろ付け足したりと、仮に日本語だったとしても読み間違いが起きそうな書き方になっています。そのため、筆者の英語力では絶対に読み間違えていないという保障はありません。もし、信頼できる情報が欲しいのであれば、仕様書の 1.10 にマルチスレッド関係の用語定義、29 にアトミック変数やフェンスの解説が書かれてあるので、頑張ってそちらを読んでみてください。そして、間違いがあれば教えてください。たぶん無いとは思いますが。
余談ですが
4回に分けて解説してきましたが、書いてる途中でうまい説明を思いついたり、説明し忘れた部分を思い出したりした部分がいくつかあります。既に公開してしまった部分を大きく修正するのはまずいと思い、そのまま続けてきたのですが、正直書き直した方が分かりやすい気もしています。これが連載記事の難しさなのかなと、書き手の気持ちを学ぶ良い機会となりました。また、簡単な解説を思いつかず解説自体をあきらめた部分もあります。いつか機会があれば書き直してブログよりも適切な場所にまとめたいです。
