yohhoyの日記

技術的メモをしていきたい日記

(抄訳)N2176 メモリモデルの論理的根拠[一部]

元文書:N2176 Memory Model Rationales, Why atomics have integrated ordering constraints, Hans-J. Boehm氏, 2007/03/09

自分自身の理解のために日本語訳を行ったC++11標準ライブラリatomic操作と順序制約(メモリオーダー; memory order)に関する文書。

atomic変数に順序制約を統合する理由

検討中のatomicオブジェクトにおけるインタフェースでは、atomic操作それ自体の一部として順序制約(ordering constraints)を備えています。これはJavaC#におけるvolatileベースのアプローチや、atomic_opsパッケージとも整合します。一方でLinuxカーネル内部のatomic実装のように、明示的なメモリフェンス(memory fence)利用を必要とする実装との整合性には欠けます*1
この選択に対する論理的根拠はN2145N2047にて部分的に示されています。ここでは、これら論理的根拠を少し拡張し更新したバージョンを提示したいと思います。
N2153でも、特定アプリケーションやアーキテクチャ上で最大性能を得るために、やはり明示的フェンスは必要であると主張していることに留意ください。ここでの議論はフェンスを排除するものではありません。
本文書では、atomic操作と順序セマンティクスが明示的に関連付けられる理由、また異なるセマンティクスそれぞれに異なる順序制約が提供される理由を列挙します:

X86やItanium等のアーキテクチャでは、複雑なコンパイル時解析を行わなくとも、この統合によって十分に高速なコードを得ることができます。例えばX86では、ロックの解放操作は、暗黙の“release”セマンティクスをもつと広く信じられている単純store命令にて行われます。ソースコードstore_releaseとして表記される場合は、store命令へとマッピングするのは簡単です。また、store操作に続くフェンスとして表現される場合には、コンパイラは該当フェンスが冗長であると推論するでしょう。
X86プロセッサでは、正確に適切なフェンス(store操作に対し"LoadStore"と"StoreStore"並び替えを抑止するフェンス)が使われた場合に限り、そのフェンスは冗長なものになります*2。(N2153ではそのようなフェンスを提案しています。)
Itaniumでは、明記された時点で、一般にフェンスをst.rel命令へと最適化することができません。これを確認するため、架空のロック解放シーケンスについて考察しましょう:

x = 1;  // ロック保護された代入
LoadStore_and_StoreStore_fence(); // 架空の最適フェンス
lock.store_relaxed(0);  // spinlockのatomicクリア操作
y.store_relaxed(42);  // 無関係なatomic操作

このコードではxyへの代入操作の入れ替えを許容しないことに留意ください。(訳注:xとlockへの代入入れ替えを抑止するフェンスにより、本来は無相関だったxとyの入れ替えをも禁止している。)しかし、Itanium上で、本当は下記コードと等価になる変形を行いたいとします。

x = 1;  // ロック保護された代入
lock.store_release(0);  // spinlockのatomicクリア操作
y.store_relaxed(42);  // 無関係なatomic操作

このバージョンではxyへの代入順入れ替えを許容するため、このような変形は安全ではありません。(訳注:フェンスを明示したコードとはプログラムのセマンティクスが変わってしまうため。)より現実的な状況では、yへのstore操作のような後続の代入文が存在しないと断定するのは困難でしょう。そのため、このような変形を実現できるとは一般に期待できません。
この問題は正直なところItanium仕様に多分に依存しています。とはいえ、上記のような入れ替えは許容されるべきで、フェンスベース実装では不必要な制約を導入してしまいます。もしフェンスだけが提供されるとすると、スピンロック解放操作のような例でも抽象的に正確な順序制約を表現できなくなってしまいます。

atomic操作に関連付けられたacquire/release順序制約は、該当atomic変数へアクセスするスレッドにのみ影響を与えます。従って、仮にコンパイラ最適化器がそれらのスレッドを統合(あるいは、始めの1スレッドだけが存在)する場合、atomic操作を通常のメモリ操作へと変更できるだけでなく、生成コードからフェンスやそれに類する機構を消し去ることができます。一方で、フェンスはメモリアクセスの無制約な集合を順序付けるため、フェンスを消し去れるほど最適化器に対して全てを十分に可視とはできそうもありません*3。(これは前掲の指摘と密接に関連しており、また現時点でも改訂中のメモリモデル詳細に依存した仔細なメリットです。)

多くのケースで、順序制約統合はより使い勝手が良いと考えられます。例えば、ダブルチェック・ロック処理(double-checked locking)は、明示的なバリアを使わずに、load_acquire操作とstore_release操作を用いて容易に記述できます*4。(フェンス利用版のセマンティクスは不必要に強くなり、Itaniumでは無用なオーバーヘッドを引き起こします。他アーキテクチャにおいて逆が成り立つような一般例が存在するかは分かりません。)

順序制約の統合は、atomicなload/store操作が“標準的”にacquire/releaseセマンティクスを持ち、一方でより弱い選択肢も存在しうるという事を表す簡単な方法を提供します。acquire-load操作とrelease-store操作は、依存性ベースのメモリ順序付け*5を必要とせず、極めて望ましい特性を享受できます。これらは、ナイーブなプログラマが無理解に期待するであろう最小限の順序付け特性と考えられます。*6

順序制約を統合したことで、順序付けの問題を無視され難くします。このレベルでは(訳注:atomic変数を利用するプログラム設計)、順序性を無視することはほとんど常に誤りです。既存のatomic変数インタフェースの多くでは、メモリオーダー取り扱いのいい加減さであったり、有用な順序制約記述が不可能になってしまうことの双方に苦慮しています。経験的に、このようなインタフェースは多数のバグをもたらします。

全ての“競合(race)”がatomic操作のみに起因すると仮定した場合、明示的に順序付けられたatomic変数は逐次一貫性(sequential consistency)を保証する“高次の”atomic変数ときれいに統合されます。これらは再び、C++Javaをまたぐ一貫したプログラミングモデルを提供します。(C#のvolatileは本質的にacquire/release atomic操作と考えています。そのため、C#との一貫性も獲得すべきです。)

*1:訳注:Linux kernel atomicドキュメント中ではメモリフェンスではなくメモリバリア(memory barrier)と呼称している。

*2:訳注:Intel x86アーキテクチャは強い(strong)メモリモデルを採るため、そもそもLoadStoreやStoreStoreの並び替え(追い越し)は発生しない。つまり、store命令に先行するフェンス命令を発行する必要がない。Java言語メモリモデルと各アーキテクチャでの実装方針について整理したThe JSR-133 Cookbook等も参考のこと。

*3:訳注:フェンス使用は全てのメモリアクセス操作に対して順序付けを強制するが、acquire/releaseでは特定atomic変数に対する操作に対してのみ順序付けを行う。つまりフェンスを用いて順序付けを表現した場合、セマンティクス上は無関係な他メモリアクセスに対しても順序付けを表明したことになってしまう。このような冗長性により、本来は制限されるべきでない変数アクセス順序入れ替えが出来なくなり、コンパイラによるコード生成最適化に不必要な制約を課す。

*4:訳注:C++0x時代の Double-Checked Locking - yamasaのネタ帳

*5:訳注:C++11ではデータ依存性に基づく順序付けが採用された。C++0xのメモリバリアをより深く解説してみる - yamasaのネタ帳

*6:訳注:「依存性ベースのメモリ順序付け」とは異なり、acquire/releaseセマンティクスではよりシンプルなsynchronizes with関係によりスレッド間の順序付けを行う。本文書ではacquire/releaseセマンティクスの関係性を「無理解なプログラマが期待する最低ライン」として扱っている(が、一般的プログラマにとってはatomic操作の既定値std::memory_order_seq_cstが最低ラインだと思う。)