メモリ階層 基礎

下記の数値は古典的な「Latency Numbers Every Programmer Should Know」 (Jeff Dean、~2009、現代ハードウェア向けに更新)。10 桁にまたがる。 右側のリスケール列が最も有用な教育的トリック:1 回の L1 ヒットを 1 秒として扱い、 他のあらゆる操作を比例的にスケールする。DRAM アクセスは 100 秒に、 DC 間 TCP パケットは 19 日に、大陸間往復は 16 年に。

この表は何のためにあるか

これらの桁感を覚えるのが基礎。そこから 2 つの具体的判断形状が出てくる:

• 隣接層間の 100× ルール。階層を 1 段下がるごとにおおむね 100 倍が乗る。 L1 → DRAM は 100×、DRAM → SSD はさらに 1000×、SSD → 大陸間はさらに 1000×。 つまり何でも適切な層にキャッシュすれば、それが効くとき 100–1000× の勝利。
• 1 回の DRAM ミスは ~100 個の有用な ALU 命令に相当する。3 GHz コアは定常で 3 命令/サイクル。100 ns ミス = 300 サイクル = 待ち中にコアができたはずの独立した依存のない仕事 ~900 命令。 アウトオブオーダー実行は一部を回収するが、全部ではない —— そして待ち自体がメモリ律速ワークロードで IPC を 1 未満に押し下げる。

なぜ右側の列が左側より重要か

生の ns 数字は人間の推論に自然に対応しない。1 ns vs 100 ns に直感はない —— どちらも「瞬時」に感じる。 秒対月にリスケールすると、ギャップが人間の脳が日常的に扱う形状にスナップする。 DC 間 RTT に対し「これのために街を車で横断するか?」を問うのは使えるコストフレーム; 大陸間 RTT に対し「飛行機に乗るか?」も同様。 多くの性能設計エラーはこれらの距離を桁数で過小評価することから来る。

この表が示さない 2 つの数字

スループット、レイテンシではなく。表は操作あたりのレイテンシ。 各層の集約帯域も知る価値がある:L1 ~1 TB/s、DRAM ~80 GB/s(チャネルあたり)、 NVMe ~7 GB/s、10 GbE NIC ~1 GB/s。DRAM 越しの memcpy は帯域律速、レイテンシ律速ではない; プリフェッチがうまく効く配列反復はレイテンシにもかかわらず DRAM ピーク帯域近くで走る。

分散。レイテンシは分布であって 1 つの数ではない。 DRAM アクセスは平均 100 ns だが、競合下では尾値ははるかに高くなる。 「NVMe SSD」100 μs レイテンシは中央値;負荷下の 99 パーセンタイルは 10 倍高くなり得る。 右側の列は分散について嘘をつく。尾レイテンシに敏感なシステムでは、 中央値ではなく p99 数値が重要。

メモリを自由に設計できるとする。速い(レイテンシ 1 ns 以下)、大きい(チップあたり TB 級)、安い(GB あたり 1 ドル)が欲しい。 各制約は単独で達成可能;任意の 2 つも;3 つ揃えるのは不可能。 階層は工学的妥協 —— ALU の隣に小量の「速くて高い」メモリを置き、 その隣に大量の「遅くて安い」メモリを置く —— ソフトウェアは単一の連続したアドレス空間の幻想を得る。

制約 1:光速

光は真空で 1 ns あたり約 30 cm 進み、シリコンや銅ではおよそ半分。 1 cm² チップの一角から対角への信号は ~1 cm の往復が必要、光速で 0.1 ns。 トランジスタや配線を通る実際の信号伝播遅延はその数倍。 ALU から数 mm 以上離れたものへのレイテンシ下限はナノ秒級。 ALU 隣の SRAM セルが速いのは、まさに近くに置けるほど小さいから; パッケージ反対側の DRAM バンクは往復が支配的なほど遠い。

制約 2:トランジスタ密度とリフレッシュ

SRAM(キャッシュ用技術)は 1 ビットに 6 トランジスタ。 DRAM(主メモリ用技術)は 1 ビットに 1 トランジスタ + 1 キャパシタ。 DRAM は単位面積あたり ~10× 多くのビットを詰めるが、 代価は数 ms ごとに各セルをリフレッシュする必要(キャパシタが漏れる)と、 100× 遅いアクセス(各読みが小さなキャパシタ経由でビット線を充電する)。

コスト面:SRAM ~$100/GB、DRAM ~$5/GB、NAND フラッシュ(SSD)~$0.10/GB、 ディスク ~$0.02/GB。各層は上の層よりおおむね 100× 安い。 SRAM 価格で 1 TB L1 キャッシュのマシンを構成すれば 1 億ドル; 1 TB ディスクなら 20 ドル。階層がコンピュータを買える値段にしている。

制約 3:熱予算

速いメモリはバイトあたりの電力(静的・動的とも)が大きい。 現代のデスクトップ CPU は ~150 W、サーバ CPU は 300–400 W を放熱する。 10 GB のキャッシュ級 SRAM を積んだチップを作れば静的電力はキロワット級 —— どんなプログラムが走る前にシリコンが溶ける。 階層は速い層をパッケージの熱包絡に収まるサイズに保つ。

階層がどう解決するか

「小さくて速い」を「大きくて遅い」の上に積む。各レベルが下のレベルのホットな部分集合を保持する。 CPU のメモリサブシステムはソフトウェアから階層を隠す: ロード命令がアドレスを問うと、L1 が最初にチェック、なければ L2、その後 L3、DRAM、 (OS のページフォールトハンドラ経由で)ディスク。 プログラムの視点には 1 つのメモリしかなく、ハードウェアが透過的にバイトを階層間で動かす。

包含 / 排他(inclusion / exclusion)方針は各レベルが何を保持するかを決める:包含的な L3 は L1 と L2 の上位集合を含む(coherence を単純化するが容量を浪費);排他的な L3 は内側キャッシュにないものだけを保持する(総容量が多いが coherence が複雑)。 現代の Intel は通常包含的、AMD Zen と Apple は通常排他的または非包含的(弱い版)。

階層は問題を解決するというより、平均ケースを速くする。最悪ケース(キャッシュ冷、ページテーブル冷、 ディスクシーク)は依然として §1 の数値が示す災害。性能仕事のゲーム全体は、 ホットパスを温かい層に保つこと。

キャッシュライン —— 転送の単位

キャッシュは DRAM から個別バイトをロードしない。キャッシュライン —— 固定サイズのブロック、現代の一般的なあらゆる CPU (x86、ARM64、Apple Silicon、POWER)で 64 バイト —— をロードする。 キャッシュにない 1 バイトを読むと、ハードウェアはそのバイトを含む 64 バイトライン全体を取得する。 10 アドレス先の別バイトを読む —— 同じライン、すでにキャッシュ済み、無料。 100 アドレス先の別バイトを読む —— 別のライン、再び完全な転送。

これが空間局所性が重要な理由:1 回のキャッシュミスはすでに 64 バイト分の代金を払った、 それらを使い切るのは本質的に無料。配列上の逐次反復は 1 回の DRAM アクセスを 多くの要素読み出しに償却する。64 バイトを超えるストライドで反復すると、 ラインごとに 1 バイト使い、残り 63 バイトを無駄にする。

セット連想度 —— ラインが住むことを許される場所

キャッシュには有限のスロットがあり、ずっと大きなメモリから引き出す。 新しいラインが来たとき、どのスロットに入るか?3 つの戦略:

• ダイレクトマップ(direct-mapped):各メモリアドレスはちょうど 1 つのスロットに対応する(アドレスの一部のビットで決まる)。 安く速いが、2 つのホットアドレスが同じスロットに対応する場合の競合ミスに苦しむ。
• フル連想(fully associative):任意のアドレスが任意のスロットに住める。ヒット率は最高だが、 全スロットを並列に検索する必要があり —— 小さなキャッシュ (16–32 エントリ、TLB のような)を超えると高すぎる。
• N-way セット連想(N-way set-associative):実用的な妥協。キャッシュは セット に分割される; 各アドレスはちょうど 1 つのセットに対応する; そのセット内では N 個の ウェイ のいずれかに住める。 現代の L1 は通常 8-way、L3 は 16-way 以上。 ルックアップは N 個のタグを並列に比較 —— 管理可能なハードウェアコスト。

追い出し方針 —— セットが満杯のとき何を捨てるか

セット内の N ウェイすべてが占有され、新しいラインが来ると、1 つを捨てる必要がある。 真の LRU(Least Recently Used)は「未来を見ない」方針の中で理論的最適だが、 正確な LRU 順序の追跡はセットあたり log₂(N!) ビットが必要で、ハードウェアには多すぎる。 実キャッシュは近似する:

• Pseudo-LRU (PLRU):ビットの二分木、セットあたり O(log N) ビット、 十分良く LRU を近似する。
• ランダム:ランダムにウェイを選ぶ。安く、意外と競争力がある。
• NRU (Not Recently Used):各ラインが「使用済み」ビットを持つ; 周期的にクリア;ビットがクリアなラインから追い出す。

ワーキングセットがキャッシュに収まる場合、追い出し方針はほとんど重要ではない。 収まらない場合、LRU とランダムの差は 1 桁パーセント。 勝敗の要因はワーキングセットが収まるかどうか —— locality セクションを参照。

ハードウェアプリフェッチャ

CPU は逐次アクセスパターン(連続ライン、または固定ストライド)に気づくとプリフェッチを始める —— プログラムがまだ要求していないラインに対する 投機ロードを発行し、要求すると見込む。現代のプリフェッチャは複数のストリームを独立に追跡し、 いくつかのキャッシュラインを跨ぐストライドパターンを検出でき、 TLB の協力でページ境界を跨いだプリフェッチさえできる。

プリフェッチャは見えない —— 見えなくなるまでは。配列上の線形スイープが DRAM ピーク帯域近くで 走るのは、プリフェッチャがキャッシュを暖かく保つから。 擬似ランダムアクセスパターン(リンクリスト走査、ハッシュテーブル探索)はそれを打ち破る: 検出するストライドがなく、プリフェッチャは助けにならない。 これが同じアルゴリズム複雑度で「キャッシュフレンドリ」データ構造 (配列、struct-of-arrays)が「キャッシュホスタイル」(リンクリスト、ポインタ木)を打ち負かす技術的理由。

TLB について短く

あらゆるメモリアクセスは仮想→物理アドレス変換を通る。TLB(Translation Lookaside Buffer)は最近翻訳されたページテーブルエントリの 小さなキャッシュ(現代の Intel コアで L1 ~64 エントリ、L2 ~1500 エントリ)。 翻訳が TLB をミスすると、CPU は DRAM 内でページテーブルをウォークする —— x86-64 で 4 メモリ読み、それぞれがキャッシュミスになり得る。 TLB は独自の性能崖:TLB のカバー範囲外のページを触るプログラム (デフォルト 4 KB ページでワーキングセット > ~256 MB、または大きなヒープ上の 任意のランダムアクセスパターン)は、実データアクセスではなくページウォークに ほとんどの時間を費やしうる。仮想メモリ primer で深く扱う。

キャッシュは「プログラムのアクセスパターンが不均一」という賭け —— 最近使われた、近くで使われたデータが再びアクセスされる可能性が高い。2 種類の賭け:

時間的局所性(temporal locality)

最近アドレス X を使ったなら、すぐにまた使う可能性が高い。 ループカウンタ、現在のリクエスト構造体、ファイルディスクリプタ表、リストの頭ポインタ —— どれも短時間ウィンドウで繰り返し叩かれる。 キャッシュ置換ポリシー(LRU とその近似)はこれに直接賭ける: 最近使われたものを保持し、触られていないものを追い出す。

時間的局所性を犯すプログラムも動く —— ただキャッシュをミスし続ける。 各反復で 1 つの新しいページを触り再訪しないループは、サイズによらず継続的にキャッシュを フラッシュすることが保証される。これが memset、memcpy、 大きな Bloom フィルタのハッシュ、あらゆる「一度だけスキャン」ワークロードのアクセスパターン。 制約はキャッシュではなく帯域。

空間的局所性(spatial locality)

アドレス X を使ったなら、X の隣のアドレスもすぐ使う可能性が高い。 配列、構造体フィールド、プロトコルヘッダ —— 隣接要素は一緒に触られる。 キャッシュはミスごとに 1 バイトではなく 64 バイトを転送することで利用する。 URL 文字列の 1 バイトを読むと、続く 63 バイトが無料で持ち込まれる; 構造体の最初のフィールドを読むと、通常後続のいくつかのフィールドも読み込まれる。

行列反復 —— 標準的なデモ

2-D C 配列 M[N][N] は行優先で格納される:M[i][j] は メモリ上で M[i][j+1] の隣;M[i+1][j] は N 要素先。for i: for j: の順で反復すると連続アドレスを触る —— 各ミスが次の 64 バイト (~8 double または 16 float)をカバーし、プリフェッチャが始動する。for j: for i: で反復すると各ステップ N 要素ジャンプ —— 各アクセスが別の cache line に着く。

// 行優先(キャッシュフレンドリ)        // 列優先(キャッシュホスタイル)
for (int i = 0; i < N; i++)              for (int j = 0; j < N; j++)
  for (int j = 0; j < N; j++)              for (int i = 0; i < N; i++)
    sum += M[i][j];                          sum += M[i][j];

4096×4096 の double 行列(128 MB)で、間違った順序は通常 5–10 倍遅い —— 実行する命令数は完全に同じにもかかわらず。Fortran はデフォルトで列優先格納で、 同じループが Fortran では逆のキャッシュ挙動を示す。C と Fortran 間の数値コード移植で ループ順を変える理由がドメインエキスパートに見えないことがあるのは、これが理由。

Array-of-Structs vs Struct-of-Arrays

100 万個の粒子があり、各粒子が位置(3 float)、速度(3 float)、色(3 float)を持つとする。 2 つの格納方法:

// Array of Structs(AoS)—— 自然な OOP レイアウト
struct Particle { vec3 pos, vel, color; };
Particle particles[1'000'000];

// Struct of Arrays(SoA)—— SIMD 向け
struct Particles {
    float pos_x[1'000'000], pos_y[1'000'000], pos_z[1'000'000];
    float vel_x[1'000'000], vel_y[1'000'000], vel_z[1'000'000];
    float color_r[1'000'000], color_g[1'000'000], color_b[1'000'000];
};

位置と速度のみ読む更新ステップで、SoA は各 cache line で粒子あたり 6 float のみを持ち込み、 帯域を完全に利用する。AoS は色が必要なくても粒子あたり全 9 float を持ち込む —— 帯域 30% 無駄。 SoA はコンパイラがベクトル化しやすくする(各成分配列を SIMD で処理可能)。 ゲームエンジン、物理シミュレータ、あらゆる機械学習フレームワークの内側ループは、 まさにこの理由で AoS から SoA へ移行する。

キャッシュフレンドリ vs キャッシュホスタイルなデータ構造

• std::vector<T> はほぼあらゆるアクセスパターンでstd::list<T> を打ち負かす —— 多くの操作でアルゴリズム複雑度が同一にもかかわらず。 ベクタの連続格納が空間局所性を自動化し、リストの要素ごとのポインタが各走査ステップを 潜在的に未キャッシュのロードにする。
• B 木はデータベースで二分探索木を打ち負かす —— 各 B 木ノードが 1 個または数個の cache line(またはページ)に収まり、 各比較が 1 個ではなく 64+ キーを一度に持ち込むから。B 木は基本的に「キャッシュ意識のある二分木」。
• ハッシュマップは 償却複雑度が優秀だが、キャッシュ挙動は可変。 オープンアドレッシングハッシュマップ(Robin Hood、swiss テーブル)は実用で チェーニングハッシュマップを打ち負かす —— すべてのエントリが 1 つの連続配列にあり、 チェーニングは衝突ごとにポインタ追跡を必要とする。
• キャッシュオブリビアス・アルゴリズム(再帰的細分化による行列乗算、 van Emde Boas 木、funnel sort)は、キャッシュパラメータを知らずに良いキャッシュ性能を得る —— 作業をあらゆるサイズの片に再帰的に分解することで。 ベースケースは最終的に何らかのキャッシュに収まる、それがどんなサイズであれ。

ワーキングセットの崖

ワーキングセットが何らかのキャッシュ階層に収まる限り性能はスムーズに変化し、 溢れた瞬間に急激に段階的に低下する。32 MB L3 キャッシュのチップで 30 MB ワーキングセットの ワークロードはピーク近くで走る;同じワークロードの 34 MB ワーキングセット版は 各アクセスで DRAM 速度に落ちる。崖が鋭いのは、キャッシュミス率が小さなワーキングセットサイズ範囲で ~0% から ~100% に上がるから。

実践的含意:Linux の perf stat -e cache-misses,LLC-load-missesがホットループがキャッシュに収まるか即座に教える。LLC ミス率が高ければ、 ワーキングセットを縮めるか、アクセスパターンを変えるか、DRAM 律速性能を受け入れるか。

コードレビューの赤旗

• ホット内側ループ内のリンクリスト走査。各ステップが潜在的に未キャッシュの ポインタロード。連続コンテナへ変換するか、コストを受け入れる。
• Array of Structs で済む場所の Array of Pointers(AoP)。std::vector<std::unique_ptr<T>> がstd::vector<T> で動く場所にあると、各アクセスが 1 ではなく 2 cache line になる。
• プローブステップ間の局所性が悪いハッシュマップ。タイトなループ内のチェーニングハッシュマップ;オープンアドレッシング (Robin Hood、swiss テーブル)を検討する。
• ストライドが cache-set サイズの倍数のストライドアクセス。行優先行列で多くの i について M[i][0] を順に アクセスする際、行のバイト数が L1 セットサイズの倍数だと、同じセットを繰り返し打ち、 N ウェイを使い果たす —— 競合ミス。行に cache line 1 本パディングするとパターンを破る。
• LLC サイズをわずかに超えるワーキングセット。必要より 5% 大きい構造体がワーキングセットを崖から押し出せる。 構造体フィールドをパックし、冷たいフィールドを別構造体へ移動するか、可能なら小さい型を使う。