メモリ階層 基礎

我々の curl プロセスは URL 文字列をメモリのどこかに持つ。先頭バイトを読むのは命令 1 つで、どの段が応答しても命令は同じ。変わるのは待ち時間だけだ。数値はすべて 1 台の機械： 3.2 GHz の Intel Golden Cove コア、48 KB L1d、1.25 MB L2、30 MB L3、デュアルチャネル DDR5-6400。

そのバイトを保持しうる場所は 7 つあり、どれが応答するかがすべてを決める。スライダを段に沿って下げてみてほしい ——応答する段の横のバーが対数軸のレイテンシで、読み出しは同じ数値をサイクルで示す：

開きが実際にどこにあるかに注目してほしい。チップ内部の 4 段は 0.31 ns から 15.6 ns —— コア全体で 50 倍にすぎない。そこから DRAM へ 1 歩、ストレージへさらに大きな 1 歩。L1 ヒットを 1 秒に伸ばせば、DRAM は 50 秒先、ディスクは 72 日先になる。

階層を 1 段下がるごとに約 100 倍、という俗説がある。復唱するより照合する価値がある：速いほうの段と遅いほうの段を 2 本のスライダに置き、そのあいだの倍率を読む：

俗説はチップ内部では大きすぎ、チップの外では小さすぎる。 L2 / L1 は 2.9 倍、L3 / L2 は 3.3 倍、DRAM / L3は 5.1 倍 —— なだらかな坂だ。ところがDRAM から SSD は 1 歩で 1,250 倍。これは階段ではなく、末端に崖のある坂である。

レイテンシは、それが押しのける仕事の隣に置いて初めて意味を持つ。ロードが未完了のあいだもコアは見つかる命令を発行し続け、埋められなかった発行スロットこそが本当の請求書だ。ロードのレイテンシをドラッグして、スロットが消えるのを見てほしい：

80 ns でコアは 256 サイクル、1 サイクル 3 命令として 768 スロットを焼く。アウトオブオーダ実行が回収できるのはスケジューリングウィンドウにたまたま入っている独立な仕事だけ —— 数十命令であって 800 命令ではない。メモリ律速のループが IPC 1 を割る一方、同じコアが既に手元にあるデータでは 3 を維持するのはこのためだ。

コアはミスを 1 件ずつ待つわけではない。ラインフィルバッファが 10 本あるので最大 10 件のミスを同時に抱えられる。リトルの法則はその本数をそのまま帯域に変える。同時発行数を上げてみてほしい：

64 バイトのミス 10 件を 80 ns ごとに 1 束、で8.0 GB/s —— DDR5-6400 2 チャネルが出せる量の 7.8% にすぎない。 1 コアではこの機械のメモリ系を飽和できず、十数コアを要する。この非対称性が、シングルスレッドのマイクロベンチと負荷のかかったサーバとでメモリの値段の答えが食い違う理由である。

しかも食い違う方向を誰も想定していない。コア群が合わせてチャネルが供給できるピークに近づくと、要求が互いの後ろに並び始め、各コアが見るレイテンシは定数でなくなる：

曲線がバスの飽和よりずっと手前で 80 ns の線を離れるのを見てほしい。ピークの 80% で待ちは 160 ns、95% で 460 ns。どのレイテンシ表に載っている数値もアイドルの数値であり、静かな機械で測ったものであって、本番を説明する見込みが最も低い数値である。

正直なコストは「80 ns」ではない。このページの残りは、それを払わずに済ませる話である。

人がまず持ち出す説明は光速だが、それは誤りだ。信号は銅の中をおよそ 15 cm/ns で進むので、距離は確かに下限を与える —— 責める前に測る価値がある。

メモリブロックを ALU から引き離してほしい。目盛りはダイの端、パッケージの端、そして基板の反対側の DIMM スロット。読み出しは距離だけで生じる往復時間だ：

それがいかに小さいかに注目してほしい。60 mm の往復で 0.80 ns —— 2.6 サイクルである。DRAM の応答は 80 ns、その 100 倍だ。距離は下限を定めるだけで、残りの待ちはメモリアレイそのものの中で起きている。

2 つの技術が分かれるのはそこだ。SRAM セルはラッチに組んだ 6 トランジスタで、自分の状態を自分で保つ。DRAM セルは 1 トランジスタと 1 キャパシタで、そのキャパシタの電荷は漏れていく。最後のリフレッシュから時間を進めてみてほしい：

64 ms を越えると電荷はセンス閾値を下回り、ビットは失われる。だから DDR4 はこの窓の内に全行をリフレッシュする —— 8,192 回、7.8 µs に 1 回。読み出し自体もセルを空にするので、読みのたびに書き戻しが続く。配線ではなくこの手順が 80 ns の正体である。

その脆さと引き換えに得られるのが密度で、密度とは価格のことだ。 1 ビットは SRAM で 6 トランジスタ、DRAM で 1 個と少し。この差はサプライチェーン全体で複利になる。欲しい容量を上げて、どの行が買えるまま残るか見てほしい：

1 TB ではディスクが $15、SRAM が $409,600 —— 同じバイト数で 26,667 倍。 1 TB のキャッシュ級 SRAM を積んだ機械は遅くも熱くもない。単に、誰も買わない製品というだけだ。

仮に金が無料でも、やはり作れない。アレイは大きいほど遅いからだ —— ワード線は長くなり、センスアンプは増え、デコーダは深くなる。キャッシュの容量を上げて、曲線からアクセスレイテンシを読んでほしい：

曲線がこのコアの3 つの実測点を通るのを見てほしい。 1 MB の L1 は応答に 14.6 サイクルかかる —— L2 が既に要している値だ。大きくて速いキャッシュというものは存在しない。作れば、それは名前を間違えた次の段でしかない。

こうして段は積まれ、積むこと自体が問いを生む：ラインが L2 にあるとき、L3 はコピーを保持するのか。ポリシーを切り替え、コア数を動かしてほしい ——この積みが保持できる量と、重複に費やす量の対比だ：

インクルーシブな L3 はコヒーレンスを安くする。L3 で外れたスヌープはその上のどの L2 でも外れることが保証されるからだ。代金は容量 —— 8 コアなら30 MB の L3 のうち 10 MB がコピーだけを保持する。エクスクルーシブは 40 MB を得るかわりに同報を要する。

64 バイトは Pentium 4 以来の x86 のライン長で、Arm の Cortex と Neoverse も同じ —— このテープが描いているのはその 64 だ。

テープに沿って読んでいるワードをドラッグしてほしい。 1 マスは 8 バイトのワード、上の括弧はそれを含むライン、枠だけのマスは招かれずについてくるバイトである：

動かしてもコストが変わらないことに注目してほしい。隣のワードでもトランザクションは同じ 64 バイト、同じ 80 ns。決められるのは、そのうちどれだけ使うかだけだ。

その 64 は普遍ではなく、詰め物をする瞬間にそれが効く。 IBM POWER と Apple silicon は 128 バイト動かす。sysctl hw.cachelinesize は M シリーズの Mac で 128、隣の Intel Mac で 64 と答える。ラインの取り合いを避けようと構造体を 64 バイトに詰めても、機械の半分では何も買えていない —— HotSpot が @Contended を 128 バイトに詰めるのもそのためだ。どちらの数字も、有効バイトあたりのタグと誰も求めないデータのあいだの同じ妥協だ。

ストライドでメモリを歩くループは、その比率を直接決める。要素間のストライドを設定してゲージを読んでほしい —— 取ってきた各ラインのうち、プログラムが実際に触る割合だ：

ストライドが 64 バイトに達した途端、4 バイトの要素はそれぞれ自分のラインを占める。64 バイトのうち 4 バイトを使用、6.3%、同じ答えに 16 倍のメモリトラフィックだ。128 を越えても悪化は止まる。 1 要素 1 ラインが床だからである。

ラインがどのスロットに落ちるかはアドレス自身が決める。 3 つのフィールドに切るだけで、シフトとマスク以外の算術はない。アドレスをドラッグし、容量を変えてindex と tag の境目が動くのを見てほしい：

下位 6 ビットは offset —— ライン内の何バイト目か —— でキャッシュには届かない。続くビットが index で、セットを選ぶのはこれだけだ。そのビットが一致する 2 つのアドレスは、メモリ上でどれだけ離れていても同じセットを奪い合う。

1 セットは複数のラインを保持でき、その本数が連想度である。ここでは 8 本のホットラインが同じセットに index し、ループがそれらを巡回する。セットあたりのウェイ数を上げてほしい：

ミス率が坂ではなく崖で落ちるのを見てほしい。7 ウェイでは毎周、ループが次に欲しがるラインをちょうど追い出す。8 ウェイで8 本すべてが常駐し、ミス率は 0 になる。問題は容量ではない —— このセットはバイトでは一度も満杯でなく、ウェイでだけ満杯だったのだ。

その崖の裏にはポリシーがある。セットが満杯なら何かを出さねばならず、その選び方こそが「収まるワーキングセット」と「スラッシングするワーキングセット」の分かれ目だ。ポリシーを切り替え、ウェイ数より 1 本多いホットラインを置いてほしい：

8 ウェイに 9 本置くと、LRU はすべてのアクセスで外す —— 巡回の次に来るラインを毎回追い出すからだ。FIFO も同じ。そこまで不運が続かないランダムは 23% で済む。

実際のキャッシュはどちらも使わない。厳密な LRU 順は log₂(N!) ビット要るので、ハードはビットの木で近似する —— 病理は緩和されるが消えはしない。

時間的な半分には測れる形がある —— 再利用距離、同じラインの 2 回の使用のあいだに触れた相異なるライン数だ。容量 C のキャッシュは距離 C 未満だけをヒットに変える。

下は 96 アクセスのトレースの距離ヒストグラムである。容量の切れ目を右へドラッグしてほしい —— 左はヒット、右はミス、端の列は各ラインの初回参照だ：

見返りの不均一さに注目してほしい。最初の 4 ライン分の容量でアクセスの 44% が取れる。12 から 16 に増やしても何も取れない。その範囲に何も残っていないからだ。キャッシュ容量は膝のある曲線であり、膝はハードウェアではなくプログラムの性質である。

空間的な半分は、ループがメモリを訪れる順序が決める。C の配列 M[N][N] は M[i][j] を M[i][j+1] の隣に置く。ここでは 1 行がちょうど 1 ラインだ。走査を進め、それから反復順序を切り替えてほしい：

左のライン列を見てほしい。行優先なら 8 要素で 1 ライン、列優先なら同じ 8 要素で 8 ライン。4096×4096 の double 行列では 2,097,152 対 16,777,216 —— まったく同じ算術に 8 倍のトラフィックだ。 Fortran は列優先で格納するので、同じループの入れ子があちらでは正しくこちらでは誤りになる。

同じ議論はレコードの内部にも当てはまる。位置・速度・色を持つ粒子は 9 個の float で、位置と速度を読む更新ステップに要るのはそのうち 6 個だ。ループが読むフィールド数を動かし、レイアウトを切り替えてほしい：

ループが 9 個すべてを読まなくなった瞬間、構造体配列は粒子あたり 36 バイトを動かして 24 バイトしか使わず、帯域の 3 分の 1 が誰も求めない色に費やされる。配列構造体は読む分だけを動かし、各フィールド配列はギャザーなしでベクトル化される。

2 つの効果は 1 本の曲線に合流する。下では同じ領域を 2 通りに歩く —— 1 度はアドレス順に、1 度はその領域内を指す依存ポインタの鎖として。領域の大きさを 4 KB から 1 GB へ動かしてほしい：

逐次スイープはほとんど動かない。 16 要素が 1 ラインを共有し、10 ラインが同時に飛んでいるので、どこでも要素あたり 1 ns を切る。追跡は 1 GB で 1 歩 103 ns —— 211 倍 —— まで登る。命令数は同じである。

逐次の曲線が平らなのはハードウェアが助けているからだ。連続 2 ラインでストリームプリフェッチャが食いつき、プログラムの 8 ライン先へロードを出す。テープに沿って読みをドラッグし、走査をランダム順に切り替えてほしい：

逐次では読みの前方のラインが既に飛んでいて、デマンドロードはヒットする。ランダムでは検出すべきストライドがなく、ストリームは形成されず、毎回 80 ns を丸ごと払う。漸近計算量が同じでも vector が連結リストに勝つ機械的な理由がこれだ。

だから探索構造で最適化すべきは深さではなく分岐数になる。二分木は 1 段につき 1 ライン。B 木のノードはライン 1 本やページ 1 枚を埋め尽くし、その全体を比較する。ノードサイズとキーの数を設定してほしい：

4 KB のノードと 16 バイトのキーなら分岐数は 256 なので、10 億キーでも30 段ではなく4 回で届く。どちらも O(log n) だが、対数の底を決めるのは転送単位である。

まず階層全体が拠って立つ不変条件から。あらゆるアクセスで、ラインはいずれかの段が保持し、コストは保持する最小の段のレイテンシに等しい。ミス率とはその段がどれかの分布にすぎない。

W バイトのワーキングセット上の一様ランダムアクセスでは、 W が C を超えたあと容量 C のキャッシュのヒット率はちょうど C/W になる。ワーキングセットを 3 つの容量にまたいでドラッグし、曲線から平均を読んでほしい：

30 MB —— ちょうど L3 —— で平均アクセスは 15.1 ns。60 MB では 47.6 ns。プログラムは何も変わっていない。同じループ、同じ命令数、3 倍の実時間だ。これがワーキングセットの崖であり、唯一の警告はこの数値そのものである。

曲線は魔法ではなく、入れ子になった 1 本の式だ。平均メモリアクセス時間は L1 のヒット時間、それに外れた割合ぶんの L2 の時間、さらに外れた割合ぶんの L3 の時間、と続く。L1 のミス率とL3 のミス率をドラッグしてほしい：

どの項も上位のミス率を掛けられるので、いちばん深い項がいちばん効く。1000 アクセスあたり L1 ミス 30 のとき、L3 のミス率を 20% から 40% にすると、平均は 2.1 ns から 2.3 ns へ —— すべてのアクセスで、である。推測せず LLC-load-misses を測れという主張の中身はこれで全部だ。

同じ壊れ方をする第 2 のキャッシュがあり、こちらのほうが見落としやすい。あらゆるアクセスは変換も受けており、TLB はその変換を蓄える —— このコアでは 1,536 エントリだ。ワーキングセットを動かし、それからページサイズを変えてほしい：

4 KB ページなら到達範囲は 6 MB —— 俗説の 256 MB ではない —— なので 30 MB のワーキングセットはアクセスの 80%を、データ参照が始まる前にページウォークへ送り込む。 2 MB ページに切り替えれば到達範囲は 512 倍になり、ワーキングセット全体が中に収まる。

最後の崖は優秀な技術者を捕まえる。コードが正しく見えるからだ。行間隔がちょうど 2 の冪の行列を 1 列下ると、どの行も同じセットに落ちる。1 行あたりのパディングを 0 から動かしてほしい：

パディング 0 では 64 行すべてが 8 ウェイの 1 セットに index し、1 周ごとに全部を取り直す。1 行 1 ライン分のパディングで走査は64 セット全部に散り、ミスは 0 になる。配列は 1.6% 大きいだけだ。

double M[512][512];      /* 行間 4096 B：全 */
                         /* M[i][0] が set 0 に */

double M[512][512 + 8];  /* +64 B：列が 64 */
                         /* セット全部を覆う */

3 つとも自ら名乗らない。例外もログも表明の失敗もなく、正しい答えが 20 倍の時間で返るだけだ。

48 KB 以下なら答えは L1 で平均 1.6 ns。 30 MB を越えるとDRAM が過半を応答し、平均は 80 へ向かう。読むべきは端点ではなく割合だ —— DRAM の応答が数パーセントを越えた瞬間、その項が平均を支配し、残りは丸め誤差になる。

どれも同じ取引の衣装違いだ。ループが読まないものが、読むものに相乗りしている。連結リストは8 バイトのために 64 バイトを動かし、ポインタ配列は 1 オブジェクトに 2 ライン、チェイン法は 1 探索に 1 ライン払う。

4 つめはバイト数が正しいためレビューで見えない。コードを変える前に perf stat -e cache-misses,LLC-load-misses,dTLB-load-misses で確かめ、変えたあともう一度測ってほしい。