次期C++に導入されるメモリバリアについて解説してみる

前のエントリで次期C++標準(通称C++0x)にatomic型とメモリバリアが導入されるという話をしました。今回はそのC++での実装について、もう少し深く追いかけてみます。
スライド資料では「atomic操作 ＋ acquire/releaseバリア」が基本であると書きましたが、実際に次期C++に導入される予定のatomic APIは、もう少し複雑な仕様になっています。一番の違いは、メモリバリアの種類が増えていることです。
次期C++標準の現在のドラフトでは、メモリバリアの種類を表すenum型の定義は以下のようになっています。

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

これらのうち、 memory_order_relaxed はメモリバリア効果を全く持たないことを示しており、 memory_order_acquire と memory_order_release はそれぞれ acquire と release のメモリバリア効果を持つことを示しています。また、 memory_order_acq_rel は読み込みと書き込みを同時に行う操作(いわゆる read-modify-write 操作)に対して指定可能で、acquire と release の両方のメモリバリア効果を持つことを示しています。
ところが、実際にatomicクラスに定義されているメンバ関数では、これらよりも「更に強い」メモリバリア指定がデフォルト値となっています。それが、上記enum型の最後に宣言されている memory_order_seq_cst です。
memory_order_seq_cst というメモリバリア指定は Sequential consistency という性質を満たすことを要求しますが、この Sequential consistency について説明する前に、まずは acquire/release バリアを使用した場合に起こり得る奇妙な例を挙げてみます。

// 初期値
std::atomic a(0), b(0);

// Thread 1
a.store(1, std::memory_order_release);

// Thread 2
b.store(1, std::memory_order_release);

// Thread 3
int r1 = a.load(std::memory_order_acquire);
int r2 = b.load(std::memory_order_acquire);

// Thread 4
int r3 = b.load(std::memory_order_acquire);
int r4 = a.load(std::memory_order_acquire);


r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0
という実行結果は起こり得る。

上のコードは、2つのスレッドがそれぞれ別のatomic変数に書き込むとき、その書き込みが他スレッドからどう見えるか、という例です。
r1 == 1 && r2 == 0 という結果が得られたということは、スレッド3からはスレッド1のstore操作がスレッド2よりも先に起こったように見えたことになります。一方、 r3 == 1 && r4 == 0 という結果より、スレッド4からはスレッド2のstore操作のほうが先に起こったように見えているわけです。この2つが両立することは奇妙に思えますが、acquire/releaseメモリバリアはこの様な結果が起こることを認めています。
これを簡単に言うと、「acquire/releaseバリアでは、異なるスレッドがそれぞれ別のatomic変数に対して書き込みを行ったとき、その順序はスレッドごとに違って見えることがある」ということになります。
一方、Sequential consistency ではこの様な挙動は許されません。つまり、以下のようになります。

// 初期値
std::atomic a(0), b(0);

// Thread 1
a.store(1, std::memory_order_seq_cst);

// Thread 2
b.store(1, std::memory_order_seq_cst);

// Thread 3
int r1 = a.load(std::memory_order_seq_cst);
int r2 = b.load(std::memory_order_seq_cst);

// Thread 4
int r3 = b.load(std::memory_order_seq_cst);
int r4 = a.load(std::memory_order_seq_cst);


r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0
という実行結果は起こり得ない。

このように、メモリバリアとして memory_order_seq_cst を使用していれば、異なるatomic変数への書き込みが、どのスレッドからも同じ順序に見えることが保証されます。

Sequential consistencyのオーバーヘッド

ところで、なぜ Sequential consistency を持たない acquire/release バリアが用意されているのでしょうか? それは、Sequential consistency を満たすためには少なからぬ実行コストがかかるからです。
特に NUMA のようなアーキテクチャでは、「異なるメモリ位置に対する書き込みが、全てのプロセッサから同じ順序で観測されなければならない」という Sequential consistency の要求を満たすことは困難です。そのため、C++ では Sequential consistency を要求するメモリバリアと要求しないメモリバリアの両方を用意しているわけです。
メモリバリアの種類を明示的に指定しない場合、 Sequential consistency を要求する memory_order_seq_cst がデフォルトとなります。「ゼロオーバーヘッド原則」を掲げ、徹底的にパフォーマンスにこだわっているはずの C++ にしては珍しく、メモリバリアに関しては最もオーバーヘッドの大きいものがデフォルトになっているのは興味深いですね。

acquire/release メモリバリアでは不十分な例

さて、 acquire/release バリアの挙動についてもう少し例を挙げてみます。最初の例でスレッド1と3、2と4をそれぞれ合体させると以下のようになります。

// 初期値
std::atomic a(0), b(0);

// Thread 1
a.store(1, std::memory_order_release);
int r1 = a.load(std::memory_order_acquire);
int r2 = b.load(std::memory_order_acquire);

// Thread 2
b.store(1, std::memory_order_release);
int r3 = b.load(std::memory_order_acquire);
int r4 = a.load(std::memory_order_acquire);


r2 == 0 && r4 == 0 という実行結果は起こり得る。
(一方、 r1 == 1 && r3 == 1 は常に保証される)

この r2 == 0 && r4 == 0 という実行結果はとても奇妙なものに見えますが、やはり正当なものです。
さらに、上の例から r1, r3 を省くと以下のようになります。

// 初期値
std::atomic a(0), b(0);

// Thread 1
a.store(1, std::memory_order_release);
int r2 = b.load(std::memory_order_acquire);

// Thread 2
b.store(1, std::memory_order_release);
int r4 = a.load(std::memory_order_acquire);


r2 == 0 && r4 == 0 という実行結果は起こり得る。

これはデッカーのアルゴリズムで使われている形そのものです。つまり、「acquire/release バリアだけでは、デッカーのアルゴリズムを実装することは出来ない」ということになります。
これは、acquire/release バリアが Sequential consistency を持たないことによるものなので、メモリバリアを memory_order_seq_cst に変更すれば、上の例でも r2 == 0 && r4 == 0 とはならないことが保証されて、デッカーのアルゴリズムを実装することが出来ます。

x86/x64におけるメモリバリアのオーバーヘッド

最後に、各メモリバリアのオーバーヘッドがどれだけ違うか、具体例を挙げてみましょう。
"C++ Concurrency in Action" の著者である Anthony Williams さんのblogに、x86/x64アーキテクチャでの各メモリバリアを実装する方針についての解説があったので引用します。*1

Memory Ordering	Store	Load
std::memory_order_relaxed	MOV [mem],reg	MOV reg,[mem]
std::memory_order_acquire	n/a	MOV reg,[mem]
std::memory_order_release	MOV [mem],reg	n/a
std::memory_order_seq_cst	XCHG [mem],reg *2	MOV reg,[mem]

x86/x64アーキテクチャでは、メモリアクセスの順序を保証したいときでも、大抵のケースでは明示的なメモリバリア命令を必要としません。いわゆる「強いメモリモデル」を採用しているアーキテクチャということになります。そのため、C++のatomic型の実装についても、基本的には単なるmov命令を発行するだけでOKとなります。(もちろん、コンパイラ上でのリオーダーの抑制は必要ですが。)
しかし、memory_order_seq_cst メモリバリアを伴う書き込みだけは例外です。強いメモリモデルを採用するx86/x64アーキテクチャにおいても、Sequential consistency を満たすためには実行コストの高い命令(xchg命令)を発行しなければならないのです。このことは逆に、Sequential consistency が必要でない場合は、デフォルトの memory_order_seq_cst の代わりに memory_order_release を用いることで性能向上を図れる、ということにもなります。
とは言うものの、実際は挙動のわかりやすさを重視して常に memory_order_seq_cst を使うべきでしょう。マルチスレッドのバグは分かりにくく、再現性も乏しいことが多いので、よほどのことがない限り安全側に寄せたコードを書いたほうが良いと思います。
続き

*1:この実装方針は、IntelやAMDのマニュアルの記述からも導き出すことができます。

*2:かわりに "MOV [mem],reg ; MFENCE" という命令列でもよいです。ただし、MFENCEはPentium4以降(SSE2)で追加された命令です。

volatile爆発しろ!

volatileという英単語には「爆発しやすい」という意味があるようですね。豆知識。
さて、前エントリのスライドで説明したように、マルチスレッドプログラムを正しく動作させるためにはCPUやコンパイラによるリオーダーを制限することが重要であり、そのためにメモリバリア(メモリフェンス)という仕組みがあるわけです。そして、CやC++のvolatile変数はメモリバリアとしての効果を持っていない、という問題点について指摘しました。この部分をもう少し掘り下げてみます。
マルチスレッドプログラムを正しく同期化させるために必要な「メモリバリア付きアトミック操作」について、それが正しく動作するために満たすべきチェックポイントを挙げると以下になります。

1. コンパイラは、その操作自体を最適化によって消去してしまったりしない。
2. コンパイラは、その操作をアトミックに実行できる命令を出力する。
3. コンパイラは、その操作をまたいだリオーダーを行わない。(メモリバリアで指定された方向について)
4. CPUは、コンパイラの出力するアトミック命令をまたいだリオーダーを行わない。(メモリバリアで指定された方向について)
5. (4が×の場合)コンパイラは、CPUのリオーダーを抑制するためのメモリバリア命令を一緒に出力する。

この 1, 2, 3, 4 または 1, 2, 3, 5 が○でないと「メモリバリア付きアトミック操作」としては欠陥があることになりますが、実際にvolatile変数へのloadやstoreについて調べてみると、以下のような結果となります。*1

gcc(x86) aligned volatile int
   1.○ 2.○ 3.× 4.○ 5.−
gcc(x86) aligned volatile long long
   1.○ 2.× 3.× 4.− 5.−
gcc(PowerPC) aligned volatile int
   1.○ 2.○ 3.× 4.× 5.×
VC++2005より前(x86) aligned volatile int
   1.○ 2.○ 3.× 4.○ 5.−
VC++2005以降(x86) aligned volatile int
   1.○ 2.○ 3.○ 4.○ 5.−
VC++2005以降(Xbox 360/PowerPC) aligned volatile int
   1.○ 2.○ 3.○ 4.× 5.×

ご覧の通り、「VC++2005以降(x86)」以外は全滅です。だからといって「volatile爆発しろ!」なんて叫んではいけません。そもそも C/C++ の仕様通りの動作なわけですから。
ちなみに、先ほどのVC++の結果については以下の解説文書を参考にしました。
Xbox 360 と Microsoft Windows でのロックレス プログラミングの考慮事項
この文書によると、アトミック操作として一般的に知られているInterlocked*命令も、PowerPCアーキテクチャ(Xbox 360)ではメモリバリア効果が不十分なことがあるので注意しなければならないようです。先ほどと同じチェックポイントで確認すると以下のようになります。

VC++(x86) InterlockedIncrement
   1.○ 2.○ 3.○ 4.○ 5.−
VC++(Xbox 360/PowerPC) InterlockedIncrement
   1.○ 2.○ 3.○ 4.× 5.×
VC++(Xbox 360/PowerPC) InterlockedIncrementAcquire/InterlockedIncrementRelease
   1.○ 2.○ 3.○ 4.× 5.○

このように、PowerPCなどの弱いメモリモデルを採用しているCPUでは、メモリバリアの有無についても特に注意しなければなりません。
続き

*1:loadについてはacquireバリアの、storeについてはreleaseバリアの有無について調べています。

そろそろvolatileについて一言いっておくか

先月、CBUGとわんくまの勉強会にて、アトミック変数とかメモリバリアとかvolatileとかについて話をしてきました。
ちょっと遅くなりましたが、そのときの講演資料を一つにまとめたので、ここで公開しておきます。あと、補足記事も追加していってます。

• volatileの実装の詳細について
• C++0xのメモリバリアについて(その1)
• C++0xのメモリバリアについて(その2)
• Double-Checked Lockingについて

そろそろvolatileについて一言いっておくか

View more presentations or Upload your own.