回 3-3 道 3 コンピュータの中
キャッシュメモリは、間に置く、小さくて速い記憶の置き場です。最近使ったデータとその近くのデータを行 (ライン) という塊で控えておき、次に同じ所を読むときは主記憶まで行かずに済ませます。Norvig の表では L1 読むのに 0.5 ナノ秒、主記憶から読むのに 100 ナノ秒で、当たるかどうかで 200 倍の差があります。
読む速さの差がどこで生まれ、どんな順に読めば当たるのかを切り分けられるようになります。
文 ゆめさくコード編集部 公開 2026年10月27日 更新 2026年10月27日 出典を確かめた日 2026年10月27日
なぜ CPU は キャッシュメモリは、速い 済むように、よく使うデータを CPU の近くに控えておく小さな置き場です。
8 行 8 列の表に入った 64 個 の数を、全部足すとします。1 行 目を左から右へ読み、次に 2 行 目へ進む読み方と、1 列目を上から下へ読み、次に 2 列目へ進む読み方があります。足し算の回数は同じでも、読む順番で速さが変わることがあります。
理由は、計算をする CPU と、データを置く主記憶 (メインメモリ、作業中のデータを広げておく机) の間に、速さの大きな差があるからです。
Red Hat の Ulrich Drepper は、2007 年 の論文の冒頭で、多くのプログラムの速さを縛っているのは今やメモリを読む速さだと書いています。そこで CPU の近くに、小さくて速い控えの置き場を作りました。これがキャッシュメモリです。この回の終わりには、上の 2 つ の読み方のどちらがなぜ速いのかを、数で説明できるようになります。
メモリの 記憶の置き場は、速くて小さい物から遅くて大きい物へ、段のように並んでいます。まず一番近い段を見て、無ければ 1 段 ずつ下へ取りに行きます。
速い CPU に近い段から順に、レジスタ (CPU の中で計算中の値を持つ所)、L1 L3 キャッシュ、並びます。L は Level (段) の頭文字で、L1 が一番 CPU に近く、一番速くて一番小さい段です。
読むのにかかる時間の目安を、2 つ の一次資料から並べます。Norvig の表は「よくある PC」の目安をナノ秒 (10 億分の 1 秒 ) で書いた物です。Drepper の表は、Intel が Pentium M という古い CPU について示した数を、CPU の 1 拍 (サイクル) の数で書いた物です。
段 Norvig の Drepper の レジスタ 載っていない 1 以下 L1 キャッシュ 0.5 約 3 L2 キャッシュ 7 約 14 L3 キャッシュ 載っていない 載っていない 主記憶 100 約 240 ディスク (読む場所を移す) 8,000,000 載っていない
どちらの表でも、主記憶は L1 より 2 桁ほど遅く、ディスクは主記憶よりさらに何桁も遅くなります。今の CPU の値はこれと同じではありませんが、段が下がるごとに桁で遅くなる形は同じです。
下の図で扱うデータを大きくすると、置き場が下の段へ落ちていきます。図の時間は桁の感じをつかむための目安で、上の表の値とは別物です。
速い段を大きく作らないのは、値段のためです。キャッシュには SRAM (電気を流している間、値を保ち続ける記憶の部品)、主記憶には DRAM (小さな電気の溜まりで値を持ち、ときどき入れ直す部品) を使います。Drepper は、すべてを SRAM にしない理由は費用で、SRAM はずっと高いと書いています。
局所性、 キャッシュが役に立つのは、プログラムの読み方に局所性 (使う場所が近くにかたまる性質) があるからです。局所性には 2 つ あります。
種類 意味 よくある場面 時間の局所性 最近使った ループの 空間の局所性 使った 配列を
キャッシュは、この 2 つ の性質に賭けた仕組みです。
当たりと CPU が読みたいデータがキャッシュにあることを当たり (ヒット)、無いことを外れ (ミス) と呼びます。当たれば近くの段からすぐ渡せます。外れれば下の段まで取りに行き、取ってきた物をキャッシュに置いてから渡します。
キャッシュは、1 つ の数だけを取ってくるのではなく、そのまわりを含む行 (ライン、まとめて運ぶ塊) を単位にして運びます。Drepper によると、昔の行は 32 バイトで、2007 年 の時点では 64 バイトが普通でした。1 つ 目の数で外れても、同じ行に入っている隣の数は当たりになります。空間の局所性を活かす作りです。
いっぱいの キャッシュは小さいので、すぐいっぱいになります。新しい行を置くには、どれかを追い出します。Drepper は、多くのキャッシュは一番長く使われていない物 (LRU、Least Recently Used) から追い出すと書いています。時間の局所性があるなら、長く使っていない物ほど、この先も使われにくいからです。
書き込みにも 2 つ のやり方があります。
やり方 書いたとき 良い所と弱い所 ライトスルー すぐ 作りは ライトバック キャッシュの 速い。
主記憶の 主記憶の下にも段があります。仮想メモリ (プログラムに、本当より広い番地の空間を見せる 仕組み) は、番地をページ (決まった大きさの区画) に分け、使っている所だけを主記憶に載せます。載っていない所を触ると、OS がディスクから運んできます。
考え方はキャッシュと同じですが、ディスクは主記憶より何桁も遅いので、ページの出し入れが続くと、プログラム全体が目に見えて遅くなります。下の図は 1 ページ を 4KB として、触ったページの数と追い出しの回数を数えます。
動かして確かめる 作り、表の読み方で当たりの数がどう変わるかを数えます。模型の決まりは次の通りです。
番地は 0 から始まる数で、8 つ ずつが 1 つ の行になる (0〜7 が行 0、8〜15 が行 1) キャッシュに置ける行は 4 本 で、どの行もどこにでも置ける いっぱいなら、一番長く使っていない行を追い出す (LRU) 行の大きさも本数も、本物の 小さくした模型です。
1 まず、読んだ番地ごとに、当たりか外れかを 1 行 ずつ出します。
動かす 1 回ずつ当たりと外れを見る
実行すると、次の通りに出ます
0 0 外れ
1 0 当たり
2 0 当たり
9 1 外れ
17 2 外れ
25 3 外れ
3 0 当たり
33 4 外れ
出す 1
9 1 外れ
出す 2各行は、読んだ番地、行の番号、結果です。「出す」の後ろは追い出した行の番号です。
番地 0 で外れると、行 0 (番地 0〜7) がまとめて載るので、続く 1 と 2 は当たりです。これが空間の局所性です。番地 3 は 4 回 前に読んだ行 0 に入るので当たり、時間の局所性です。番地 33 のとき 4 本 が埋まっていて、一番長く使っていない行 1 を追い出しました。行 0 は直前に番地 3 で使ったので残っています。最後に番地 9 を読み直すと、行 1 はもう追い出されているので外れです。
表を 次に、冒頭の 8 行 8 列の表を 2 つ の順に読み、64 回 のうち何回当たるかを数えます。表は 1 行 目の 8 個 、2 行 目の 8 個 と、行の順に番地を並べて置いてあるとします。
動かす 読む順で当たりの数を比べる
実行すると、次の通りに出ます
行の順 56
列の順 0行の順では 64 回 のうち 56 回 当たりました。外れは各行の最初の 1 回 ずつで、1 つ 外れるたびに 8 個 が載り、残りの 7 個 が当たります。
列の順では 1 回 も当たりません。0 になったのには 2 つ の条件がそろっています。1 つ は、次に読む番地が 8 つ 先で、行の大きさと同じだけ飛ぶので、毎回別の行を読むことです。もう 1 つ は、1 列を読み終えるまでに 8 本 の行を触るのに、キャッシュには 4 本 しか置けないことです。2 列目に移って行 0 に戻るころには、行 0 はもう追い出されています。
平均で 当たりの割合 (ヒット率) から、1 回 読むのに平均で何ナノ秒待つかを見積もります。見積もりの置き方は次の通りです。
当たりは L1 から読むとして、Norvig の表の 0.5 ナノ秒 外れは読むとして、Norvig の表の 100 ナノ秒 (L2 と L3 は考えない) 当たりの数は、上の模型の 56 回 と 0 回 (どちらも 64 回 中) 動かす 平均の待ち時間を見積もる
実行すると、次の通りに出ます
行の順 12.9375
列の順 100.0
差の倍率 200.0行の順なら 1 回 あたり約 13 ナノ秒、列の順なら 100 ナノ秒です。1 回 ずつの差が 200 倍あるので、ヒット率が少し下がるだけで平均は大きく動きます。模型の上の見積もりで、測った時間ではありません。
キャッシュが 最近の所をまた使う」という前提に賭けています。前提が崩れると、キャッシュがあっても毎回下の段まで取りに行くことになります。
使う 何本かの行をくり返し読むとします。読む行の本数がキャッシュに置ける本数を超えたとき、何が起きるかを数えます。
動かす 置ける本数を 1 本超えると
実行すると、次の通りに出ます
3 本を 10 周 27 / 30
4 本を 10 周 36 / 40
5 本を 10 周 0 / 50
8 本を 10 周 0 / 803 本 と 4 本 では、外れは 1 周目の最初の数回だけで、2 周目からは全部当たります。ところが 5 本 にすると、当たりが 0 になりました。4 本 しか置けないところに 5 本 目を載せると、一番長く使っていない行、つまり次にすぐ使う行を追い出してしまうからです。追い出した行を次に読むときにはまた外れ、その行を載せるためにまた次の行を追い出す、が続きます。
1 本 増えただけで、9 割当たっていたのが 0 になりました。この 0 は、どの行もどこにでも置けて LRU で追い出す、この模型での結果です。本物のキャッシュは置き場所の決め方や追い出し方が違うので、同じ数にはなりません。
崩れる前提をまとめると、次の通りです。
使う範囲はキャッシュに収まる、という前提。超えると、LRU では次に使う物から追い出すことがある 次に読むのは近くの番地、という前提。行の大きさ以上に飛んで読むと、行にまとめて載せた残りが無駄になる (列の順の 0) 載る、という前提。載らないとページの出し入れが始まり、ディスクの遅さがそのまま効く 仕事で 仕事では、まず自分の機械の調べ、次に読む順番を疑い、最後に直す前と後の速さを同じ条件で比べます。
1 つ 目は、行の大きさを決め打ちしないことです。Drepper の 2007 年 の資料は 64 バイトを普通としていますが、手元の機械が答える値は違うことがあります。下は、Apple M3 Pro の Mac (macOS 26.3.1) で sysctl を動かした結果です。
手元の Mac で sysctl を動かした結果
$ sysctl hw.cachelinesize
hw.cachelinesize: 128
$ sysctl hw.l1dcachesize
hw.l1dcachesize: 65536
$ sysctl hw.l2cachesize
hw.l2cachesize: 4194304
$ sysctl hw.pagesize
hw.pagesize: 16384この Mac は、行の大きさを 128 バイト、L1 のデータ用のキャッシュを 65536 バイト、L2 を 4194304 バイト、ページを 16384 バイトと答えました。ページの図は 4KB で描いていますが、この Mac のページはその 4 倍です。
2 つ 目は、大きな表を回す読む順番が置かれた順番と合っているかを見ることです。2 重のループの内と外を入れ替えるだけで、列の順が行の順になります。
3 つ 目は、直す前と後の時間を、同じデータと同じ機械で並べて比べることです。模型は考える助けで、本物の速さは測って確かめます。
関わる実例 外れの時間の差は、速さの話だけでなく、守りの穴にもなりました。
Meltdown と Google の Project Zero の Jann Horn は、2017 年 6 月 1 日 に Intel、AMD、ARM へ知らせ、2018 年 1 月 に公表しました。記事は、CPU のデータのキャッシュにかかる時間を悪用すると、本来は読めないはずの漏らせると書いています。同じ時期に、Meltdown の論文が 2018 年 1 月 3 日 に arXiv に出ました。論文によると、Meltdown は普通のプログラムから 中のメモリ (含む) を読めます。番号は、Meltdown が CVE-2017-5754、Spectre が CVE-2017-5753 と CVE-2017-5715 です。
崩れた前提は「キャッシュに当たったか外れたかは、外から見えない」です。当たれば速く、外れれば遅い。その時間の差を測れば、どの行がキャッシュに載ったかが分かり、そこから中身を割り出せました。速くするための仕組みの性質が、そのまま情報の漏れ口になった例です。
よくある問い キャッシュメモリと キャッシュメモリは すぐ近くにある小さくて速い控えの置き場で、主記憶) はプログラムが作業中のデータを広げる大きな置き場です。主に SRAM、主記憶には DRAM が使われ、SRAM の方が速い代わりに高価です。キャッシュはプログラムから直接は操作せず、CPU が自動で間に挟みます。
L1、 数字は CPU からの近さの段で、L1 が一番近くて速く、一番小さい段です。L1 で外れると L2、L2 で外れると L3 を見て、それでも無ければ主記憶へ取りに行きます。Norvig の表では、L1 から読むのが 0.5 ナノ秒、L2 から読むのが 7 ナノ秒です。
ヒット率とは何ですか ヒット率は、読んだ回数のうち、キャッシュに当たった回数の割合です。この頁の模型では、表を行の順に読むと 64 回 中 56 回 当たり、ヒット率は 0.875 です。当たりと外れの時間の差が大きいので、ヒット率が少し変わるだけで平均の待ち時間は大きく動きます。
確認クイズ 答えだと
1 問目
キャッシュメモリを 置く一番の理由はどれですか。
ア 主記憶より イ 電源を ウ 主記憶より エ 主記憶を 2 問目
この頁の模型 (1 行 に 8 個 、置ける行は 4 本 、LRU) で、番地 0 から 15 までを順に 1 回 ずつ読みます。このコードを動かすと何が出ますか。
番地 0〜15 を順に読む
print(run(range(16)))3 問目
時間の局所性の説明として正しいのはどれですか。
ア 使った イ 最近使った ウ 古い エ 番地の 4 問目
置ける行が 4 本 の LRU の模型で、5 本 の行を順にくり返し読むと、当たりがほとんど無くなりました。理由はどれですか。
ア 5 本目を イ 行の ウ 同じ エ 主記憶が 説明課題 次のことを、図を思い浮かべながら、自分の言葉で 3〜4 行 にまとめてください。書いたら、下の模範解答を開いて比べてください。
速いのはなぜか。階層のどの段とどの段の差かを含めて 8 行 8 列の表を、行の順に読む方が列の順に読むより当たりやすいのはなぜか あなたの説明
模範解答 模範解答を開く 自分の
記憶の置き場は、レジスタ、L1、L2、L3、主記憶、ディスクと、上ほど速くて小さく、下ほど遅くて大きい段に並ぶ。当たれば すぐ近くの段で済み、外れると何段も下の主記憶まで行く。Norvig の表では L1 が 0.5 ナノ秒、主記憶が 100 ナノ秒で、200 倍の差がある。キャッシュは隣の番地を含む行の単位で載せるので、表を置いた順の行の順に読めば、1 回 外れたあとの同じ行の残りは当たる。列の順では毎回別の行を読み、戻る前に追い出されるので当たらない。
大きな
もっと深く この
一次資料 どれも 2026年 10月 27日 に開いて、題と中身を確かめました。
