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 難しい。

左シフト演算子と未定義動作

指定したビット数だけ下(LSB)からビットが立ったビットマスクを得るために

(1U << bits) - 1

という式を愛用していたのだがはまってしまった。bits == std::numeric_limits::digits つまり全て 1 のマスクにしたい場合、この式は未定義動作をもたらす。14882:2003 5.8/1 には（右シフトも含めて一般に）こうある。

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

そして実際に少なくとも x86 上ではまず期待通り（全て 1）にはならない。x86 アセンブリの左シフト命令はシフト数は 5 ビット分だけ有効である。つまり 32 == 100000(2) は 0 ビットシフトと同じになり結果として上の式は 1 - 1 == 0 となってしまう。

左シフトには他にも未定義動作となる場合があるのだがこの記述にも変遷がある。

14882:1998 と 14882:2003 では以下の通りである。つまり undefined behavior という記述がない。E1 が signed な場合はどうなるのが正しいんだよ、という感じである。恐らく未定義動作を意図していない記述だろう。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]

一方、14882:2011 （多分。自分の参照文書は n3291 なので違う場合もあり得る）では DR854 によりこうなっている。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2 × 2^E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ] one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

int, long int よりも大きな型も想定した記述となっていること、E1 が signed な場合にも記述が明確となり、負の場合には未定義動作となっている。

そして、既に DR1457 が出ており以下のように修正される予定である。

if E1 has a signed type and non-negative value, and E1 × 2^E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

これは、1 << std::numeric_limits::digits のように最大の負数を得るためにビット数-1（=符号ビット分少ないビット数）だけシフト、つまり符号ビットを 1 にするコードを合法にするためである。ただし、これは signed の範囲で表現できない unsigned の値から signed への変換について処理系定義の動作を含む。……しかしだったら signed 全体について全て unsigned にして処理した後 singed に戻すとか規定してしまえばいいじゃないかとも思う。

なお、右シフトについては実質的に記述は変わっておらず(文による表現が式による表現になっただけ)、E1 が負数の場合は処理系定義となっている（以下は n3291 より）。

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

図解 MPL Metafunctions

Boost ライブラリの中でも Boost.MPL は割と食わず嫌いというかなんとなく敬遠している人も多いライブラリのような気がする。MPL = Meta Programming Library ということで「メタプログラミング？黒魔術？」みたいな受け取り方をされているんじゃないかというか、実際には

Boostは一般人が闇に触れずとも闇の力を使える様にするアーティファクトですが、ちょっと使った程度の事では闇に落ちたりしませんから安心してBoostするといいです・ｘ・ （ｯｸｯｸｯｸ ##bot

— 伊藤 兎 (実際にんじん)さん (@USAGI_WRP) 2月 13, 2012

という言にふさわしい、コンパイルタイムメタプログラミングを Sequence、Iterator、Algorithm といったランタイム(実行時：コンパイルタイムの対義語として)の語彙で取り扱えるようにする一般人のためのライブラリである。typename ::type 乱舞になりがちなところと、代入や状態の変更ができず関数型言語的に記述する必要があるところだけ気をつければ難しくない。のだがちょっと自分の中で整理しきれていなかったのが Metafunction 関係である。前回 MPL 用再帰的 equal を書く中で大分整理できたのでまとめてみる。

MPL の Metafunction 関係について包含図を書いてみると以下のようになる。

MPL Metafunctions

Metafunction がランタイム世界での通常の関数にあたる。適用が ::type しないといけないところがちょっと面倒なところだ。Metafunction 以外の Lambda Expression は高階関数にあたるところであり Metafunction Class と Placeholder Expression からなる。Metafunction Class は関数オブジェクト(Functor)にあたると思えばよい。operator() の代わりにメンバテンプレート apply があると考えても良いだろう。さて、ランタイムにおける世界でも毎回毎回関数オブジェクトを書くのは面倒ということで Boost.Lambda や C++11 でのラムダ式がある。これの MPL 版にあたるのが Placeholder Expression だ。良く分からない英語が書いてあるが、placeholder(boost::mpl::_1 等)自身や、テンプレートパラメータのどこかに placeholder ないし Placeholder Expression を含むテンプレートクラスの特殊化(specialization)である。

_1
plus<_, int_<2> >
if_< less<_1, int_<7> >, plus<_1,_2>, _1 >

最後が bind expression である。これは単に bind の特殊化だ。bind はメンバテンプレート apply を持つため必ず Metafunction Class となるが、必ずしも Placeholder Expression とはならない。placeholder なしで bind することも可能だからだ。そのため Placeholder Expression から一部はみ出している。

bind< times<>, int_<2>, int_<2> >

さて、なんとなく Metafunction 族については分かっただろうか。自分もここまでは大体分かっていたのだがそれに作用するもの、具体的に主要なものをあげると apply, lambda, apply_wrap, protect, quote 辺りについて整理ができていなかったので以下に並べてみる。以下の図で青色が引数に取る対象、桃色がある場合はその部分が実際に変換される対象である。

MPL apply

apply は Lambda Expression を引数に取り、その Lambda Expression を適用する(呼び出す)。実際には lambda を適用した後で apply_wrap を呼び出す。では、その lambda と apply_wrap がどうなっているかというと、

MPL lambda

lambda は任意の型を引数に取るが、その内 Placeholder Expression を Metafunction Class に変換する。他はそのままである。

MPL apply_wrap

そして、apply_wrap は Metafunction Class の呼び出しである。実際には ::apply<...> と同等だ。なので、apply は lambda により全て Metafunction Class に変換した後、apply_wrap で呼び出すことになる。

MPL protect

protect は Metafunction Class を受け取るが bind expression しか変換しない。リファレンスマニュアルの例だが以下のように bind 時の placeholder の置き換えを抑止する。protect なしだと入れ子の bind 中の _1, _2 まで置き換えられているが、protect をかけると置き換えされない。

struct f
{
    template< typename T1, typename T2 > struct apply
    {
        typedef T2 type;
    };
};

typedef bind< quote3<if_>,_1,_2,bind<f,_1,_2> > b1;
typedef bind< quote3<if_>,_1,_2,protect< bind<f,_1,_2> > > b2;

typedef apply_wrap2< b1,false_,char >::type r1;
typedef apply_wrap2< b2,false_,char >::type r2;

BOOST_MPL_ASSERT(( is_same<r1,char> ));
BOOST_MPL_ASSERT(( is_same<r2,protect< bind<f,_1,_2> > > ));

MPL quote

最後に上の protect の例でも使われていた quote である。これは Metafunction を Metafunction Class に変換する。引数の数を指定する必要があり、その際デフォルトパラメータの部分も数えなければならないし、変換された Metafunction Class には全引数を渡してやらなくてはならない。bind 等と併用するくらいなら Placeholder Expression + lambda の方が楽かもしれない。

まとめ

どうだろうか。少しでも理解の助けになっただろうか？現実的には以下のルールに従っていれば大体問題ないと思われる。

• 高階関数を受け取る場合は Lambda Expression を受け取ることにする
  • 適用(呼び出し)する場合は apply を使う
  • 高階関数として「そのまま」渡したい場合は lambda をかける(protect をかけた状態になる。実際 lambda は Lambda Expression に対しては protect<bind<...> > になる)
• 高階関数として Metafunction を渡したい場合は quote をかける

Boost.MPL 用再帰的 equal

Boost.MPL の Sequence はその特性上 is_same を使いにくい。例えば

BOOST_MPL_ASSERT((
 boost::is_same<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

は通らない。push_front した結果は list ではなくなっているからだ。このため Boost.MPL には equal というアルゴリズムが用意されている。

BOOST_MPL_ASSERT((
 boost::mpl::equal<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

equal は Sequence の種類を気にせずその「要素」が一致しているかを判別するためこれは通る。通るのだが、equal は最上位の Sequence だけしか考慮してくれないため多次元の Sequence だとうまくいかない。equal の第 3 引数は要素を比較する際の Predicate であるため次元に合わせて equal を渡してやればいいのだが割と面倒である。

// bind base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::bind<
   boost::mpl::quote3<boost::mpl::equal>,
   boost::mpl::_1,
   boost::mpl::_2,
   boost::mpl::protect<
    boost::mpl::bind<
     boost::mpl::quote2<boost::is_same>,
     boost::mpl::_1,
     boost::mpl::_2
    >
   >
  >
 >));
// lambda base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::lambda<
   boost::mpl::equal<
    boost::mpl::_1,
    boost::mpl::_2,
    boost::mpl::lambda<
     boost::is_same<
      boost::mpl::_1,
      boost::mpl::_2
     >
    >::type
   >
  >::type
 >));

やってることは同じである。というか bind base の方は実質 lambda を展開した結果になっている。二次元でこれだとそれ以上だと絶望しそうだ。ということで再帰的な equal を書いてみた。

template<typename Arg1, typename Arg2, typename Pred = boost::is_same<boost::mpl::_1, boost::mpl::_2> >
struct equal_deep
{
 typedef typename boost::mpl::eval_if<
  boost::mpl::and_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
  boost::mpl::equal<Arg1, Arg2, equal_deep<boost::mpl::_1, boost::mpl::_2, typename boost::mpl::lambda<Pred>::type> >,
  boost::mpl::eval_if<
   boost::mpl::or_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
   boost::mpl::false_,
   boost::mpl::apply<Pred, Arg1, Arg2>
  >
 >::type type;
};
BOOST_MPL_ASSERT((
 equal_deep<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
 >));

やっていることはそれほど難しくない。引数が両方 Sequence である時には equal に対して自分自身(equal_deep)を渡して再帰し、両方が Sequence でない時には渡された Predicate を呼び出す。自分が MPL Metafunction 関係をちゃんと把握していなかったので lambda かけるところと apply で迷ったぐらいである。7 行目の eval_if は if_ だと is_same の場合は大丈夫だが Sequence に対して呼び出せない Predicate (equal_to 等) を渡した場合にコンパイルエラーになるため eval_if でなければならない。また、nullary Metafunction を受け付ける部分は typename ::type を付けずに不要なインスタンス化を避けている。

これを書く際にせっかくなので一度 MPL Metafunction 系について整理してみたのだが以下次号。

Susie プラグインと GPL

axpdf--.spi という似非(まともにレンダリングせず画像データだけ抽出する) PDF プラグインを作成、公開しているのですが、公開ページにも書いている通りライセンス的に問題のない PDF Susie プラグインを作成したい、というのが目的の一つでもありました。私は一個人プログラマであって法的なところで確実なことは言えないわけですがちょっと書いてみます。

PDF は仕様が公開されているためオープンソースのレンダラも存在しています。最も有名なのは Ghostscript でしょうか。MuPDF なんてのもあるようですね。しかし、これらのコードを内部で使って Susie プラグインを作成、公開する、という方法には問題があります。これらのコードは GPL でライセンスされているためプラグイン自体も GPL で公開することになります。GPL での派生著作物がどの範囲にあたるのか、は議論の余地があり最終的には法廷で決着が付けられるべきところですが、とりあえず FSF の主張ないし期待するところを正とします。すると動的リンクされるプラグインが GPL でライセンスされている場合、本体側のプログラムも GPL でライセンスされていなければなりません(cf. GPL FAQ Can I apply the GPL when writing a plug-in for a non-free program? フリーではないプログラム向けのプラグインにGPLを適用することはできますか?)。Susie プラグインに対応したソフトで GPL でライセンスされているソフトというのはそう多くないはずです(自分は知りません)。つまり多くの場合でライセンス的に問題のない状態で使用できないことになってしまいます。FAQ のこの項では「フリーではないメインプログラムとのリンクを許可する例外条項」(cf. GPL FAQ What legal issues come up if I use GPL-incompatible libraries with GPL software? フリーではないライブラリを利用するフリーソフトウェアを書いているのですが、GPLを適用した場合どのような法的問題が発生するでしょうか?)の記述があるのですが、この例外条項を付与できるのは著作権者のみです。つまり使用しようとしている「GPL でライセンスされたライブラリ」の著作権者全てに許諾を得る必要があります。これはちょっと望み薄でしょう。

さて、ここまでは以前からそう思っていたことで、ここからはちょっと考えが整理できたかな、と思っていることです。やはり駄目そうです。コメントを参照ください。(2003/01/19) GPL な Susie プラグインを真っ当に使ってもらうためには例外条項がいるとして、では例外条項なしの GPL でライセンスされた Susie プラグインが、GPL でライセンスされていないビューワのもとで使用された場合、その責は誰が負うべきでしょうか。行為としてはビューワの使用者のものなのですが、一方で GPL はソフトウェアの使用に制限を課さないライセンスだという記述もあり、でも GPL の意図上使用者が自由に使えて良いわけはないし、かといって GPL なビューワとの使用なら問題ないんだから GPL な Susie プラグインを公開できないというのも変な話です。これについては GPL による制限が課されているのは使用の前の「動的リンク」であると考えることで GPL 違反をしているのは使用者である、と納得することができました。つまり例外条項なしの GPL でライセンスされた Susie プラグインを公開すること自体は問題なく、GPL でライセンスされていないビューワのもとで使用しないようにするのは使用者の責任であることになります。配布しないなら GPL に違反しないです。(2003/01/19) ただし、プラグイン作者は GPL でライセンスされていることを明示した上で(これは GPL で要求されています)、個人的には GPL でライセンスされていないビューワのもとで動作させてはならないとも明示的に警告するべきではないかとも思います、道義的に。より個人的には、例外条項を付けるか、付けられないならそもそも公開するべきではないとも思いますが。