Rustにおけるキャッシュ効率の良いデータレイアウト:フィールドゾーニング、偽共有、128バイトルール
要約
この記事は、Rustで高スループット・低レイテンシのシステムを構築するための低レベル設計に焦点を当てています。特に、CPUキャッシュの効率を最大化するために、データ構造のフィールドをアクセスパターン(書き込み所有者、アクセス頻度)に基づいて「ゾーン」に分割し、キャッシュラインの共有によるパフォーマンス低下(偽共有)を防ぐ方法を解説しています。また、`#[repr(C)]`属性の重要性や、キャッシュラインのサイズ(一般的に64バイトだが、128バイトが最適となる場合もある)についても説明しています。
全文翻訳
Rustにおけるキャッシュ効率の良いデータレイアウト:フィールドゾーニング、偽共有、128バイトルール
キャッシュ効率の良いデータレイアウト:フィールドゾーニング、偽共有、128バイトルール
Rustでの低レベルシステム設計 シリーズのパート1です。このシリーズでは、シングルプロデューサー/シングルコンシューマー(SPSC)リングバッファを例として、高スループット・低レイテンシのシステムコードの書き方を探ります。
パート0 - アーキテクチャの分解 では、最も効果の高い決定(構造的に競合を排除し、各ライターが独自のリングを持つようにする)を行い、シリーズ全体のインデックスと指針となる原則を示しました。
この記事では、マイクロレベルの作業を開始します。1つのSPSCリングバッファが与えられたとき、メモリ内でのレイアウトはどのようになるべきでしょうか?これらのパターンはリングバッファに固有のものではなく、複数のコアが触れるあらゆる構造体に適用できます。
マルチスレッド構造体について誰も教えてくれないこと
シングルスレッドのデータ構造を書くとき、レイアウトに関する唯一の重要な問いは「キャッシュに収まるか?」です。しかし、マルチスレッドの構造体を書くとき、2つ目の、関連性があり、やや微妙な問いが現れます。
各フィールドについて、どのコアがそれを触り、どのくらいの頻度で触るのか?
これを間違えると、プロファイラーが単一のホットラインとしてフラグを立てない方法で代償を支払うことになります。2つのコアが、偶然同じ64バイトのキャッシュラインを共有する異なるフィールドに書き込んでいる場合、ハードウェアコヒーレンスプロトコルを通じて静かに互いをシリアライズしてしまいます。これは偽共有(false sharing)と呼ばれる病理です。コードはロックフリーに見えます。ベンチマークはそうは言いません。
この記事では、レイアウトを意図的に設計することについて説明します。これは2つの部分からなります。
- フィールドゾーニング -
(書き込みオーナー, 頻度)でフィールドをグループ化し、あるコアのホットな書き込みが別のコアのホットなワーキングセットを追い出さないようにします。 - アライメントとパディング - ゾーニングを現実にするためのメカニズム:なぜ
#[repr(C)]が重要なのか、なぜマジックナンバーが64ではなく128であることが多いのか、そしてなぜプリフェッチヒントを追加すると状況が悪化する可能性があるのか。
例として使用するのは、シングルプロデューサー/シングルコンシューマー(SPSC)リングバッファです。1つのコア(プロデューサー)が追加し、もう1つのコア(コンシューマー)が消費します。これらは2つの単調なカーソル、tail(プロデューサーが次に書き込む場所)とhead(コンシューマーが次に読み取る場所)を通じて連携します。
以下の議論と設計原則は十分に一般的ですが、これらの原則を尊重したリファレンスポイントとして、このリングバッファ実装を参照できます。
パート1 - フィールドゾーニング:「誰が何に触るか」に基づいた設計
キャッシュライン(x86-64および多くのAArch64コアでは一般的に64バイト)は、コア間通信の通貨単位です。コヒーレンシートラフィックは、バイトごとやフィールドごとではなく、ラインごとに計算されます。したがって、共有構造体に対する最初の設計上の移動は、アクセスパターンによってフィールドをゾーンにソートすることです。
| ゾーン | フィールド | 書き込みオーナー | コア間アクセス |
|---|---|---|---|
| プロデューサーホット | tail, cached_head | プロデューサー | コンシューマーがtailをサンプリングする |
| コンシューマーホット | head, cached_tail | コンシューマー | プロデューサーがheadをサンプリングする |
| コールド | closed, config, metrics | ライフサイクル/オブザーバビリティ | まれ、ホットパスでのポーリングではない |
「プロデューサーホット」は「プロデューサー専用」を意味するわけではありません。プロデューサーはtailへの書き込みを所有しますが、コンシューマーはキャッシュビューが枯渇したときに依然としてtailを読み取ります。重要な区別は書き込みオーナーシップです。プロデューサーはラインを排他的に保つコアなので、その書き込みに近いフィールドは慎重に選択する必要があります。
まず、用語を定義します。以降の投稿で頻繁に使用します。ホットパスとは、(ほぼ)すべての操作で実行されるコードのことです。ここでは、各コアが毎秒数百万回実行する送受信ループです。ホットフィールドとは、tail、head、および2つのカーソルキャッシュのような、それらのループが触れるフィールドです。対照的に、コールドパスは、構築、シャットダウン、時折のメトリクス読み取りなど、まれに実行されるすべてのものです。コールドフィールドとは、configやmetricsのような、コールドパスのみが触れるフィールドです。「ホット」と「コールド」はアクセスの頻度に関するものであり、上記のテーブルのゾーンがソートされている基準です。
ルールは単純に述べられます:各ゾーンを独自のキャッシュラインセットに配置します。 あるコアによって書き込まれるホットフィールドは、別のコアが頻繁に読み書きするホットフィールドと同じラインを共有してはなりません。プロデューサーがtailにストアしても、コンシューマーのheadまたはcached_tailを保持するラインを無効にしてはなりません。逆も同様です。コールドフィールドは、ホットパスで誰も競合しないため、まとめて後部に詰め込むことができます。
ここでは、ゾーンを宣言に直接エンコードしたリングバッファを示します。型パラメータAは、バッキングバッファのプラグ可能なアロケータにすぎません。気にする必要はありません。重要なのはフィールドの順序とグループ化です。
#[repr(C)]
pub struct Ring<T, A: BufferAllocator = HeapAllocator> {
// PRODUCER HOT
tail: CacheAligned<AtomicU64>,
cached_head: CacheAligned<UnsafeCell<u64>>,
// CONSUMER HOT
head: CacheAligned<AtomicU64>,
cached_tail: CacheAligned<UnsafeCell<u64>>,
// COLD
closed: AtomicBool,
metrics: Metrics,
config: Config,
buffer: UnsafeCell<A::Buffer<T>>,
}
ここで注意深く読むべきことがいくつかあります。それぞれがスタイルの偶然ではなく、意図的な選択だからです。
2つのcached_*フィールドは、コールドゾーンではなくホットゾーンに配置されます。 「スペースがあるか?」を知りたいプロデューサーは、tailとheadを比較する必要があります。しかし、headは別のコアによって書き込まれるため、直接読み取ることはクロスコアコヒーレンスミス(数十から数百サイクル)の可能性があります。代わりに、プロデューサーはcached_headを保持します。これは、プロデューサーが所有する、コンシューマーが前回見た場所のスナップショットです。headの古いビューは、利用可能なスペースを過大報告することは決してなく、常に過小報告する可能性があるため、キャッシュは高速パスで信頼しても安全であり、実際のheadのコストのかかるAcquire読み取りは、キャッシュが部屋がないと判断した場合にのみ発生します。そのスナップショットは、送信ごとに触れられるため、プロデューサーホットゾーンに属します。そして、それは原子型ではなく、単なるUnsafeCell<u64>であるのは、それを書き込むのは1つのコアだけだからです。コンシューマーは鏡像を持ちます。cached_tailは、ローカルスナップショットが枯渇するまで、プロデューサーが所有するtailの読み取りを回避できるようにします。
コールドフィールドは意図的にラインを共有します。 closed、metrics、configは、間にパディングなしでまとめられています。それは怠慢ではなく、それがポイントです。ゾーニングの目標はすべてをアライメントすることではありません。それはコア間でピン留めされるものだけをアライメントすることです。コールドフィールドをパディングすると、ホットデータを常駐させるために使用できたキャッシュラインが無駄になります。ライフサイクルフラグが送信または受信ごとにポーリングされる場合、それはもはやコールドではなくなります。「シャットダウン」という言葉の陰に隠すのではなく、独自のホットゾーンまたはライフサイクルゾーンに昇格させてください。
なぜ#[repr(C)]が実際に機能するのか
構造体上の#[repr(C)]に注目してください。これは装飾ではなく、それを削除すると、レイアウト戦略全体が静かに損なわれます。
デフォルトでは、Rustはrepr(Rust)を使用します。Rustリファレンスは、repr(Rust)がフィールドのアライメントのみを保証し、フィールドが重複せず、集約が十分にアライメントされていることを明示しています。フィールドが宣言順にレイアウトされることは保証されておらず、コンパイラは自由に並べ替えることができます(通常はパディングを最小限に抑えるため)。通常の構造体にとっては機能ですが、パフォーマンスの正確性がtailとheadが異なるゾーンに配置されることに依存する構造体にとっては、並べ替えによって慎重に分離されたゾーンが共有ラインに再び収束する可能性があります。
#[repr(C)]はフィールドを宣言順に固定するため、記述したゾーンレイアウトがそのまま得られます。
見落としやすい微妙な点があります:外側の構造体上のrepr(C)は、ネストされたrepr(Rust)フィールドのレイアウトを再帰的に凍結しません。 これはRing自身のフィールドの順序を固定しますが、例えばMetricsやConfigの内部順序は、それらの型が独自のrepr(C)を持たない限り、依然としてrepr(Rust)です。ネストされた構造体がそれ自身のホット/コールド分割を持っていてそれが重要である場合、それにもrepr(C)を与えてください。ここでは、MetricsとConfigは完全にコールドなので、それは問題ありません。
パート2 - アライメントと偽共有:ゾーニングを現実にする
ゾーニングは意図です。アライメントはメカニズムです。tailとheadが異なるゾーンに属すると宣言しても、バイトが実際に異なるキャッシュラインに着地しない限り、何も達成されません。それがCacheAligned<T>の仕事です。
費用に見合う、1行のヘルパー
/// 値を128バイト境界にアライメントし、コア間フィールドがキャッシュラインを共有しないようにします。
/// 128(対64)はターゲットポリシーです。これは、それらが重要なCPUでの隣接ライン/空間プリフェッチ効果のためのスペースも残します。
#[repr(C, align(128))]
struct CacheAligned<T> {
value: T,
}
impl<T> CacheAligned<T> {
const fn new(value: T) -> Self {
Self { value }
}
}
impl<T> std::ops::Deref for CacheAligned<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
&self.value
}
}
これだけです。Derefを持つ#[repr(C, align(128))]ニュータイプなので、呼び出しサイトでは透過的です(self.tail.load(...)はそのまま機能します)。ライブラリの依存関係は不要です。Ringはrepr(C)なので、コンパイラはフィールドを宣言順にレイアウトし、各フィールドのアライメントを満たすために必要なパディングを挿入します。Rust型のサイズはアライメントの倍数であるため、各小さなCacheAligned<T>も完全な128バイトスロットを消費します。2つのホットフィールドがラインを共有することはなく、さらに重要なことに、それらが続くコールドフィールドと同じラインを共有することもありません。
キャッシュラインは64バイトなのに、なぜ128バイトなのか?
これは人々がつまずく部分です。キャッシュラインが64バイトなら、なぜ128バイトにパディングするのでしょうか?
厳密なラインレベルの分離は、依然として楽観的すぎる可能性があるからです。一部のCPUには隣接ラインまたは空間プリフェッチャの動作があります。1つの64バイトラインに触れると、コアは隣接するラインを投機的にプルする可能性があります。プロデューサーホットデータがコンシューマーホットデータに隣接するラインにある場合、プリフェッチャは、厳密にはラインを共有していなくても、2つを互いのキャッシュに引き込む可能性があります。結果はプリフェッチャによって引き起こされる偽共有です。ラインは技術的には別々ですが、競合は現実であり、ライン粒度のツールは直接それを指さないかもしれません。あなたはそれを、アルゴリズムが予測するよりも低いスループットとして目にします。
小さなカーソルフィールドの場合、各ホットフィールドを128バイトにアライメントすると、偶数の64バイトライン境界に配置されるため、隣接ラインプリフェッチは通常、他のコアのホットデータを引き込むのではなくパディングを引き込みます。
正確な幅を普遍的な定数ではなく、ターゲット固有のポリシーとして扱ってください。Crossbeamの現在のCachePaddedポリシーは次のとおりです。
- 128バイト:x86-64、AArch64、powerpc64
- 256バイト:s390x
- 32バイト:arm、mips、mips64、sparc、hexagon
- 16バイト:m68k
- 64バイト:その他すべて。
Crossbeamは、これらが合理的な推測であり、実行しているマシンの物理キャッシュラインと一致することを保証するものではないことも文書化しています。固定align(128)を持つローカルCacheAligned<T>は、ポリシーを固定したい場合に適切です(例:ターゲットをベンチマークし、それをフリーズしたい場合)。いずれにせよ:ベンチマークで検証してください。128を含む単一の数値を信頼しないでください。
まとめ:CPUが実際に目にするレイアウト
ゾーンとアライメントを組み合わせると、構築は注目に値しません。レイアウト作業はすでに型によって行われています。
Ring {
tail: CacheAligned::new(AtomicU64::new(0)),
cached_head: CacheAligned::new(UnsafeCell::new(0)),
head: CacheAligned::new(AtomicU64::new(0)),
cached_tail: CacheAligned::new(UnsafeCell::new(0)),
closed: AtomicBool::new(false),
// metrics, config, buffer ...
}
プロデューサーコアはtailラインを書き込み、cached_headラインを使用します。コンシューマーコアはheadラインを書き込み、cached_tailラインを使用します。公開されたカーソルは依然として避けられないクロスコア通信を作成します。コンシューマーは時折tailを観測する必要があり、プロデューサーは時折headを観測する必要があります。しかし、それらの無効化はもはや無関係なホットフィールドを引きずりません。それがペイオフであり、ホットフィールドあたり約1つの128バイトスロットを要します。2つのコアに頻繁にアクセスされる構造体にとっては良い取引であり、コールドフィールドに対しては決して行わないでしょう。
2つの直感に反する帰結
キャッシュラインとプリフェッチャのレベルで考えるようになると、「明白な」パフォーマンスの伝承の2つが間違っていることがわかります。
ソフトウェアプリフェッチヒントを散りばめない
プリフェッチャが存在することを知った後、一般的な本能は、次のスロットを早期にプルするために、ホットループに_mm_prefetch(またはRustのcore::intrinsics::prefetch_*)をドロップして、それを「助ける」ことです。リングバッファ、つまりストライド1、線形アクセスでは、これはほとんどの場合損失です。
最新のL1/L2ハードウェアプリフェッチャは、最初の2〜3回のアクセス内で線形ストライドを検出し、CPUの前にキャッシュラインをストリーミングします。手動のソフトウェアプリフェッチはそれに加わるのではなく、それに競合します。命令発行スロットと、デマンドフェッチが実際に必要とするメモリ帯域幅を消費しますが、ハードウェアはすでにそれらのラインを持ってくるつもりでした。これは私が何度も出荷するのを見た間違いです。手動プリフェッチヒントでシードされたホットループ、A/Bベンチマーク、そしてスループットを損なうことが判明しました。ヒントは削除されます。
正直なルール:ソフトウェアプリフェッチは、ハードウェアプリフェッチャが次のアドレスを予測できない非線形アクセスパターン(グラフウォーク、ハッシュテーブルプローブシーケンス、ポインタチェイシング)でのみその価値を発揮します。そして、その場合でも、プロファイルガイド付きの実験がワークロードで役立つことを証明した場合にのみ追加してください。ストライド1のものは、プリフェッチャの邪魔にならないようにしてください。
キャッシュレベルに収まる容量を意図的に選択する
リングのバッファには、カーソルとは別に独自のキャッシュストーリーがあります。容量は特定のキャッシュレベルでの常駐を保証しませんが、階層に運ぶように要求しているワーキングセット予算を設定します。丸い数値を入力してハードウェアにトレードオフを発見させるのではなく、意識的に選択してください。
- L1の近くに留まるようにサイズ設定。 8バイト要素の場合、4,096スロットは32 KiBです。これは、32 KiB以上のL1Dを持つコアでのキャッシュ常駐リングの合理的な開始点になり得ますが、32 KiB L1では他のホットデータのためのスペースが残りません。L1Dのサイズは様々であり、容量的に収まることがゼロL2/L3ミスを保証するわけではありません。競合ミス、プリフェッチ動作、コヒーレンシートラフィック、および同じコア上の他のホットデータはすべて依然として重要です。算術ではなく、ハードウェアカウンターで確認してください。
- バーストを吸収するようにサイズ設定。 256Kスロット(8バイト要素で2 MiB)でサイズ設定すると、バッファがL1常駐であるという仮定を意図的にやめ、バックプレッシャーなしでより大きなバーストを吸収することと引き換えに、低キャッシュまたはLLCレイテンシを受け入れます。
どちらも正当です。正当でないのは、「100万のような良い丸い数字」が設定に忍び込み、ホットパスが運ぶ必要があるワーキングセットを偶然決定させることです。
これはどこに一般化されるか
これらのどれもリングバッファに固有のものではありません。「ゾーンを(書き込みオーナー, 頻度)で分け、クロスコアフィールドをパディングする」パターンは、構造体がコア間で共有されるあらゆる場所に出現します。
- SPSCキューの
tail/headカーソル、およびMPSCキューの競合するカーソル(パディングはそこで偽共有を防ぎます。共有テール競合を排除するわけではありません)。 - シャードメトリクスの各スレッドカウンター(コアごとの
AtomicU64、読み取り時に合計)。 - EBR/ハザードポインタメモリリクラメーションの各コアのエポックカウンター。
- CPUごとのスケジューラー実行キュー。
- ロックフリーハッシュテーブルのリサイズエポックカウンター。
あらゆるケースでレシピは同じです。
- 各フィールドについて、書き込みオーナー、リーダー、頻度を名前付けします。
- フィールドをホットゾーン(書き込みオーナーごとに1つ、および避けられないマルチライターアトミック用の分離ゾーン)とコールドゾーンにグループ化します。
#[repr(C)]で順序を固定します。- ホットなクロスコアフィールドをターゲットに適したキャッシュ境界にパディングします。Crossbeamのポリシーではx86-64/AArch64/powerpc64で128バイト、または
CachePaddedに選択させます。 - コールドフィールドは詰め込んだままにし、線形ループにプリフェッチヒントを追加しないでください。
perf c2cなどのハードウェアカウンターで、およびスループットベンチマークで勝利を検証してください。なぜなら、これらのバグは、プロファイラがあなたのために指摘しないバグだからです。
構造体はどちらの方法でもロックフリーに見えます。2つのバージョンの違いは、ハードウェアが同意するかどうかです。
誤植
2026-08-23追記
構造体リストは古く、4番目のゾーンがあります。 リファレンス実装のデータ競合の修正(ringmpsc-rs#5、PR #6)により、構造体の末尾が変更されました。Ringは現在、スロット0への生のベースポインタを保持し、バッファハンドルは追加のBoxの背後にあります。
// COLD
closed: AtomicBool,
metrics: Metrics,
config: Config,
base: *mut MaybeUninit<T>, // 新しいフィールド
buffer: Box<UnsafeCell<A::Buffer<T>>>, // 元は UnsafeCell<A::Buffer<T>>
この記事のすべてのレイアウト引数は変更されません。#[repr(C)]は依然として重要であり、ホットゾーンは依然としてパディングされ、コールドフィールドは依然として意図的に詰め込まれています。
しかし、baseはこの投稿で名前が付けられた3つのゾーンには適合せず、その不一致は厄介ではなく興味深いものです。これは、すべての操作で両方のコアによって読み取られ、構築後決して書き込まれません。それは4番目のカテゴリ、不変共有となります。それがclosed、metrics、configの隣にパディングなしで配置できる理由は、まさにこの記事のテーマです。ゾーニングは、あるコアから書き込まれ、別のコアから読み取られるラインから保護します。誰も書き込まないラインは、すべてのコアが永遠に共有でき、各コアのキャッシュに、コヒーレンシートラフィックなしで配置できます。読み取り専用データは、同時構造体の中で最も安価なものです。だからこそ、「コールド」と「共有」は同じ軸ではなく、フィールドを配置する正しい質問は「ホットか?」ではなく「誰がそれを書き込むか?」なのです。
さらに2つの小さな注記があります。buffer上の追加のBoxは、バッファハンドルを固定アドレスにピン留めし、Ringの移動中もbaseを有効に保ちます。これは構築時に1つの割り当てを要し、ホットパスでは決して触れられません。そして、フィールドは16バイトではなく8バイトになりますが、詰め込まれたコールドテールの最後にあるため、ゾーニングには何も影響しません。