false sharingとキャッシュライン設計

なぜ「無関係な変数」が干渉するのか

マルチコアの一貫性は キャッシュライン単位 で保たれます。x86-64 や多くの ARM でラインは 64バイト で、CPU はバイト単位ではなくこのブロックごとにメモリと往復し、MESI などのプロトコルがラインごとに状態を持ちます。詳しい状態遷移は メモリ階層とキャッシュコヒーレンシ に譲りますが、本稿で要るのは一点だけです。書き込みは、そのラインを排他的に持つコアでしか行えず、書き込んだ瞬間に他コアの同ラインのコピーは無効化（Invalid）される。

ここに落とし穴があります。一貫性はライン単位なので、ハードウェアは そのラインに何個の変数が同居しているか を区別しません。コア0が変数 a を、コア1が変数 b を更新していて、両者がたまたま同じ64バイトラインに載っていると、a への書き込みが b のコピーまで巻き添えで無効化します。論理的には共有していないのに、ラインを共有しているせいで干渉する。これが false sharing（偽共有） です。

struct counters {
  long hits;    // コア0だけが更新
  long misses;  // コア1だけが更新
};              // 8+8=16バイト → 同一64バイトラインに同居しがち

ライン ping-pong のコスト

false sharing が起きると何が遅いのか。コア0が hits を書くたびにラインは「コア0が排他保有する Modified」になり、コア1の同ラインは Invalid へ落ちます。次にコア1が misses を読み書きするとミスし、ラインを取り直す。今度はコア1が排他保有し、コア0のコピーが無効化される。互いに相手のラインを無効化し合い、1本のラインがコア間を往復し続ける ping-pong が発生します。

コア0: store hits    → ラインをM(排他)で奪取、コア1のコピーをI化
コア1: store misses  → ミス。ラインを奪い返し、コア0のコピーをI化
コア0: store hits    → またミス。奪い返す …（延々と往復）

無効化と再取得はコア間あるいはソケット間の相互接続を経るため、L1 ヒットの数十倍から、ソケットをまたぐと数百サイクル級に膨らみます。マルチソケットでは遠ノードへの転送になり、NUMAとメモリアクセス局所性 の非対称コストがそのまま乗ります。

対策：アラインメントとパディングで分離する

原理から対策は一つに決まります。書き込みが競合する変数を、別々のキャッシュラインへ追い出す。やり方は、各変数をライン境界に アライン し、後ろに パディング を詰めてラインを占有させることです。

struct counters {
  long hits;
  char pad[56];   // 64 - 8 = 56バイト詰めてラインを使い切る
  long misses;    // 次の64バイト境界から始まり、別ラインに乗る
};

ただし手動パディングは保守が難しいので、実務では言語やカーネルの機能を使います。

注意すべきは 両側の保護 です。hits の後ろに詰めても、hits の 手前 に別のホットな変数があれば同じラインに巻き込まれます。確実を期すなら、対象変数の前後をパディングで挟むか、構造体全体をライン境界にアラインしたうえで ____cacheline_aligned 済みの要素を並べます。

per-CPU変数：構造で false sharing を起こさせない

個別の変数を後追いで剥がすより、最初から競合しないデータ構造 にするほうが堅牢です。その代表が per-CPU変数 で、Linux カーネルが多用します。考え方は単純で、共有カウンタを1つ持って奪い合う代わりに、CPU の数だけ独立した複製を用意し、各 CPU は自分の複製だけを触る。

共有1個:   [counter]            ← 全CPUが奪い合い→ping-pong
per-CPU:   [cpu0][cpu1][cpu2]…  ← 各CPUは自分の枠だけ更新→競合なし
           ↑ 各枠をライン境界に整列して隣同士の干渉も断つ

肝は 各 CPU の枠をキャッシュライン境界に整列して配置 する点です。枠が64バイト未満だと隣の CPU の枠と同居して再び false sharing が起きるため、per-CPU 領域はラインアラインを前提に確保されます。更新時は無効化通信が一切走らず L1 ヒットで完結し、読み出し（集計）が要るときだけ全 CPU の枠を合算 します。書き込みは局所・読み出しは集約、という非対称を活かす設計です。

この発想はユーザー空間でも有効です。スレッドごとの統計はスレッドローカルに持って終了時に合算する、ワークキューはスレッドごとに分けて偶にスチールする、といった「まず分割し、合流は最小限に」の形が、ロック競合と false sharing を同時に減らします。ロックそのものを避ける手法は カーネルのロックフリー同期とCAS を併読すると、競合点を消す設計の引き出しが増えます。

設計チェックリスト

まとめ