CPUキャッシュ
CPU Cache ・ しーぴーゆーきゃっしゅ
CPUと主記憶の速度差を埋める小容量高速メモリ。局所性を活かすと桁違いに速くなる。
✦ 30秒で試す — 航海CPUは1つ読むとき、頼んでいない隣まで運んでくる同じ64要素を読むのに、列の順は行の順の何倍かかる？予想してみる概要
CPUキャッシュは、CPUと主記憶（RAM）の間に挟まれた小容量・高速なメモリで、メモリ階層の最上段近くを担う存在です。CPUが主記憶からデータを読むには約100ナノ秒かかりますが、これは現代のCPUにとって数百命令ぶんの時間に相当します。そこで「最近使ったデータとその周辺」をCPUのすぐそばに写し取っておき、大半のアクセスを数ナノ秒で済ませるのがキャッシュの仕事です。
ハードウェアが全自動で管理するため、プログラムから直接操作することはできませんし、普段は存在すら意識しません。しかし性能の世界では話が別で、「キャッシュに乗るかどうか」でプログラムの速度は数倍から数十倍変わります。同じアルゴリズム・同じ計算量でも、データの並べ方とアクセスの順序しだいで実行時間が桁で変わる — その分かれ目を握っているのがCPUキャッシュです。
Webアプリのキャッシュ（Redis や CDN）と発想は同じですが、こちらはナノ秒の世界で、ハードウェアに焼き込まれた仕組みという点が異なります。
なぜ生まれたか
1980年代以降、CPUの動作周波数は急速に伸びた一方、主記憶に使われるDRAMのアクセス速度はわずかしか改善しませんでした。両者の差は開き続け、CPUは「1命令を1ナノ秒未満でこなせるのに、データの到着を100ナノ秒待つ」という状態に陥ります。どれだけCPUを速くしても、メモリ待ちで遊んでいては意味がありません。この差は「メモリの壁（memory wall）」と呼ばれました。
速いメモリ素子（SRAM）は存在しましたが、DRAMよりずっと高価で、面積も食うため大容量にできません。そこで「主記憶を全部SRAMにする」のではなく、「小さなSRAMをCPUの隣に置き、使用頻度の高いデータだけを写しておく」という折衷案が採られました。プログラムのメモリアクセスには局所性 — 同じ場所が繰り返し使われる時間的局所性と、近くの場所が続けて使われる空間的局所性 — という偏りがあるため、小さなキャッシュでもヒット率は9割を超えます。メモリ階層の考え方をCPUの内側に持ち込んだこの設計は、ハードウェアが透過的に管理するため既存のプログラムを書き換える必要もなく、すべての現代CPUの標準になりました。
詳細
L1・L2・L3の分担
現代のCPUキャッシュは通常3段構成です。L1は各コア専用で最速（数十KB、約1ナノ秒 = 4〜5サイクル。命令用とデータ用に分かれる）、L2も各コア専用でやや大きい（数百KB〜数MB、約3〜5ナノ秒 = 十数サイクル）、L3は全コア共有で大きい（数十MB、約10〜20ナノ秒 = 数十サイクル）という分担です。CPUはデータが必要になるとL1→L2→L3→主記憶の順に探し、見つかった段から取り寄せます。L1ヒットと主記憶アクセスの差はおよそ100倍。つまり「キャッシュミスを1回減らす」ことは「命令を数百個減らす」ことに匹敵します。数値は世代や製品で変わりますが、「段を1つ下りるごとに数倍遅く、数倍〜数十倍大きくなる」という比は共通です。
キャッシュラインという単位
キャッシュ理解の急所は、データの移動が1バイト単位ではなく「キャッシュライン」（一般に64バイト）というかたまり単位で行われることです。ある1バイトを読むと、その周囲64バイトがまるごとキャッシュに載ります。空間的局所性への賭けであり、続けて隣のデータを読めばタダ同然でヒットします。さらに多くのCPUはプリフェッチャ（アクセスの規則性を見抜いて、次に使いそうなラインを先回りで読んでおく回路）を持ち、順番に読み進めるアクセスをいっそう速くします。
この性質は実務のコードに直接効きます。定番の例が2次元配列の走査です。C や Java、NumPy（既定）では2次元配列は行優先（1行分が連続したメモリ）で置かれるため、行方向にたどれば1ラインの読み込みで連続要素をまとめて処理でき、列方向にたどると毎回別のラインを取りに行ってミスの連続になります。走査の向きを変えるだけで、同じ計算が数倍から10倍以上速くなることは珍しくありません（Fortran や MATLAB は列優先なので向きが逆になります）。
下の部品では、配列のマスを押す・なぞると、その要素を読みます。ミスしたときにラインの4要素がまとめて載る様子と、行の向き・列の向きで読んだ時間の差を確かめてください。
左の配列のマスを押すか、なぞって読んでみてください。まず a[0][0] から右へなぞり、次に下へなぞって、ヒット（緑）とミス（朱）の出方を比べましょう。
同じ理由で、ポインタで散らばったリンクリストより連続配置の配列が速い、よく使うフィールドだけを連続に並べる（構造体の配列より配列の構造体）ほうが速い、といった「キャッシュフレンドリー」なデータ構造の定石も、すべてこのライン単位の読み込みから導かれます。データベースのインデックスにB木のような「ノードを太くして段数を減らす」構造が使われるのも、ディスクとメモリという別の階層で同じ発想を適用した例です。
書き込みと一貫性 — マルチコアの難しさ
読み込みだけでなく書き込みもキャッシュを経由します。すると並行と並列の世界で厄介な問題が生じます。同じデータのコピーが複数コアのキャッシュに存在し得るため、コア1が書き換えた値をコア2の古いコピーとどう整合させるか — これを解決するのがキャッシュコヒーレンスプロトコル（MESI など）で、あるコアが書き込むと他コアの同じラインを無効化して一貫性を保ちます。
ここから生まれる有名な性能バグが「偽共有（false sharing）」です。2つのスレッドがそれぞれ別の変数を更新しているだけなのに、その2変数がたまたま同じ64バイトのラインに同居していると、書き込みのたびに互いのキャッシュを無効化し合い、まるで同じ変数を取り合っているかのように遅くなります。論理的には競合ゼロなのに数倍遅くなるため原因に気づきにくく、スレッドごとのカウンタをライン境界まで詰め物（パディング）をして分離する、といった対策が定番です。
実務での構え方
CPUキャッシュの最適化が本当に必要になるのは、数値計算・ゲーム・データベースエンジンのような性能が勝負の領域が中心です。とはいえ「メモリは連続に、アクセスは順番に」という原則を知っているだけで、日常のコードでも不利な選択を自然に避けられます。そして大切なのは、推測ではなく計測で確かめることです。プロファイラやCPUのパフォーマンスカウンタ（Linux の perf など）でキャッシュミス率を測れば、ボトルネックが計算なのかメモリ待ちなのかを切り分けられます。「速いはず」の最適化がキャッシュを乱して逆効果になることもある — ナノ秒の世界でも、監視と同じく計測が最後の審判です。
試問
8×8 の配列 a[行][列] のマスを押すか、指でなぞると、その要素を読みます。キャッシュになければ主記憶から約100nsかけて運び（ミス）、あれば約1nsで読めます（ヒット）。配列はメモリ上で行ごとに1列につながって並び、キャッシュには4要素ずつの囲みが4つまでしか載りません。
配列のマスを押すか、なぞって読んでください。読むたびに、ヒット（緑）かミス（朱）かが分かります。