A bit inside of Transactional Language Constructs for C++ - part.1 Atomic transaction

Boost.勉強会 #10 にて @yohhoy さんが Transactional Language Constructs for C++ (C++ における Transactional Memory 拡張)について発表 されました。丁度自分も提案文書を読んでいるところであり Transactional Memory (以下 TM)というか並列プログラミング全般について知識がないので勉強会駆動の発表ネタになるかなと思っていたところだったので非常にタイムリーでした。発表内容としては現在提案されている TM 拡張の syntax と semantics についての説明で、実装については対象外だったわけですが(もともと提案文書には実装については含まれていない)、その発表の中で

• (Atomic Transaction で、他の transaction だけでなく)他のスレッドに途中状態を見せないってどう実現するのか分からない

というコメントがありました(多分)。その時は、ピンと来なかったのですが色々調べたりするうちにその感覚が分かってきました。その心は

• ゼロオーバーヘッドか？(TM 有効にしても実際に TM を使用しなければオーバーヘッドはないか？)

という質問にも通じます。私は TM 拡張は基本的に transaction 内部のコードだけ変更すればいいと考えていたので実行時にはほぼゼロオーバーヘッドだと思っていたのですが、(transaction 外の)他のスレッドにも途中状態を見せないということは transaction 外のコードに対しても何かガードなりを設ける必要があるのではないか？という懸念があった訳です。

が、なんというか「確かに嘘は書いてないんだけどさぁ」という解釈が可能であることに気付きましたので、本稿ではそのことについて書いてみます。

さて、提案文書では Atomic transaction について以下のように書かれています。

In a data-race-free program, an atomic transaction appears to execute atomically; that is, the compound statement appears to execute as a single indivisible operation whose operations do not interleave with the operations of other threads.

データ競合がないプログラムでは、atomic transaction はアトミックに実行される。(atomic transaction として指定された)複文は他のスレッドの操作とインターリーブされない単一の分割不可能な操作として実行される。

さて、ここでどうしても後半に意識がいってしまうわけですが、この文章で最も重要なのは最初の部分 "In a data-race-free program" です(appear であることも多分重要)。

data-race-free とは何かについては TM 提案の最初の方にも簡単に触れられています。C++11 では 1 スレッド内の実行順序について "sequenced before" という関係で順序が定められているものがあります。またスレッド間の実行順序について "synchronized with" という関係で順序が定められているものがあります。これらをもとに "happens before" という関係が定められています(厳密にはもうちょっと複雑)。

• A is sequenced before B → A happens before B
• A synchronizes with B → A happens before B
• A happens before B ∧ B happens before C → A happens before C

そして、あるメモリ領域に対する書き込み操作と、別の読み込み操作あるいは書き込み操作が同じメモリ領域に対して行われている時、これらを conflict と称します。以上を元に data race (データ競合) は、次のように規定されています。

The execution of a program contains a data race if it contains two conflicting 2 operations in different threads, at least one of which is not an atomic operation, and neither happens before the other.

異なるスレッドの 2 つの操作が conflict しており、"happens before" の関係になく、かつ、少なくとも一方は atomic ではない場合、data race が発生している。

要するに、「同一メモリ領域に対する書き込みと、読み込みないし書き込み」(=conflict)について順番が定められていないケースを data-race と呼んでいる訳です。

さて、transaction 間については、ある transaction の終了と別の transaction の開始には "synchronized with" の関係があるとされ、実行がインターリーブしません。従って、transaction 間では data-race は発生しません。では、transaction と transaction 外ではどうなるでしょうか？

atomic transaction はロックや atomic など他の同期機構を含むことができません。このため、transaction 内のコードと transaction 外のコードについて "synchronized with" 関係が発生しません。この状況下で data-race-free、つまり順序不定な conflict が存在しないためには、

1. 同一スレッド内で sequenced before 関係にあるか、
2. そもそも conflict が存在しないか、
3. 別の transaction 内に存在しているか、

のいずれかである必要があります。結果として別スレッドの transaction 外のコードは transaction の途中状態を見ることがありません。この場合、2 しか有り得ず、そもそも transaction が変更するメモリ領域に対するアクセス、conflict が存在しない訳ですから。

つまり、atomic transaction において他のスレッドが transaction の途中状態を見ないというのは atomic transaction によって保証されているというよりは、その前提、data-race-free なプログラムである、というところに依るところが大きいと言えます。data-race-free であることはプログラマが保証してやらねばなりません。一番簡単なのは conflict があるところを transaction で囲むことでしょう。この場合、atomic transaction である必要はありません(transaction 間であれば relaxed transaction でも順序が規定されるので)。

本記事では A bit inside of Transactional Language Constructs for C++ part.1 として TM 提案 での atomic transaction の記述の解釈について書いてみました。心づもりとしては part.2 では TM 提案の対とも言える文書、Intel TM ABI を元にコンパイラがどのように C++ TM を実現しようとするかについての概要、part.3 では Intel TM ABI を実装しているライブラリ RSTM の実装を簡単に覗いてみたいと思っています。

小ネタ： BOOST_CHECK_CLOSE と BOOST_CHECK_CLOSE_FRACTION

Boost.Test は Boost にあるユニットテストフレームワークである。ユニットテストの項目記述用に色々とマクロが定義されているのだが、その中に浮動小数点数比較用のものがある。なぜ浮動小数点数用が別にあるかというと誤差の問題が存在するからで許容範囲を与えるようになっている。

BOOST_CHECK_CLOSE         ( 1.00001e-10, 1.00000e-10, 0.00001 ); // FAIL
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK

ではこの _FRACTION の有無の違いは何かということでドキュメントを見ると、見ると……。違いが分からなかったという貴方は正しい。なぜならドキュメントが間違っているからだ。間違っていることは #3964 で指摘されており trunk では修正されているのだが release ブランチにマージされていないようだ。ということで、チケットを切ってみた。状況にもよるがチケット切ると割とすぐに対応してもらえたりするので、見つけた問題点はばんばんチケット切ると良いと思う（もちろん重複確認ぐらいはした上で）。

話を戻すと、BOOST_CHECK_CLOSE はパーセンテージ指定、BOOST_CHECK_CLOSE_FRACTION は比率指定、つまり

BOOST_CHECK_CLOSE         ( 1.00001e-10, 1.00000e-10, 0.001 );   // OK
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK

が同じ挙動になるということである。

ちなみにパーセンテージ、比率ということからも分かる通り、許容範囲は相対指定である。マクロを使う限りにおいては引数それぞれからの相対で両方を満たしていなければならない（これに関するドキュメントもリリースでは古いので trunk から)。

|u − v| / |u| ≤ ε ∧ |u − v| / |v| ≤ ε

つまり以下はいずれも FAIL する。

BOOST_CHECK_CLOSE         ( 0.99999e-10, 1.00000e-10, 0.001 );   // FAIL
BOOST_CHECK_CLOSE_FRACTION( 0.99999e-10, 1.00000e-10, 0.00001 ); // FAIL

片方からだけでも構わないという場合は第 4 引数を FPC_WEAK として直接 check_is_close を使えば良い。

emplace と aggregate

C++11 で rvalue reference による perfect forwarding が実現されたため、STL コンテナに emplace 系の関数が追加されている。insert() や push_back() は value_type 型の値自体を与える必要があるが、emplace 系には生成に必要な引数(コンストラクタの引数等)を渡してやれば良い。

 std::vector<std::pair<int, int>> v1;
 std::pair<int, int> p{ 0, 0 };
 v1.push_back(p);
 v1.push_back({ 0, 0 });
 v1.emplace_back(0, 0);

これで無駄な temporary 作成が無くなり万々歳、なのだが。非常によく似た以下の例は実はコンパイルできない。

 struct point { int x, y; };
 std::vector<point> v2;
 point pt{ 0, 0 };
 v2.push_back(pt);
 v2.push_back({ 0, 0 }); // (g++ 4.5 compilation error
                        // by ambiguous between const value_type & and value_type &&)
 v2.emplace_back(0, 0);  // g++ 4.5-4.8 compilation error
                        // new initializer expression list treated as compound expression

g++ 4.5 特有のエラーについては置いとくとして、下側なんでやねんというのは StackOverflow の質問 ならびに引用されている DR を見てもらえれば良いのだが、問題は emplace 系で呼び出される std::allocator_traits::construct(m, p, args) が最終的に ::new((void *)p) U(std::forward(args)...) となり、list-initialization ではなく direct-initialization になってしまう、という点にある。単純に list-initialization にする、というのは例えば下記のようなコードの挙動を変えてしまうということで、

 std::vector<std::vector<int>> v;
 v.emplace_back(3, 4); // v[0] == {4, 4, 4}, not {3, 4} as in list-initialization

is_constructible<U, Args...> が true かどうか(direct-initialization が有効かどうか)によって、direct-initialization か list-initialization かを呼び分ける方向での修正が提案されている。

こんな単純そうな例ですら落とし穴があるとは、ほんと C++11 難しい。