元文書：N3710: Specifying the absence of "out of thin air" results (LWG2265), Hans-J. Boehm氏, 2013/08/29
訳出メモ：
- 自分自身の理解のために日本語訳を行ったC++メモリモデルから "out of thin air" を禁止する提案文書。（前半）
- 訳文中では "out of thin air" は英語表記のままとする。"out of thin air" については江添さんの2013-09 pre-Chicago mailingの簡易レビュー やid:yohhoy:20120517も参照のこと。
- C++11実行モデルにおける "carries a dependency" は必ず英語表記を併記する。
"out of thin air" 結果の不在を規定する (LWG2265)
C++11メモリモデルは、共有された通常オブジェクトおよびatomicオブジェクトのセマンティクスを規定します。この仕様には、私たちが前々から曖昧であると認識している、小さな問題が存在しています。1.10節にある弱い順序付けatomic操作の仕様は、atomicなload操作が競合するstore結果を観測するまたは観測しないのいずれも許容します。このことは、明示的に非常に弱いメモリ順序付けを用いる場合に、“因果循環(causal cycles)”という全く直観に反する結果をもたらします。xとyをゼロ初期化されたatomic変数、riをローカル変数として、次の例を考えます：
Thread 1: r1 = x.load(memory_order_relaxed); y.store(r1, memory_order_relaxed); Thread 2: r2 = y.load(memory_order_relaxed); x.store(r2, memory_order_relaxed);
Thread 1はxからyへのコピーを、Thread 2はyからxへのコピーを行っています。仕様書1.10節はそれぞれのload操作が、ゼロ代入による初期化もしくは他スレッド上でのstore操作のいずれかを観測することを許容します。
良く知られているように、この例ではr1とr2の両方が最終的に値42、もしくは他の"out of thin air"値になることを許容します*1。これはそれぞれのload操作が、他方のスレッド上でのstore結果を観測する場合に生じます。実際には、コンパイラが両atomic変数ともに値42を持つであろうと推測して、その結果を投機的にstoreし、先のload操作に関する推測が正しく再試行は不要と確認する実行(execution)をモデル化したものです。
実際の所そのような結果を生成する処理系は知られていません。しかしながら、コンパイラやハードウェアでの正当な最適化を阻害せずに、これらを禁止する仕様を書くのは極めて困難です。複雑さの最初の兆候として、先の例の下記バリエーションでは理想的にはx = y = 42を許容すべきであり、またこのような結果を生成する処理系は実在するのです：
Thread 1: r1 = x.load(memory_order_relaxed); y.store(r1, memory_order_relaxed); Thread 2: r2 = y.load(memory_order_relaxed); x.store(42, memory_order_relaxed);
このケースでは、特に問題なく各スレッドload操作が他方スレッド上のstore結果を実際に観測できます。スレッド2上の二つの操作は独立かつ順序付けされないため、コンパイラまたはハードウェアのいずれも操作入れ替えを行えます。
この論点は本質的に、10年近くJava言語仕様の未解決問題として存在しています。C++での主な利点は、この問題が同期しないatomic操作、すなわちmemory_order_relaxedや一部のmemory_order_consume利用（またはある変数に対するread／write操作よりも弱い順序付けのread-modify-write操作）に限定されることです。こういった操作は稀にしか使わないと期待されます。
現行規格では29.3節 段落9-11でこの論点を扱いますが、万人にとって盤石といえる記述にはなっていません。（2007年頃や現行記述に至るまでの議論はここで見つかります。）残念なことに、私たちはこの論点の影響度と、現行記述に関する問題との両方を過小評価していました。その間、多くの人々、Peter Sewell、Mark Batty、直近ではBrian Demskyが現行記述にまつわる問題を指摘しています。
この提案では、私たちの本来の意図に比べると無視できないコストだが、現行文書の文面と比べた場合はそうでないように、仕様の訂正を試みます。この変更によって事実上memory_order_relaxedがより強いセマンティクスを持ち、ARMや現行NvidiaまたおそらくPOWER等のいくつかのアーキテクチャ上ではmemory_order_relaxedが追加のオーバーヘッドを伴うでしょう。きちんと定義可能なセマンティクスを与えるため、提案では両例でx = y = 42という結果を禁止し、前掲の2つの例を事実上合成します。
memory_order_relaxedに関するこういった制限には先例がない訳でもありません；Itaniumにおける現行のキャッシュ・コヒーレンス要件は、通常のload操作とstore操作がmemory_order_relaxedにはすでに十分でないと意味しています*2。（Jaroslav Sevcik and Peter Sewell's table of C++11 atomic mappings参照）たしかに、競合のない通常アクセス向けに設計されたload命令やstore命令が、atomicアクセスにもそのまま適用できると信じる先験的理由は存在しません。
現在の要件(requirement)から奨励規定(normative encouragement)へとあえて意味論要求を弱めることで、これらのアーキテクチャにおける要求性能への影響度軽減を試みています*3。これはハードウェアベンダに対して、改良されたセマンティクスのより良いサポートに必要な期間を与えるべきとの意図から来ています。さらに、現行要件および提案する要件のいずれもが強すぎる場合に、非競合コンテキストでのmemory_order_relaxedアクセスの代替手段提供も提案します。
ここでの追加オーバーヘッドはC++11標準の意図(intent)と比べての話であり、実際の仕様に対してではないことは繰り返しておきます。現行記述の通り、実際の仕様ではmemory_order_relaxedをmemory_order_seq_cstに近いものとして実装するよう意図せず要求しており、それゆえLWG2265が指摘する通り、技術的にはより大きなぺナルティを課しています。
本提案は、ペーパー先頭で挙げた参加者らによるメールでの長期にわたる議論に助けられています。これらの非常に有用な入力情報は、本提案の改善につながっています。グループ内で明確な合意に達しなかったことや、より良い合意が得られる代替提案に至らなかったことは残念です。必ずしも全てのコントリビュータが本提案を支持するものではありません。ただ現状維持の方針が支持されることは無いと信じており、それゆえ私は本提案を推し進めていきます。Mark BattyとPeter Sewellが、本トピックについての代替提案を含む追加の最新ペーパー提出を現在検討中です。
out-of-thin-air結果の禁止が重要な理由
Java言語の文脈では、信頼されないコードが特定情報へのアクセス手段を獲得不可能であると示すために、out-of-thin-air結果の禁止が必要とされます。仮に信頼されないコードが何らかの手段で処理系に影響を与えて、ユーザの機密パスワードを"out of thin air"に作り出せるとしたら、その結果は酷いことになるでしょう。C++では信頼される実行モジュールの一部としての信頼されないコード実行のサポートは目指しておらず、このような論点はそれほど問題となりません。
しかしながら、Brian Demskyらが指摘する通り、out-of-thin-air結果の許容は、通常のC++コードを形式的に、もしくは非形式的にさえ論証することも困難にします。
この問題を確認するため、atomic変数xとyに0または1を代入しておき、ときたま弱い順序付け操作を用いて一方から他方にコピーするだけのプログラムPを考えます。ライブラリ仕様として第一引数に0または1を要求する関数f()があり、仕様上はf()が正しく呼ばれる限りグローバル変数も第二引数の参照変数いずれも変更しないと仮定します。このプログラムがf(x.load(memory_order_relaxed), y)を呼び出すケースを考えてみましょう。
fの第一引数が常に0もしくは1になると、十分に証明可能と期待することでしょう。しかし、out-of-thin-airを許容する場合はその保証が無くなります。仮にスレッド1がmemory_order_relaxed操作を用いてyからxへコピーし、一方でスレッド2がf(x.load(memory_order_relaxed), y)を呼び出す場合にも、スレッド1がy = 42を観測して、xへ42をコピーし、スレッド2がf()へ42を渡すようなケース、つまり、ライブラリ仕様から外れた操作につながる、yに42がstoreされ、スレッド1上での42のload処理が正当化されるようなケースを、依然として排除する必要があります。
前提条件が満たされない場合の振る舞いが未知なライブラリ関数f()といった実際の状況下では、明らかにこの手の議論があってはなりません。この“あってはならない”実行パスに関する論拠の必要性こそが、いかなるout-of-thin-air結果の許容も支持できない理由なのです。
out-of-thin-air結果の禁止が困難な理由
これまでに示した通り、複数の値の間に循環する“依存チェーン(dependency chains)”が存在するときにout-of-thin-air値が生じます。従って、もし“依存チェーン”を定義できれば、out-of-thin-air値の定義を与え、それらを禁止することで問題解決するはずです。
この考え方はハードウェア・メモリモデルで取られる本質的なアプローチです。そこでは依存先のload操作より前に他スレッドに対して可視とするstore操作を禁止しており、ハードウェア・レベルでのout-of-thin-air値を抑止するには十分なのです。ハードウェア・レベルでは、他の値に“依存する”値という概念は比較的素直に定義されます；アプローチは1.10節[intro.multithread]における“依存性伝搬(carries a dependency)”関係の定義でとった方針と似ています。本質的に、aがbを計算する操作の引数であるときは、bはaに依存しており、またもしbがそのような操作の連鎖によって計算される場合も同様です。“依存性伝搬(carries a dependency)”の定式化とは異なり、大抵のハードウェア・モデルではaに依存したbの計算に分岐が先行する場合にも、bはaに依存するとみなします。（Itaniumは例外的ですが、ここでは問題としません。）
ハードウェア・メモリは、他スレッド対して順序通り(in order)に可視とする依存操作を要求することで、暗黙的にout-of-thin-air値の禁止をモデル化します。ハードウェアでの依存性の概念は、他方に影響を与える値の全ケースをカバーするため、この問題を解決するには十分なのです。
現在の“依存性伝搬(carries a dependency)”の定義は、ある値が他に影響を与える手段の一部しかカバーしないため、似てはいるものの十分ではありません。例えば、if文の条件中での式評価はその値に影響する場合であっても、thenやelse文中での式評価へと依存性を伝搬しません。もしaからbへ依存性が伝搬(a carries a dependency to b)される場合に順序付けを強制すると仮定しても、例えばyへの代入で定数値を代入するが、該当コードがf()への第一引数が2以上のときの条件分岐に位置するなど、引数評価x.load(...)からf()内部でのyへのstore操作へと依存性を伝搬(carry a dependency)しないため、前節での問題を排除できません。*4
この問題をハードウェアと同様に扱うには、“依存性伝搬(carries a dependency)”を、制御の依存性(control dependencies)も含んだ、ある値が他に影響を及ぼすあらゆる手段を包含するよう一般化しなければならず、これにより全ての依存性に順序付けの強制を要求することが考えられます。コンパイラは最適化の一種として必ずこういった依存性を除去するため、この方針は現実的ではないように思えます。下記コード片を考えます：
if (x) { a[i++] = 1; } else { a[i++] = 2; }
合理的なコンパイラは&(a[i++])の計算を条件文の外へ移動するでしょうし、それによりiからxへの依存性は取り除かれます。このような依存性はatomic変数にアクセスしない別個コンパイルされた関数を通過するため、プログラムのあらゆる箇所でそのような最適化を禁止する必要があり、後述する私たちの提案よりも非常に高価と見込まれるコストを払うことになるでしょう。またatomic変数に対する正しいセマンティクスを得るために、atomic変数にアクセスしない既存コードの再コンパイルも必要となってしまうでしょう。
コンパイル処理がこういった構文的依存性を除去できるという事実は、ハードウェアからは隠蔽されるため、この問題をプログラミング言語レベルとハードウェア・レベルで本質的に異なるものにします。
このような依存性の除去が、実際にはout-of-thin-air値を導入しないことは留意してください。それを禁止する技法が単にこの仕様と合致しないだけなのです。if構文でのiからxへの依存性の削除は、xの変更結果としてiの値が変更されることは無いという事実を反映したに過ぎません。そのためこの事実を反映する、依存性のさらに“動的”な概念定義を試みることになります。
ただ、それは原理的に定義不可能な概念であり、どのようなハードウェア仕様でも試みられたことがないものに思えます。困難さを説明するため、次の関数定義を考えます：
int f(int x, int y) { return x - y; }
計算結果は入力xに“動的に依存する”でしょうか？仮にf()が両引数が等しい状況でのみ呼び出され、f()がインライン化などで決定的にコンパイルされるなら、依存性は無いといえます。常にそのような状況と限定されない場合であっても、コンパイラはf()の事実上のコピーを作りだし、通常は再びインライン化を行って、両引数が等しい状況での関数呼び出しを処理することでしょう。Mark BattyとPeter Sewellは、単なるシングルスレッド実行を考えた場合でさえ、このような概念が原理的に定義不可能であると指摘しています。従って、少なくとも、与えらえた入力でのプログラムの振る舞いを理解するために、他の仮想的な実行を理解する必要に再びせまられます。その場合も、そのような定義が関数の複製や特殊化を正しく扱えるかは明確ではありません。
非形式的には、“依存性”の概念を正しく定義することは“out-of-thin-air”を定義することと正に等価と考えられ、いずれもが実現不可能に思えます。従って私たちはこの問題を回避する方針で、長い期間を必要とする、相当に抜本的な提案を行っていくつもりです。
→ id:yohhoy:20140415 へ続く
*1:訳注：ここでの値42は具体的な意味を持たない。https://www.google.com/search?q=the+answer+to+life+the+universe+and+everything
*2:訳注：C++ memory_order_relaxedに対応するItanium load命令(ld.acq)とstore命令(st.rel)はmemory_order_relaxedよりも強い順序付けセマンティクス（それぞれmemory_order_acquireとmemory_order_releaseに対応）をもつ一方で、通常のItanium load命令(ld)とstore命令(st)ではmemory_order_relaxedよりも遥かに弱いセマンティクスとなってしまうため、同アーキテクチャ上ではmemory_order_relaxedセマンティクスを直接実現する手段が存在しない。
*3:訳注：言語仕様として強制力をもつrequirementとせず、少し弱い要請となる"normative encouragement"として定義する。
*4:訳注：関数定義 f(int c, atomic<int>& v){ if(c<2){...}else{ v.store(42, memory_order_relaxed); } } を考えたとき、呼出元 f(x.load(memory_order_relaxed), y) では「xからyへの依存性伝搬」を知りえないため、仮定を置いた「依存性伝搬による順序付け」がやはり機能しないという主張に思える。1センテンス長すぎ…
