元文書：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"は英語表記のままとする。
- C++11実行モデルにおける"happens-before", "synchronizes-with", "sequenced-before", "carries-a-dependency-to"、および"write-seen-by"は英語表記のまま（または英語表記を併記）とする。
- 注意：C++14言語仕様では、本N3710よりもさらに簡易的な文面としたN3786が採択される。（ただし、目指している方向性は同じ）
前半（→id:yohhoy:20140411）の続き。
直近の問題
Brian DemskyらはLWG2265にて、“out-of-thin-air”値の禁止を目的とした現行の文面では、いくつかの重要な弱い順序付けアーキテクチャ上での実装が事実上不可能と指摘しています。現行文面は本質的にmemory_order_seq_cstと非常に近い方法でmemory_order_relaxedが実装されることを要求します。このことは、初期の“out-of-thin-air”問題のごく一部を扱う取り組みから生まれた、予期しない状況です。
LWG2265中の例示は解析困難に思えます。ただし、POWERまたはARM上で普通にコンパイルされた、Brian Demskyによる例示の（少々短縮した）下記変形コードでは、29.3節[atomics.order] 段落9により間違って禁止されるにもかかわらず、32行目でstoreする値を生み出す“有限のプログラム評価列(finite sequence of program evaluations)”を要求するような、T1およびT2のstore結果がT3またはT4では（意図通りに）異なる順序で観測され得ることには賛同できると思います。*1
1 atomic_int x[2]; 2 atomic_int z; 3 int c1, c2; 4 int d1, d2; 5 6 void T1 () { 7 x[0].store(1, relaxed); 8 } 9 10 void T2 () { 11 x[1].store(1, relaxed); 12 } 13 14 void T3 () { 15 c1= x[0].load(relaxed, consume or acquire); 16 c2= x[c1].load(relaxed); 17 } 18 19 void T4 () { 20 d1= x[1].load(relaxed, consume or acquire); 21 d2= x[d1^1].load(relaxed); 22 } 23 24 int user_main (int argc , char ** argv ) { 25 x[0] = 0; 26 x[1] = 0; 27 28 { T1 () || T2 () || T3 () || T4 () } // 全てを並列実行 29 30 /* ここで値200の書き込みは起き得るか？（つまりc1=d1=1, c2=d2=0） */ 31 /* そうであるなら、その結果を正当化する評価列はどのようなものか？ */ 32 z.store((c1+d1)*100 + c2+d2); 33 }
この結果を生じさせるには、要求される評価列ではT3とT4での最初のload操作よりも前にT1とT2での代入を行ない、T3とT4それぞれのload順は維持されなければいけません。もしT4の最初のload操作がT3のよりも後ならば、T4の最後のload操作は値1を観測せねばならず、またもしT3のload操作が最後ならば同様となります。よって、現行テキストの妥当な解釈に従うならば、この評価列は存在が許されないのです。*2
一方で、POWERやARM上でこの計算結果を禁止することは、T3とT4上で行われる2つのload操作の間に重量級のフェンス操作を要求し、load操作をほぼ逐次一貫(sequentially consistent)的に扱うよう強制することであり、memory_order_relaxedの意義を完全につぶしてしまいます。さらに、より現実的な例であっても、一般的なコンパイラがmemory_order_relaxedをその意図通りコンパイルするのに十分なコンテキストをいつも俯瞰できるとは考えられません。
先のセクション（訳注：前半参照）で指摘した通り、この問題を修正する方法は知られておらず、痛みを伴わない解決策を見落としているとはほとんど思えません。
長期的な解決提案
後続memory_order_relaxed store操作からのmemory_order_relaxed（またはmemory_order_consume）load操作を行うような順序入れ替えを事実上禁止し、また非常に弱い順序付けread-modify-write atomic操作へも同様な制限を加える、相当に抜本的な文面変更を提案します。これは、atomic変数での“〜で観測される書込(write seen by)”（逆の表現では“〜から読み込む(reads-from)”）関係を、“先行発生(happens-before)”関係と組み合せたとき、循環を形づくることができない、より形式的には2つの二項関係の和集合による推移閉包(transitive closure)が非反射的(irreflexive)である、という制限によって容易に表現されます。これはどんな因果循環(causal cycle)も明確に禁止します；全ての依存性は明らかにwrite-seen-by関係かhappens-before関係のどちらかに（またはデータ競合(data race)として）反映されており、もはや循環する依存性の列をたどることはありません。しかし残念ながら、片方のスレッド上で定数値をstoreする、冒頭で示した2番目の例示（訳注：前半のxへ42を代入する例）も禁止してしまいます。load操作と後続store操作のあいだで単純な依存性の順序を強制する代わりに、ハードウェアが行っているように、全ての緩和(relaxed)されたstore操作は先行load操作へ依存するかのように扱っており、これで依存性定義の問題を回避しています。
詳細は個別のマシン・メモリモデルに依存しますが、atomic変数へのload-to-store操作並び替えを禁止することで一般に上記制限を強制できます。これを理解するには、write-seen-by関係とhappens-before関係の列で構成されるパスを考えます。各happens-before関係の辺(edge)はsynchronizes-with関係およびsequenced-before関係の辺へ分解されます。（今はmemory_order_consumeを無視します。）従って循環は、write-seen-by関係またはsynchronizes-with関係の辺で接続されたスレッド内セグメントから構成されます。各スレッド内セグメントはload操作もしくはacquire操作で始まり、release操作もしくはstore操作で終わらなければなりません。いずれの場合も、順序は維持されます。よって全てのスレッド内セグメントは開始した後に完了せねばならず、同期する辺（訳注：write-seen-byまたはsynchronizes-with）に対しても同じことがいえます。パス上で前のアクションに戻ることは出来ず、循環が生じることはあり得ません。
（パスがmemory_order_consumeを含む場合も、memory_order_consumeの追加属性を無視しmemory_order_relaxedのように扱うことで、やはり同様のパスが存在すると言えます。memory_order_consumeにより生じるhappens-before関係は、carries-a-dependency-to関係にとって代わるsequenced-before関係と、memory_order_release store操作とmemory_order_consume load操作の間のwrite-seen-by関係により置き換えが可能です。このように、同じ議論の適用を継続できます。）
性能への影響
提案では依存性の強制を要求しないため、弱い順序付けatomic操作を用いるコードのみが影響を受けます。少なくともmemory_order_acquire load操作、memory_order_release store操作およびmemory_order_acq_rel read-modify-write操作を一貫的に用いるコードでは、すでにこの追加保証を満たしています。
多くのアーキテクチャ上では、コンパイラが再配置をしなければ、memory_order_relaxed store操作に続くmemory_order_relaxed load操作はすでに順序付けられています。コンパイラではそのような並び替えを行う強い動機が存在しないため、大抵はわずかなコストに過ぎません。このようなアーキテクチャにはx86のようなTSOアーキテクチャも含まれます*3。memory_order_relaxed対して通常のload／store命令利用を妨げる制限事項が課されているため、Itaniumアーキテクチャもここに含まれます。POWERアーキテクチャでは公式には規定されていませんが、現在のPOWER実装はここに含まれるように見えます。
memory_order_relaxedで相応のオーバヘッドが追加される主要アーキテクチャは下記と考えられます。
（OpenCLは本質的にC++メモリモデルを採択しているため、ここではGPUアーキテクチャにも関係があり、またこの一貫性は維持したいと考えています。）
ARM上では（およびPOWER仕様によれば）、memory_order_relaxed load操作の後かつ次の異なるメモリ位置へのmemory_order_relaxed store操作より前に、該当load結果をテストする決して分岐しない(never-taken)条件分岐を常に追加することで、要求される順序付けを強制できます。同分岐命令では実際には決して分岐が行われず、後続命令が実行対象となります。（もしmemory_order_consumeがmemory_order_acquireとしてコンパイルされないならば、再び似たように取り扱うことが要求されるでしょう。memory_order_acquire順序付けよりも弱いread-modify-write操作もまた、同様の取扱いが必要となります。）特にコンパイラでは分岐を大幅に遅延させて、load操作完了までの待機ストール回避を期待できるため、この方法はフェンス命令追加よりも相当に安価であると見られています。*4
現行のARMプロセッサ上では、この技法には分岐予測スロットを事実上浪費するという悪影響があるでしょう。これは将来のアーキテクチャ改訂で回避されると推測されます。
一般的に実メモリアクセスの待機を伴うロード操作完了を待機する必要があるため、現行のNvidia GPU上ではより大きなオーバーヘッドが存在すると考えられます。ただし、典型的には待機処理はload結果が本当に必要となるまで遅延可能と見込めるため、このようなオーバーヘッドの大部分は回避されると期待しています。
一部アーキテクチャでは性能への影響があるため、私たちの目標は
- 現行の要件(requirement)からより曖昧な文面の勧告(recommendation)に弱め、そして
- 現行ハードウェア上では効率的に実装できない可能性があっても、望ましい性質を備えるよう、意図された今後の方向性を明確に提示することです。
今後の方向性であっても、現行の意図しない制限よりは実装への影響度が小さいことに留意してください。
29.3節への提案文面
表現上はベンダに対して問題解決の代替手法を探るか、少なくとも短期的には、完全に勧告内容を無視することも明に許容します。しかし、ベンダ仕様の洞察力ある代替案が存在しないなら、勧告の方向性でいずれ要件となることを期待します。
（省略）
atomic変数への非atomicなload／store操作
すでに指摘した通り、本来の設計の一部ではなかったload-to-store順序付けという新たな要件を追加する一方で、memory_order_relaxedへの意図しない要件を取り除きます。一部プラットフォーム上でのmemory_order_relaxed速度低下は、私たちが初期に考案していた仕様と比べての話であり、標準規格の意図しない要求に対してではありません。
atomic変数アクセスにおけるmemory_order_relaxed利用ケースの大部分は実際のところ、他のどんなアクセスと競合するか分からない、もしくは競合なしと断定できない限り廃棄されるというものです*5。これらはほぼ間違いなく安全かつ単純な利用ケース、すなわちdouble-checked lockingでの2回目の“確認”*6や、seqlock*7でのリーダー・クリティカルセクション内部のread操作などをカバーします。
アクセス方法の分離によりこれらのケースをサポートすることで、再び性能を取り戻し、時には若干の性能向上を得ることができます。これらのケースでは事実上read-modify-write操作に適用しないため、新しいmemory_order_値の導入でなくload()とstore()に類似したnon_atomic_load()とnon_atomic_store()関数を追加するのは理にかなっています。こういった操作は競合するコンテキストでは意味が無いため、複数のステップつまりバイト単位で処理されることもあるでしょう。ロックベース実装では、これらの操作はロック獲得を必要としません。またキャッシュ同期の必要もないため、より弱い最適化ルールの影響をうけます。Itanium上では、memory_order_relaxedのときとは違って、通常のload／store操作を用いることでしょう。
ヘルパークラスrace_or<T>の導入によって、競合の可能性があるnon_atomic_load()操作の投機的結果を表現しますが、これらの結果は競合が存在しない時だけ実行されます。race_or<T>は論理的にはTの値。もしくは特別な“競合”値を保持します。どちらを保持しているか確認する手段はなく、競合値からTへの変換は未定義動作(undefined behavior)を引き起こします。
これはnon_atomic_load()呼び出しにより、競合が生じないことのチェック、つまりseqlockが行うような（cf.私の最近のMSPC論文*8）、または多くのトランザクショナルメモリ実装で行われる、インターリーブされたstore操作の不在を確認するためのバージョン番号付与などを許容します。
以前にもatomic変数への非atomic操作サポートという要求は存在しました。例えば、Linuxカーネル中でのC++11/C11 atomic変数利用に対する要求などです。私たちのこれまでの反論は“memory_order_relaxedで十分なはずです；そうでなければ再検討しましょう”というものでした。今回の件は再検討に適したタイミングとなるでしょう。
上記で提案した説得力のない文面を採択するならば、現時点でこの追加は必須ではないと考えます。もし採択を決定するときは、load-to-store順序付け要件を厳格にするより前に、この方針に沿う何らかの変更が必要になると信じています。
非atomicなload／store操作への暫定文面
（省略）
*1:訳注：T3ではx[1]=0かつx[0]=1（T1のstore結果）が観測され、T4ではx[0]=0かつx[1]=1（T2のstore結果）が観測されるような実行。
*2:訳注：POWERやARMのような弱いメモリ順序付け制約のアーキテクチャでは普通に発生する計算結果が、C++11言語仕様 29.3/p9が要求する「有限の評価列により生じる計算結果」では説明不可能な実行となっており、仕様上は意図せず禁止されてしまうというのがLWG2265指摘。
*3:訳注：TSO＝Total Store Ordering。強いハードウェア・メモリモデルなアーキテクチャに分類される。load−load／store−store／load−storeの操作順序は維持するが、store−loadのみ後続load命令の先行store命令追越しを許容する。
*4:訳注：見かけ上は無意味な条件分岐命令を発行することで、C++メモリセマンティクス実現に要求されるハードウェア・メモリセマンティクスを表現し、プログラム実行時のOut-of-Order命令スケジューリングやメモリキャッシュ同期に影響を与える。
*5:訳注：“競合なしと断定できない限り廃棄”という動作は、投機的read処理での割込更新検知による再試行を指すと考えられる。
*6:訳注：http://yamasa.hatenablog.jp/entry/20100128/1264693781 参照
*7:訳注：Linuxカーネル内で利用される、楽観的readを許容するReader-Writerロック機構。詳細はwikipedia:en:Seqlockを参照のこと。
*8:訳注：同論文のポスター http://safari.ece.cmu.edu/MSPC2012/slides_posters/boehm-poster.pdf も参照のこと。
