C++における非対称フェンスの詳細

非対称フェンス？Follyの同期プリミティブを調べていて、コードベースの中で見慣れた名前「非対称スレッドフェンス（Asymmetric Thread Fence）」が目に留まりました。std::atomic_thread_fenceが何を達成しようとしているかはすでに知っていましたが、この構造は何をするのでしょうか？そして、何が「非対称」なのでしょうか？その疑問は、非対称スレッドフェンスの詳細と、それが実際に（少なくともLinux上では）どのように動作しているのかを理解するという興味深い探求へと私を導きました。まず、この構造のためのC++の提案から始め、次に実装の詳細へと進んでいきます。 C++ P1202R0 導入メカニズムは後述しますが、現時点ではこれらのフェンスが何を達成しようとしているのかを理解しておけば十分です。提案を参照して、概要を見てみましょう。 一部の種類の並行アルゴリズムは、共通パスと非共通パスに分割でき、どちらも正しさのためにフェンス（または非リラックスメモリ順序を持つ他の操作）を必要とします。多くのプラットフォームでは、非共通パスにさらに強力なフェンスタイプ（memory_order_seq_cstよりも強力）を追加することで、共通パスを高速化することが可能です。これらの機能は、ますます多くの並行ライブラリで使用されています。私たちは、これらの非対称フェンスを標準化し、メモリモデルに組み込むことを提案します。 本質的に、並行アルゴリズムは元々両方の側でフェンスを必要とする場合があります。しかし、一方のパスが他方よりも著しく一般的である場合、共通パスにはより軽量なフェンスを使用し、より重い同期コストを非共通パスにシフトすることで、コードを最適化できます。共通パスからのパフォーマンス上の利得が、非共通パスのより重いフェンスのオーバーヘッドよりもはるかに大きいことを保証できれば、全体的なパフォーマンスの向上が期待できます。 このパターンは、最初に思われるよりも一般的です。Follyのコードベースを調べると、いくつかの使用例が見つかります。 folly/synchronization/HazptrDomain.h: Hazard Pointers folly/synchronization/detail/ThreadCachedReaders.h: RCU folly/executors/ThreadPoolExecutor.cpp: Thread Pool Executor 論文からの修正された例であるデッカーの例から始めましょう。 ```cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 atomic_int x{0}, y{0}; int r1, r2; // Path A: x.store(1, memory_order_relaxed); atomic_thread_fence(memory_order_seq_cst); r1 = y.load(memory_order_relaxed); // Path B: y.store(1, memory_order_relaxed); atomic_thread_fence(memory_order_seq_cst); r2 = x.load(memory_order_relaxed); // Happens after both paths are completed. assert(!(r1 == 0 && r2 == 0)); // Never fails. We know the assertion cannot fail. ``` C++メモリモデルの下で、これがなぜ失敗しないのかを検証しましょう。 制約 $(1) ightarrow (2)$ および $(1) ightarrow (5)$ は、スレッド構築とスレッド関数の開始との間の同期関係 [thread.thread.constr]/6 から生じます。これはまた、[intro.races]/15 で説明されている書き込み-書き込みコヒーレンス保証を通じて、XとYの両方の変更順序を確立します。 制約 $(4) ightarrow (5)$ および $(7) ightarrow (2)$ は、[atomics.order]/3.3 の要件から生じるコヒーレンス順序です。例えば、$(4)$ と $(5)$ は同じアトミック読み取り-変更-書き込み操作ではなく、$(4)$ は $(1)$ によって格納された値を読み取り、$(1)$ は Y の変更順序で $(5)$ より前に来ます。 [atomics.order]/4.4 から、memory_order​::​seq_cst フェンス $A$ は $(4)$ より前に発生し、$(5)$ は memory_order​::​seq_cst フェンス $B$ より前に発生するため、$(3)$ は単一の全順序 $S$ において $(6)$ より前に来る必要があります。対称的な推論により、$(6)$ も同じ順序 $S$ において $(3)$ より前に来る必要があります。 これは不可能であるため、矛盾が生じます。したがって、r1 == 0 && r2 == 0 となる実行は禁止されます。 さて、非対称スレッドフェンスに戻りましょう。鍵となる考え方は、一部の並行アルゴリズムでは、非共通パスの犠牲を払って共通パスを最適化することに関心があるということです。遅いパスに、より強力な同期コストを吸収させることをいとわない場合、非対称フェンスを使用してコードを再構築できます。論文では、次の変換でこれを説明しています。 ```cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // Globals: atomic_int x{0}, y{0}; int r1, r2; // Fast path: x.store(1, memory_order_relaxed); asymmetric_thread_fence_light(); // Like atomic_signal_fence; // only inhibits compiler reordering r1 = y.load(memory_order_relaxed); // Slow path: y.store(1, memory_order_relaxed); asymmetric_thread_fence_heavy(); // Stronger than atomic_thread_fence(memory_order_seq_cst); r2 = x.load(memory_order_relaxed); // Happens after both fast path and slow path are complete. assert(!(r1 == 0 && r2 == 0)); // Never fails. ``` 現時点では、これらについて知っておくべきことはこれだけです。次に、これらの非対称フェンスがどのように実装されているかを見ていきましょう。 非対称ライトフェンス - コンパイラバリアーまず、より単純なプリミティブであるasymmetric_thread_fence_lightから始めましょう。Follyの実装では、これはGCC/Clangではasm volatile("" : : : "memory")、MSVCでは_ReadWriteBarrier()を使用して実装されており、std::atomic_thread_fence(order)がフォールバックとして使用されます。補足として、asm宣言はC++では[dcl.asm]/1に従って条件付きでサポートされるため、ここでは正確なセマンティクスについてGCCのドキュメント、特に拡張アセンブリセクションを参照します。 ```cpp 1 2 3 4 assembly-template : OutputOperands [ : InputOperands [ : Clobbers ] ] ``` ここでは、clobberリスト、特に特殊な"memory" clobber引数のみに関心があります。 "memory" clobberは、アセンブリコードが入力オペランドおよび出力オペランドにリストされていない項目（例えば、入力パラメータの1つが指すメモリへのアクセス）に対してメモリの読み書きを実行することをコンパイラに伝えます。メモリに正しい値が含まれていることを保証するために、GCCはアセンブリを実行する前に特定のレジスタ値をメモリにフラッシュする必要がある場合があります。さらに、コンパイラは、アセンブリの前にメモリから読み取られた値がアセンブリの後も変更されないとは想定しません。必要に応じて再ロードします。"memory" clobberを使用すると、実質的にコンパイラに対する読み書きメモリバリアが形成されます。 このclobberは、プロセッサがアセンブリステートメントを越えて投機的な読み取りを行うのを防がないことに注意してください。それを防ぐには、プロセッサ固有のフェンス命令が必要です。 これは、コンパイラがasm volatile("" : : : "memory")に関してメモリの読み書きの順序を維持しなければならないことを意味し、実質的にコンパイラバリアとなります。しかし、これはコンパイラによって実行される命令の並べ替えにのみ制約を課し、プロセッサ自体には制約を課しません。CPUは実行時にメモリ操作を順不同で実行する可能性があります。 追加の注意点として、ここでvolatile修飾子が何をするかも調べることができます。 GCCのオプティマイザは、出力変数が必要ない場合、アセンブリステートメントを破棄することがあります。また、オプティマイザは、コードが常に同じ結果を返す（つまり、呼び出し間で入力値が変更されない）と判断した場合、ループからコードを移動することがあります。volatile修飾子を使用すると、これらの最適化が無効になります。出力オペランドを持たないアセンブリステートメントおよびasm gotoステートメントは、暗黙的にvolatileです。 ここでは、volatileはアセンブリステートメント自体に対する不要なコンパイラ最適化を防ぐだけです。厳密には、このケースでは出力オペランドを持たないアセンブリステートメントはすでに暗黙的にvolatileであるため、必要ありません。 非対称ヘビーフェンス - membarrier()非対称フェンスの背後にある主要な同期メカニズムは、asymmetric_thread_fence_heavyにあります。実装戦略はいくつかありますが、ここでは通常のLinuxパスに焦点を当てます。membarrier()システムコールに依存します（別の代替手段としてTLBシュートダウンを強制する方法もありますが、そのアプローチについては十分に精通していないため、ここでは詳しく説明しません）。以前と同様に、std::atomic_thread_fence(order)がフォールバックとして使用されます。 ドキュメントを見てみましょう。 membarrier()システムコールは、メモリアクセスの順序付けに必要なメモリバリア命令のオーバーヘッドを削減するのに役立ちます o