キャッシュ最適化とは（全体像）
CPUは、メモリから毎回データを取りにいくと遅い。そこで、よく使うデータをCPUのすぐそばの高速メモリ（キャッシュ）に置いておく。このキャッシュをうまく当てるように書くのが、キャッシュ最適化だ。
身近にたとえると、机の上によく使う本を置くのと同じ。毎回書庫まで取りにいかず、手元（キャッシュ）にあれば一瞬で使える。
押さえるのは、キャッシュが効きやすいデータの使い方には2つの傾向（局所性）があること。これを意識すると、同じ処理でも大きく速くなる。
詳しく：2つの局所性と配列の並び順だけ覚えれば戦える
ここが記事の心臓部。まず2つの局所性を見ましょう。
2つの局所性
| 種類 | 意味 | 例 |
|---|---|---|
| 時間的局所性 | 最近使ったデータは、またすぐ使われやすい | ループの中で何度も使う変数 |
| 空間的局所性 | 使ったデータの「近く」もすぐ使われやすい | 配列を端から順にたどる |
この2つに沿って書くと、キャッシュがよく当たる。とくに空間的局所性で大事なのが、配列の並び順だ。
配列の並び順は言語で違う
| 言語 | メモリ上の並び | 速いたどり方 |
|---|---|---|
| C／C++／Python(NumPy) | 行優先（横方向に連続） | 外側＝行、内側＝列 |
| Fortran／MATLAB | 列優先（縦方向に連続） | 外側＝列、内側＝行 |
ここで一番のひっかけが「CもFortranも並び順は同じ」という誤解。Cは行優先、Fortranは列優先で逆。並びと逆向きにたどるとキャッシュが外れ続けて、何倍も遅くなることがある。
もう1つの要点がキャッシュライン。メモリとキャッシュの間は、1バイトずつではなくまとまった単位（典型64バイト）でやりとりする。だから、近くのデータを一緒に使う書き方（空間的局所性）が有利になる。
なお、複数のCPUコアが同じキャッシュライン上の別の変数を書き換え合うと、おたがいのキャッシュが無効になって急に遅くなるフォルスシェアリングという落とし穴もある。
わかりやすく言い換えると
要するに、机と本でイメージするとラクです。
①時間的局所性 … よく使う本を手元に置いておく（また使うから）
②空間的局所性 … 関連する本を隣に並べる（次に近くを開くから）
③キャッシュライン … 一度に持ってこられるのは「64ページ分」みたいなまとまり
つまり、「局所性に沿って書く」「並び順は言語で違う（C行・Fortran列）」、この2点が試験の急所です。
試験のツボ
🔴 一番出る：2つの局所性
①時間的局所性＝最近使ったデータはまたすぐ使われる
②空間的局所性＝使ったデータの近くもすぐ使われる
🔴 次に出る：配列の並び順（言語差）
①Cは行優先（横に連続）・Fortranは列優先（縦に連続）
②並びと逆向きにたどるとキャッシュが外れて遅くなる
🟡 押さえると安定：キャッシュラインとフォルスシェアリング
①メモリとキャッシュは「キャッシュライン（典型64バイト）」単位でやりとり
②別コアが同じライン上の変数を書き換え合うと遅くなる（フォルスシェアリング）
よくある間違い
①「CもFortranも配列の並び順は同じである」→ ✗ Cは行優先、Fortranは列優先で逆。逆向きにたどると遅くなる。
②「キャッシュは1バイトずつメモリとやりとりする」→ ✗ まとまった単位（キャッシュライン・典型64バイト）でやりとりする。
③「局所性は性能に関係ないので気にしなくてよい」→ ✗ 局所性はキャッシュ効率＝性能の根幹。意識する書き方で大きく速くなる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（2つの局所性）
局所性に関する次の記述のうち、正しいものはどれか。
- 時間的局所性は画面の表示時間のことで、データのアクセスとは無関係だとされているものである
- 局所性とはデータを必ず1か所にまとめる決まりのことを指すものだとされている
- 局所性はプログラムの行数を数える方法のことで、キャッシュとは関係がないものだとされている
- 時間的局所性は最近使ったデータの再利用、空間的局所性は近くのデータを使う傾向のことである
解答は 4 ですよ。
時間的局所性は、最近使ったデータがまたすぐ使われる傾向。空間的局所性は、使ったデータの近くもすぐ使われる傾向ですね。この2つに沿って書くとキャッシュがよく当たります。
選択肢1の「画面の表示時間」、選択肢2の「1か所にまとめる決まり」、選択肢3の「行数を数える方法」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 画面の表示時間ではない |
| 2 | ✗ | まとめる決まりではない |
| 3 | ✗ | 行数を数える方法ではない |
| 4 | ✓ | 時間的＝再利用・空間的＝近くの利用 |
オリジナル問題2（配列の並び順）
配列のメモリ上の並び順に関する次の記述のうち、正しいものはどれか。
- CもFortranもまったく同じ並び順で、どちらの言語でも走査順は気にしなくてよいとされる
- Cは行優先、Fortranは列優先で並びが逆になり、並びに合わせてたどると速くなるとされる
- Cは列優先、Fortranは行優先で、Cでは縦方向にたどるのが必ず速いものだとされている
- 配列の並び順はどの言語でも毎回ランダムに決まり、決まった規則はないものだとされている
解答は 2 ですよ。
Cは行優先（横に連続）、Fortranは列優先（縦に連続）で、並びが逆ですね。並びに合わせてたどるとキャッシュがよく当たり、速くなります。逆向きだと外れ続けて遅くなります。
選択肢1の「同じ並び」、選択肢3の「CとFortranが逆」、選択肢4の「毎回ランダム」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 並び順は言語で違う |
| 2 | ✓ | C行優先・Fortran列優先で合わせる |
| 3 | ✗ | Cが行優先・Fortranが列優先 |
| 4 | ✗ | ランダムではなく規則がある |
オリジナル問題3（キャッシュライン）
キャッシュラインに関する次の記述のうち、正しいものはどれか。
- キャッシュは1バイトずつメモリとやりとりし、まとめて運ぶことはないものだとされている
- キャッシュラインは画面に引く線のことで、メモリの転送とは無関係なものだとされている
- キャッシュラインはメモリとキャッシュの最小転送単位で、典型は64バイトのまとまりである
- キャッシュラインはデータを必ず消す機能のことで、転送の単位とは関係がないものだとされる
解答は 3 ですよ。
キャッシュラインは、メモリとキャッシュの間でやりとりする最小の単位で、典型は64バイトのまとまりですね。1バイト読むつもりでも、近くの64バイトがまとめて運ばれます。だから近くのデータを一緒に使う書き方が有利です。
選択肢1の「1バイトずつ」、選択肢2の「画面に引く線」、選択肢4の「データを消す機能」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | まとまった単位で運ぶ |
| 2 | ✗ | 画面の線ではない |
| 3 | ✓ | 最小転送単位・典型64バイト |
| 4 | ✗ | データを消す機能ではない |
まとめ
押さえどころ
- 🔴 2つの局所性 ＝ 時間的（最近使ったデータの再利用）と空間的（近くのデータの利用）。これに沿うとキャッシュが当たる。
- 🔴 配列の並び順 ＝ Cは行優先、Fortranは列優先。並びに合わせてたどると速い（逆だと遅い）。
- 🟡 キャッシュラインとフォルスシェアリング ＝ 転送は64バイト単位。別コアが同じライン上の変数を書き換え合うと遅くなる。
次に学ぶ
- キャッシュメモリ詳細 ── キャッシュの階層やヒット率など、キャッシュそのもののしくみ。
- メモリ割当戦略 ── メモリのどこを使うか決めるやり方。データ配置の理解につながる。
執筆: SikakuQuest編集部