HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

C++ Details of Asymmetric Fences (nekrozqliphort.github.io)

44 pointsby anon_farmer3 コメント

要約

この記事では、C++の非対称スレッドフェンス(Asymmetric Thread Fence)について解説します。これは、並行アルゴリズムの共通パスを軽量なフェンスで最適化し、稀なパスに重い同期コストをシフトすることで全体的なパフォーマンスを向上させるための提案です。記事では、C++の提案(P1202R0)の概要、デッカーの例を用いた説明、そしてLinuxにおける`membarrier()`システムコールを用いた実装の詳細に触れています。

全文翻訳

学習者のメモ: Linuxのmembarrier()システムコール - 非対称フェンスの詳細

非対称フェンスとは?

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 ExWcutor

論文からの変更された例であるデッカーの例から始めましょう。

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.

このアサーションが失敗しないことはわかっています。C++メモリモデルの下でその理由を調べてみましょう。

[画像: Dekker's Example] [画像: Dekker's Example]

  • 制約 $(1) \rightarrow (2)$ および $(1) \rightarrow (5)$ は、スレッド構築とスレッド関数の開始との同期関係 [\ thread.thread.constr]/6 から生じます。これは、[\ intro.races]/15 で説明されている書き込み-書き込み一貫性保証を介して、XとYの両方の変更順序も確立します。
  • 制約 $(4) \rightarrow (5)$ および $(7) \rightarrow (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)$ はすべての memory_order::seq_cst 操作の単一の全順序 $S$ において $(6)$ より前に来る必要があります。対称的な推論により、$(6)$ も同じ順序 $S$ において $(3)$ より前に来る必要があります。

これは不可能であるため、矛盾が生じます。したがって、r1 == 0 && r2 == 0 の実行は禁止されます。

ここで、非対称スレッドフェンスに戻りましょう。重要な考え方は、一部の並行アルゴリズムでは、非共通パスの犠牲を払って共通パスを最適化することを重視することです。遅いパスがより強力な同期コストを吸収することを許容するならば、非対称フェンスを使用してコードを再構築できます。論文はこのことを次の変換で示しています。

// 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) が使用されます。補足として、C++では asm 宣言は [\ dcl.asm]/1 によると条件付きでしかサポートされないため、ここでは正確なセマンティクスについてGCCのドキュメント、特に拡張アセンブリセクションを参照します。

1 2 3 4
asm asm-qualifiers (
    AssemblerTemplate
    : OutputOperands
    [ : InputOperands
    [ : Clobbers ] ]
)

ここでは、クロバーリスト、特に特別な `