STAGE 3
キャッシュ
近くに置いて速くする
🎯 ミッション
キャッシュが当たる仕組み(ライン単位で運ぶ・2つの局所性)を説明できるようになろう。3つの読み方でキャッシュの当たり外れを確かめ、確認クイズに全問正解すれば合格。
未達成

ねこ博士
前のステージで、メモリから1つ読むのに約300拍も待つと分かった。この待ち時間を減らすために、CPU の中には、メモリの一部の写しを置いておく、小さくて速い記憶がある。これをキャッシュと呼ぶ(cache は「隠し場所」という意味)。

うさ美
机の上に、よく使う本を何冊か置いておくようなものですね。

ねこ博士
そう。CPU がある番地を読みたいとき、まずキャッシュを見る。そこに写しがあれば当たり(ヒット)で、数拍で読める。無ければ外れ(ミス)で、メモリまで取りに行き、ついでにキャッシュにも写しを置いておく。

うさ美
でもキャッシュは小さいんですよね。何を置いておくかは、どうやって決めるんですか? 未来に何を読むかは分からないのに。

ねこ博士
いい質問だね。未来は分からないけれど、プログラムにはよく当たる癖がある。2つあるよ。1つ目は、一度使った場所は、すぐにまた使うことが多い。くり返しの中で同じ変数を何度も足す、というように。

うさ美
だから、さっき使ったデータを残しておけば、また当たる。

ねこ博士
そう。これを時間的局所性と呼ぶ(局所性=使う場所が一部に偏ること)。2つ目は、ある場所を使ったら、その近くの番地もすぐに使うことが多い。配列を前から順に読むときがそうだね。

うさ美
配列は、番地が連続した箱に並んでいるから、1つ読んだら次は隣の番地ですね。

ねこ博士
そう。これは空間的局所性と呼ぶ。そこでキャッシュは、外れたときに1バイトだけでなく、その周りの決まった大きさのかたまりをまとめて運んでくる。このかたまりをキャッシュラインと呼び、いまのパソコンではふつう64バイトだ。
外れたとき:その番地を含む1ライン(例:64バイト)を丸ごとメモリから運び、キャッシュに置く
時間的局所性:さっき使った場所をまた使う → 置いてある写しに当たる
空間的局所性:近くの番地を続けて使う → 一緒に運んだラインに当たる

うさ美
キャッシュがいっぱいになったら?

ねこ博士
どれかを追い出して場所を空ける。よく使われるのは「いちばん長いあいだ使っていないラインを追い出す」やり方で、LRU(Least Recently Used)と呼ぶ。最近使ったものほどまた使う、という1つ目の癖に合わせた決め方だね。

ねこ博士
小さな例で数えてみよう。ラインを4バイト、キャッシュに置けるラインを4本とする。番地0から順に、1バイトずつ32バイト読むと、外れるのは何回かな。

うさ美
番地0 で外れて、0〜3 の4バイトがまとめて運ばれる。だから 1〜3 は当たり。番地4 でまた外れて 4〜7 が運ばれる……。4バイトに1回外れるので、32 ÷ 4 = 8回外れて、24回当たり。4回に3回は当たります。

ねこ博士
では、番地0, 4, 8, 12, … と、4バイトおきに16回読んだら?

うさ美
毎回、新しいラインの先頭を読むことになるので、16回とも外れです。せっかくまとめて運んだ残りの3バイトは、一度も使われない。同じ回数読んでも、順番だけで当たり方がまるで違いますね。
※ 模型では、ライン4バイト、キャッシュは4本、追い出しは LRU。

ねこ博士
そこが大事なところなんだ。プログラムの答えは同じでも、メモリをどの順番で読むかで速さが何倍も変わる。たとえば、縦横に並んだ表(2次元の配列)は、メモリの上では1行目、2行目……と横の並びが続けて置かれることが多い。それを縦向きに読むと、毎回別の行、つまり遠くの番地へ飛ぶことになる。

うさ美
行ごとに読めば空間的局所性が生きて、列ごとに読むと外れてばかりになる……。書き方のちょっとした違いで速さが変わるんですね。

ねこ博士
実際、大きな表で試すと、何倍もの差が出ることがある。キャッシュは CPU が勝手にやってくれるので、プログラムには1行も現れない。それでも、メモリの並び方を知っている人は、キャッシュに当たりやすい書き方ができる。

うさ美
キャッシュは1つだけですか?

ねこ博士
いまの CPU は、小さく速い L1、少し大きい L2、さらに大きく複数のコアで共有する L3 と、何段かに分けて持っていることが多い。L1 で外れたら L2、L2 で外れたら L3、それでも外れたらメモリ、と順に探しに行くんだ。次のステージからは、プログラムのデータがメモリのどこに置かれるかの話に入ろう。まずは、関数を呼ぶたびに使われる場所、スタックだ。
確認クイズ
Q1. キャッシュが外れたとき、メモリから運んでくるのは?
正解! 近くもすぐ使われる(空間的局所性)ので、1ラインまとめて運ぶ。次に隣を読むときは当たりになる。
Q2. 「一度使った変数を、すぐにまた使う」ことが多い、という癖の名前は?
正解! 時間の面で偏る=時間的局所性。近くの番地を続けて使うのが空間的局所性。LRU は追い出すラインの決め方。
Q3. 大きな2次元の表を、行の順に読むより列の順に読むほうが遅くなることがある理由は?
正解! 計算回数は同じ。違うのは番地の飛び方。行の順なら一緒に運んだラインに当たり、列の順だと毎回別のラインが要る。