C++0xのメモリバリアをより深く解説してみる

もはや誰得レベルになりつつありますが、今回もメモリバリアについての話です。以前の話の続きになるので、まだの方は初回と前回のエントリを先にどうぞ。
さて、まず最初に、C++0xのatomicクラスを使った「正しく同期化されているコード」の例を挙げてみます。

struct Hoge {
   int  foo;
};

// 初期値
std::atomic p(nullptr);

// Thread 1
Hoge* r1 = new Hoge();
r1->foo = 42;
p.store(r1, std::memory_order_release);

// Thread 2
Hoge* r2;
do {
  r2 = p.load(std::memory_order_acquire);
} while (r2 == nullptr);
std::cout << r2->foo;   // 42が出力されることが保証される

Hogeインスタンスのメンバ変数 foo への読み書きに注目すると、アトミック変数 p を介して以下のような順序付けが成立しています。releaseやacquireメモリバリアの意味については初回の記事を参照してください。

r1->foo = 42
  ↓  releaseメモリバリアによる順序付け
p.store(r1, std::memory_order_release)
  ↓
r2 = p.load(std::memory_order_acquire)
  ↓  acquireメモリバリアによる順序付け
r2->foo

このような順序付けが成立している状態を「メンバ変数 foo へのアクセスが正しく同期化されている」と呼び、その結果、 r2->foo の値が42になることが保証されるのです。
では、次のコードはどうでしょうか?

// 初期値
std::atomic p(nullptr);

// Thread 1
Hoge* r1 = new Hoge();
r1->foo = 42;
p.store(r1, std::memory_order_release);

// Thread 2
Hoge* r2;
do {
  r2 = p.load(std::memory_order_relaxed);
} while (r2 == nullptr);
std::cout << r2->foo;   // Data race?

最初のコードとの違いは、Thread 2 側のメモリバリア指定が memory_order_relaxed (メモリバリア無し) に変わっている点です。つまり、先ほどの図で示した「acquireメモリバリアによる順序付け」が無くなっています。その結果、このコードはメンバ変数 foo への読み書きが正しく順序付けられていない、すなわち「正しく同期化されていない」不正なコードということになります。
でも、本当にこのコードは正しく動作しないのでしょうか? Thread 2において、式 r2->foo を評価するには、当然ながら r2 の値がわかっている必要があります。よって、明示的にacquireバリアを指定しなくても、 r2->foo の実行は p.load(...) より前にリオーダーされることはないと考えてよさそうです。従って、「r2->foo の結果は必ず 42 になる」と言い切ってもよさそうな気がします。
しかし、残念ながら一部のプロセッサではそうならないことが知られています(参考文献)。メモリバリアはキャッシュコヒーレンシの動作にも影響を与えているので、メモリバリアが無いとキャッシュメモリ内の古い値を読み込んでしまう可能性があるのです。そのため、acquireメモリバリアを省略した2つめのコードは、やはり正しく同期化されておらず不正だということになります。

Data-Dependency Ordering の導入

と、普通であればこの話はここで終了です。しかし、世の中にはパフォーマンスを変態的偏執的に追い求める人達が居ます*1。彼らはこう考えました。

「確かに一部のプロセッサでは正しく動作しないけれども、先ほどのようなケース(ある変数に対する読み込みの結果から、次にアクセスする変数のアドレスが求まるような場合)では、明示的なメモリバリア無しでも順序付けが保証されるプロセッサが沢山ある。そのようなプロセッサのために、メモリバリア無しでも正しく同期化されているとみなすことのできる特例を設けてはどうだろうか。そうすれば、acquireバリアのオーバーヘッドを削減できるはずだ。」

そこで、memory_order_acquire よりも「弱い」メモリバリアとして、「読み込んだ値に依存する式」に対してのみ順序付けを保証する memory_order_consume が定義されました。このような順序付けは "Data-Dependency Ordering" と呼ばれています。
コンパイラは、メモリバリアとして memory_order_consume が指定されている場所について、プロセッサの特性に従ってメモリバリア命令を発行すべきかどうかを判断します。 "Data-Dependency Ordering" が自動的に保証されるプロセッサではメモリバリア命令を発行せず、そうでないプロセッサではメモリバリア命令を発行する、といった感じです。
Data-Dependency Ordering を利用すると、先ほどの例は次のように書き換えることができます。

// 初期値
std::atomic p(nullptr);

// Thread 1
Hoge* r1 = new Hoge();
r1->foo = 42;
p.store(r1, std::memory_order_release);

// Thread 2
Hoge* r2;
do {
  r2 = p.load(std::memory_order_consume);
} while (r2 == nullptr);
std::cout << r2->foo;   // 42が出力されることが保証される

Thread 2において、 r2->foo は Data-Dependency Ordering によって p.load(std::memory_order_consume) の後に評価されることが保証されています。その結果、このコードは正しく同期化されていることになり、 r2->foo の結果が 42 となることも保証されます。この順序付けを詳しく書くと、以下のようになっています。

r1->foo = 42
  ↓  releaseメモリバリアによる順序付け
p.store(r1, std::memory_order_release)
  ↓
r2 = p.load(std::memory_order_consume)
  ↓  Data-Dependency Ordering
r2->foo

memory_order_acquire は「それより後の全ての文」に対して順序付けを保証するのに対し、 memory_order_consume は「読み込んだ値に依存する式だけ」にしか順序付けを保証しません。順序付けを保証する範囲が小さくなる代わりに、明示的なメモリバリア命令を発行しなくても大丈夫なケースが増えるのです。

Data-Dependency Ordering の詳細

Data-Dependency Ordering について、もう少し具体例を挙げてみましょう。

// 初期値
std::atomic b(false);
Hoge* p;

// Thread 1
p = new Hoge();
p->foo = 42;
b.store(true, std::memory_order_release);

// Thread 2
while (!b.load(std::memory_order_consume)) {
}
std::cout << p->foo;   // NG

このコードのThread 2側では、bool型のatomic変数 b と式 p->foo との間に Data-Dependency は存在していません。 b.load(...) の結果はwhileのループ条件として使われていますが、それとは独立して p->foo を先に評価することが可能だからです*2。よって、このコードは正しく順序付けられていない不正なコードということになります。
しかし、メモリバリアを memory_order_consume から memory_order_acquire に換えてやると、acquireメモリバリアの効果により両者の間に順序付けができるため、正しく同期化されたコードになります。
このように、 memory_order_consume を使用する際は、どこまで Data-Dependency が保証されているか常に注意していなければなりません。
もっと凝った例を挙げてみます。

// 初期値
std::atomic a(-1);
int table[10];

// Thread 1
table[3] = 5;
table[5] = -1;
a.store(3, std::memory_order_release);

// Thread 2
int r0, r1, r2, r3, r4, r5;
do {
  r0 = a.load(std::memory_order_consume);
} while (r0 < 0);
r1 = table[r0];    // OK
r2 = table[r1];    // OK
r3 = table[3];     // NG
r4 = table[r0 + 3 - r0];   // OK
r5 = (r2 < 0) ? table[3] : table[5];  // NG

順に説明していきましょう。whileループを抜けたときの r0 の値は 3 になります。そして式 table[r0] は r0 と Data-Dependency の関係にあるので、値 5 が得られることが保証されます。 Data-Dependency は推移的な関係なので、その次の table[r1] も値 -1 が保証されます。
次の式 table[3] は Data-Dependency が存在しないため data race となり、結果は未定義です。しかし、その次の table[r0 + 3 - r0] は、「r0 と Data-Dependency の関係がある」とみなすので data race とはなりません。この2つは単純な最適化で同一なものになってしまいそうですが、 Data-Dependency においては明確に区別されます。*3
最後の三項演算子を使った式は、一つ前のサンプルコードのときと同じく、条件分岐とみなされるので Data-Dependency が存在せず、結果は未定義となります。同じことは && や || 演算子にも言えます。

Data-Dependency Ordering の問題点

さて、ここまで Data-Dependency Ordering の詳細を説明してきましたが、この仕様にはいくつか問題点があることがわかります。

Data-Dependency Ordering の仕様自体が非常にわかりにくい

これまで述べてきたように、 Data-Dependency Ordering では、何が保証されて何が保証されないのかを判断するのが非常に難しいです。 memory_order_acquire ではプログラム上の前後関係だけを見ていればよかったのですが、 memory_order_consume ではどの式に対して依存関係があるかをいちいちトレースしなければならないので、全く直感的ではありません。

Data-Dependency の扱いはコンパイラにとっても複雑である

先ほどの式 table[r0 + 3 - r0] のように、普通に最適化してしまうと Data-Dependency の関係が切れてしまうようなものも、あえて最適化しないようにコンパイラは注意しなければなりません。このように Data-Dependency の関係をトレースしていくのはコンパイラにとっても大きな負担です。一応、コンパイラに対してどこまで Data-Dependency をトレースすればよいかを指示するために、 std::kill_dependency() 関数や carries_dependency アトリビュートというものが用意されています。しかし、これらも適切に使用しないと効果がありませんし、使い方を誤ると、正しく同期化されない不正なコードとなってしまうこともありえます。

そもそも、 Data-Dependency Ordering を利用することのメリットはかなり小さい

Data-Dependency Ordering が提案された動機は「acquire メモリバリア(memory_order_acquire)のオーバーヘッドを削減する」ことですが、そもそも acquire メモリバリアのオーバーヘッドはたいして大きくありません。特に x86 アーキテクチャにおいては皆無です*4。 Data-Dependency Ordering を利用する意味があるのはPowerPCなどの弱いメモリモデルを採用しているアーキテクチャだけであり、それでもせいぜい数十クロックを削減できる程度です。

ということで、x86やx64アーキテクチャにしか興味が無い人は Data-Dependency Ordering (memory_order_consume) のことは忘れてしまって構いません。 PowerPCなどのアーキテクチャに興味があり、その上で、わずか数十クロックの高速化に対しても多大な努力を惜しまない人だけが、 Data-Dependency Ordering の世界に踏み入ることができるのです。:-)
続き

*1:Linux kernel界隈とか

*2:投機的実行や分岐予測と呼ばれる最適化手法です。

*3:以前のドラフトでは「最適化で消えてしまうような式に対しては Data-Dependency を保証しない」という仕様も提案されていたのですが、「最適化」がどのようなものかを定義するのが複雑になりすぎてしまったため、結局取り下げられました。

*4:前回の最後で示したように、mov命令だけでacquireバリアの効果を持つからです。