読者です 読者をやめる 読者になる 読者になる

今ココなう! iPhone用Webアプリのソースコードを公開

私の作成した今ココなう!のiPhone用Webアプリについて、そのソースコードgithubにて公開しました。
このWebアプリは、iPhoneだけでなくAndroid2.1以降やFireFox3.5以降、Chrome5やSafari5など、最近のHTML5対応ブラウザでも利用することができます。アプリが利用している技術要素を以下に列挙してみたので、興味のある方の参考になれば幸いです。

マルチコア時代のLock-free入門

本日、並カンにてLock-freeアルゴリズムについて発表しました。発表資料は以下になります。
なお、今回の発表で割愛したメモリバリアの詳細については、以下の発表資料を参照ください。

また、Hazard pointerやタグ付きポインタを使用したサンプルコードを以下に置いています。こちらも参考にどうぞ。

C++0x時代の Double-Checked Locking

今回は "Double-Checked Locking" (以下DCL)というマルチスレッドプログラム向けのイディオムを例にして、C++0xの(低レイヤ向け)マルチスレッド機能の利用方法を紹介してみます。
DCLとは、「ロック→条件判定」というロジックを「条件判定→ロック→(再度)条件判定」と書き換えるイディオムで、主に遅延初期化などの処理においてロックのオーバーヘッドを減らすために用いられます。DCLはシンプルかつ効果の高いイディオムだったので、一時期もてはやされました。ところが、DCLはコンパイラやCPUによるリオーダーの影響により正しく動作しない場合があることがわかったため(参考1参考2)、今ではアンチパターンと呼ばれることすらある始末です。
しかし、DCLの問題点は、メモリモデルに関する知識があまり知られていなかったことと、プログラミング言語の仕様でメモリモデルが正しく定義されていなかったことにあり、DCLというイディオムそのものは正当なものです。そして、atomic変数とメモリバリアがきちんと定義されている C++0x では、DCLを正しく実装することが可能になったのです。
ではさっそく、「正しい」DCLの実装例を挙げてみましょう。

std::atomic p(nullptr);
std::mutex m;

Hoge& getInstance() {
  Hoge* tmp = p;
  if (tmp == nullptr) {
    std::lock_guard lk(m);
    tmp = p;
    if (tmp == nullptr) {
      tmp = new Hoge();
      p = tmp;
    }
  }
  return *tmp;
}

std::mutex や std::lock_guard は C++0x で追加されたロックを行うためのAPIです。上のコードだと「"std::lock_guard lk(m);" の行で排他ロックを行い、変数lkのスコープの終わり(つまりreturn文の前の行)でアンロックする」という意味になります*1。DCLの特徴である「条件判定→ロック→(再度)条件判定」という実装になっていることがわかるでしょうか。
このDCL実装の肝は、変数 p がatomic型として宣言されている点です。 C++0x のatomic型は、これまで繰り返し説明してきたように、操作がアトミック(不可分)に行われるだけでなく、メモリアクセスの順序付けを保証する効果(メモリバリア)も持っています。変数 p への読み書きの際にメモリバリア効果が発揮されるため、最初に挙げた「DCLの問題点」を解消できているのです。

release/acquireメモリバリアによるDCL

ちなみに、こちらの記事で説明したように、atomic型でのデフォルトのメモリバリアは memory_order_seq_cst という「最も強力だが遅い」ものになっています。しかし、DCLを実装するにはもっと弱いメモリバリア指定でも十分です。明示的に release や acquire のメモリバリア種別を指定することで、先のDCL実装を「より高速に」動作するように書きかえてみると以下のようになります。

std::atomic p(nullptr);
std::mutex m;

Hoge& getInstance() {
  Hoge* tmp = p.load(std::memory_order_acquire);
  if (tmp == nullptr) {
    std::lock_guard lk(m);
    tmp = p.load(std::memory_order_relaxed);
    if (tmp == nullptr) {
      tmp = new Hoge();
      p.store(tmp, std::memory_order_release);
    }
  }
  return *tmp;
}

太字の部分が、明示的に指定したメモリバリア種別になります。最後の p.store(tmp, std::memory_order_release) と最初の p.load(std::memory_order_acquire) が対になることで、newされたHogeインスタンスへのアクセスが「正しく同期化」されるのです。
一方、真ん中のloadには「メモリバリアなし」を意味する memory_order_relaxed が指定されています。その理由は、std::mutex による排他制御が暗黙的なメモリバリアとして働いているために*2、このload自体にはメモリバリアが不要となるからです。

Data-Dependency OrderingによるDCL

さらに、前回説明したData-Dependency Orderingを利用して、もっと高速なDCLを実装することも可能です。

std::atomic p(nullptr);
std::mutex m;

[[carries_dependency]] Hoge& getInstance() {
  Hoge* tmp = p.load(std::memory_order_consume);
  if (tmp == nullptr) {
    std::lock_guard lk(m);
    tmp = p.load(std::memory_order_relaxed);
    if (tmp == nullptr) {
      tmp = new Hoge();
      p.store(tmp, std::memory_order_release);
    }
  }
  return *tmp;
}

[[carries_dependency]] というヘンテコな句が増えていますが、これについてはこちらの文書を参照してください。

std::call_onceによる遅延初期化

いろいろDCLの実装方法について述べてきたのですが、単に「最初の一回だけ処理を行いたい」ということであれば、C++0xには std::call_once という関数が用意されています。利用例は以下のようになります。

Hoge* p = nullptr;
std::once_flag flag;

void init() {
  p = new Hoge();
}

Hoge& getInstance() {
  std::call_once(flag, init);
  return *p;
}

この std::call_once は、最初に呼び出されたときのみ init() を実行し、2回目以降は何も行いません。また、複数のスレッドが同時に std::call_once を呼び出した場合でも、必ず1つのスレッドのみが init() を実行し、他のスレッドは init() の実行が完了するまで待機させられます。
std::call_once は、DCLをわざわざコーディングしなくて済むためのユーティリティ関数と考えてよいでしょう。実際、std::call_once と同等のものは std::atomic と std::mutex を用いたDCLによって実装することが可能です。

ブロックスコープのstatic変数による遅延初期化

とまあ、いろいろ例を挙げてきたのですが、実はもっと単純な記述でインスタンスの遅延初期化を実現することが可能です。それは以下のコードです。

Hoge& getInstance() {
  static Hoge hoge;
  return hoge;
}

このようにブロックスコープでstatic変数を宣言すると、最初の getInstance() の呼び出しのときにHogeインスタンスが初期化されます。そしてC++0xでは、マルチスレッド環境においてもこの仕組みが正しく動作することが保証されます。つまり、最初に getInstance() を呼び出したスレッドだけがHogeのコンストラクタを呼び出し、他のスレッドはコンストラクタの実行が完了するまで待機させられるのです。*3
ということで、複雑なDCLのコードをわざわざ書かなくても、C++0xでは遅延初期化のコードをスマートに記述することが可能です。つまり、「C++0x時代では(遅延初期化のための) Double-Checked Locking は必要ない」というのが、この記事の結論なのです。:-)

*1:これらのAPIについてはこちらの記事が参考になります。

*2:こちらの記事を参照。

*3:さらに、このstatic変数を用いたバージョンでは、プログラム終了時にちゃんとデストラクタが呼びだされる点が他の例よりも優れています。

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などの弱いメモリモデルを採用しているアーキテクチャだけであり、それでもせいぜい数十クロックを削減できる程度です。

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

*1:Linux kernel界隈とか

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

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

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

次期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:この実装方針は、IntelAMDのマニュアルの記述からも導き出すことができます。

*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とかについて話をしてきました。
ちょっと遅くなりましたが、そのときの講演資料を一つにまとめたので、ここで公開しておきます。あと、補足記事も追加していってます。