元文書：(PDF)N4215 Towards Implementation and Use of memory_order_consume, P.McKenney/T.Riegel/J.Preshingほか, 2014/10/05
訳出メモ：
- 自分自身の理解のために日本語訳を行ったC++メモリモデル／memory_order_consumeに関する提案文書。§5, 6のみ訳出。
- C++メモリモデルへのmemory_order_consume導入は、LinuxカーネルRCU(read-copy-update)での利用を一つの目的としていた。（§3.1冒頭）
- memory_order_consume, carries_dependency属性, kill_dependency()関数 についてはC++0xのメモリバリアをより深く解説してみる - yamasaのネタ帳やThe Purpose of memory_order_consume in C++11などを参照のこと。
- LinuxカーネルRCUについてはIntroduction to RCU、@IT記事やLinux Kernel Watch記事などを参照のこと。
5. C11およびC++11処理系での順序依存性
依存性順序付け(dependency ordering)の問題を避ける最も単純な方法は、全てのmemory_order_consume操作をmemory_order_acquireへと強化することです。これは正しく機能しますが、ARMやPowerPCといった弱い順序付けシステム上では、メモリバリア命令挿入によって許容しがたい性能低下をもたらし5、またコード移動を伴う最適化を必要以上に抑制することでしょう。
脚注5) Linuxカーネルコミュニティの観点では、「許容しがたい性能低下につながるであろう」と解釈すべきです。
（訳注：C11/C++メモリモデルのセマンティクス上、consume操作からacquire操作へは常に安全に変換できる。この変換によってより強い順序付け保証を要求するため、弱いメモリモデルのハードウェア上では、メモリバリア命令発行など追加の実行時オーバーヘッドが必要となってしまう。）
もう一つの単純なアプローチは、値の投機(value speculation)やその他の依存性を壊す(dependency-breaking)最適化を避けることです。これは最適化の機会損失につながりますが、依存性チェイン・アノテーションの必要性や、依存性を壊す最適化に起因する他のあらゆる問題を避けることができます。またこの方法は、Linuxカーネルコミュニティでの依存性チェインに対する現行アプローチと完全な互換性があります。残念ながら、依存性チェインを壊すが有益な最適化というものは多数存在するため、この方法は現実的ではありません。
3番目のアプローチは、memory_order_consume load操作や[[carries_dependency]]属性(attribute)を含む関数では、値の投機など依存性を壊す最適化を避ける方法です。例えば、そのような関数中では、a = b + c - cをa = bと変形するような最適化はキャンセルされ、図10に示すハードウェア分岐予測(hardware-branch-predition)最適化は禁止されるでしょう。この方法は前述アプローチに比べて非常に限定的ではあるものの、やはり最適化の機会損失となりえます。また図11の関数d()のように、[[carries_dependency]]属性を付けない関数では、依存性を壊す最適化に起因する問題を引き起こします。さらに図12の関数g() return文のように依存性チェインがスコープ外へ出る場合は、にせのメモリバリア命令を発行することになります。
（訳注：依存性チェインが関数スコープ外へ出てしまうため、依存性順序付けによるハードウェア・メモリ可視性保証に依存しないよう、保守的にメモリバリア命令を発行してしまう。）
（図10〜12省略）
4番目のアプローチは、RCU参照側クリティカルセクション(RCU read-side critical section)開始／終了に相当するコンパイル時操作を追加する方法です。これらは入れ子構造や条件付きクリティカルセクション開始／終了があり得ることも考慮して、コンパイル時に評価する必要があるでしょう。最外RCU参照側クリティカルセクションからの終了は、到達時点で有効な各変数に対するkill_dependency()操作を意味することに留意ください。6しかしながら一般的なケースでは、あるRCU参照側クリティカルセクションの境界を正確に決めるすることは恐らく不可能であり、大半のケースでそのクリティカルセクション範囲を過大評価するよう保守的手段を採るべきでしょう。このアプローチでは、図11の関数c(), d()では依存性チェインを自然な方法で扱いますが、プログラム全域解析(whole-program analysis)を避けるには、C11/C++11標準の[[carries_dependency]]アノテーションに類似する何かを必要とするでしょう。
脚注6) あるrcu_read_unlock()が最外RCU参照側クリティカルセクションの出口となることもあり、またあるときは他のRCU参照側クリティカルセクションの入れ子になるとしたら？この場合は、kill_dependency()を適用すべきではありません。
5番目のアプローチは、あらゆる依存性チェインの本質的サブセット上の全操作にアノテーションを要求することでしょう。この方法は実装が非常に容易ですが、Linuxカーネルコミュニティには受け入れられそうもありません。
6番目のアプローチは、C11/C++11標準が求めるように依存性トラッキングを行います。ただし、[[carries_dependency]]なしに依存性チェインが関数に出入りするときは、メモリバリア命令を発行する代わりに、暗黙のkill_dependency()呼び出しを挿入します。このようなケースでは、処理系は診断(diagnostic)もオプションで出力すべきです。この方法はLinuxカーネルRCUコードをC11へ変換する場合に、[[carries_dependency]]よりもkill_dependency()の方が多くなることを期待したものです。例えば図12では、関数f()の明示的なkill_dependency()が無くても、関数g()での不必要なメモリバリア命令発行を回避します。両関数とも図12にあります。
最後7番目のアプローチは、C11/C++11標準が求めるように依存性トラッキングを行います。この方法では、関数e()とf()は必要な依存性順序付けの量を適切に維持します。
6. C11およびC++11依存性順序付けの欠点
これまでの経験から、C11およびC++11標準が規定する依存性順序付けには、さまざまな欠点があると判明しました：
1. C11標準は属性、特に[[carries_dependency]]属性を提供をしません。このため、開発者は関数呼び出しや関数からのリターンをまたぐ依存性チェインの指定ができません。
2. 両標準により要求される依存性チェイン・トラッキングの実装複雑度は、非常に面倒なものになりうる一方で、memory_order_consume load操作をmemory_order_acquireへと無条件昇格することは、弱い順序付け処理系上では過剰なオーバーヘッドになりえます。したがって、弱い順序付けシステム上でmemory_order_consumeを実装する安易な方法は存在しません。
3. 関数レベルの[[carries_dependency]]では粒度が粗すぎると考えられます。一例として、コンパイラによるポインタ解析(points-to analysis)は自明でなく、あるポインタが依存性を伝搬をする／しないと判定するのが困難なことが挙げられます。たとえば、現行標準の文面はstoreからloadを介した依存性チェインを（意図的に！）許可していません。そのため、依存性伝搬中の値がある変数に書き込まれたとしても、その変数からのあらゆるload操作が依存性伝搬する前提にすべきと、処理系は合理的仮定を置くでしょう。*1
4. 標準が定める規則[N3691*2, 1.10p9]は、C11/C++11以前のコンパイラ利用時に依存性チェインを維持するために、現在のところ開発者が守るべき規則とはあまり整合しません。例えば、標準はx-xが依存性を伝搬することを要求し、この保証の提供は少なくとも、xが依存性を伝搬しているときに、コンパイラへx-x（や類似のパターン）を除去する最適化を止めるよう要求します。また他の例として、4.1節の9項目で既に説明したような、開発者が書きがちな図13に示す値の投機的コードを考えます。この例では、標準は1行目 memory_order_consume loadと後続3行目 参照外しとの間で依存性順序付けを要求しますが、典型的なコンパイラが同値にみえる2変数を区別するとは期待できません。これら2つの例は、人工的な依存性の挿入、最適化の省略、同一に見える値の区別、またはmemory_order_acquireフェンス発行といったケースさえ、コンパイラが検出して注意深く扱う必要があることを示しています。
図13: Dependency-Ordering Value-Narrowing Hazard
1 p = atomic_load_explicit(gp, memory_order_consume); 2 if (p == ptr_a) 3 a = p->special_a; 4 else 5 a = p->normal_a;
（訳注：2行目でp == ptr_aを検査するため、3行目ではコンパイラはpとptr_aを同一とみなして依存性チェインを扱うこともできる。一方、ハードウェアによる依存性伝搬ではp->special_a相当を実行するレジスタ間依存性が必要となるが、3行目をptr_a->special_a相当の機械語命令列にコンパイルしてしまうと、本来必要なメモリ可視性保証がなされず不正な実行結果となる。）
5. memory_order_consumeと依存性チェインによる効果の本質は、開発者にコード最適化を許可することです。この手の最適化の試みは、[[carries_dependency]]属性の助けなしに依存性チェインがスコープ外に出る場合に、現行標準が要請するmemory_order_acquireフェンスにより完全に無力化されてしまいます。コンパイラによるこういったフェンス発行を防ぐには、kill_dependency()の十分な使用が要求されます。しかし、この方法はコードをノイズだらけにし、開発者の多大な労力と、さらには特定コンパイラのあるバージョンで最適化される（つまりフェンス発行を避ける）コードパターンや、最適化されない（人手でkill_dependency()の挿入が必要な）コードパターンについて、かなりの知識を持つことを開発者に要求します。
（訳注：consume→acquire昇格は安全なため、コンパイラが依存性チェイン解析を行わない／トラッキング不可となった場合は、若干の実行時コスト増加と引き換えにacquireフェンス相当メモリバリア命令を発行すればよい。あえてconsume操作を用いるほどのコード最適化を達成するには、memory_order_consumeとkill_dependency()を効果的にコード中に配置せねばならず、またコンパイラ固有の最適化・コード生成の振る舞いも熟知していないとダメ。無理ゲー。）
本稿執筆時点では、C11/C++11依存性順序付けを完全にサポートする処理系は知られていません。こういった欠点をPaulは当時予測できなかったのかという点は、確認する価値があります*3。これにいくつかの理由があります：
- Paulが標準化活動を始めた時期からこの7年間を通じて、コンパイラがより積極的な最適化を行うようになりました。
- 同時に、依存性順序付けの新たなユースケースが生まれてきました。特に、依存性チェインが複数コンパイル単位に広がるような、長い依存性チェインが多数存在します。
- この期間で依存性チェイン数のオーダーが変わるほど増加したため、コーディングスタイルの乗り換えに具体的な利点が無い限りは、Linuxカーネルコミュニティによる抵抗の増大に直面することが予想されます。*4
次章では、C11/C++11標準で定義される依存性順序付けの代替案候補を、いくつか考察していきましょう。
*1:「store-loadを介した依存性チェインを不許可」は、C++11 1.10/p9-10 carries a dependency関係とdependency-ordered before関係の定義に対応している。ような気がする。コンパイラによるwikipedia:ポインタ解析は困難かつ限定的効果に留まるため、ポインタ値のrelease-consume操作を経由した依存性チェイン追跡が現実的ではなく、ポインタ型変数からのconsume操作以前に接続されている依存性チェインを特定できない。んじゃないかなぁ。consume操作側の機械語命令列生成にはあまり関係ない気がするが、例示にポインタ解析を挙げていることから、大局的な依存性チェイン・トラッキングの分断によって、ある種の最適化機会が制限されることを指すのだろうか。いずれにせよ、この2文の論理的接続を理解できていない。かゆ うま
*2:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3691.pdf
*3:Paul E.McKenney氏はLinuxカーネルRCUのメンテナであり、N2260 C++ Data-Dependency Ordering初期提案者でもある。また、本提案N4215の筆頭著者にもなっている。
