CPUキャッシュ階層 — 近いほど速いが、小さい

CPUはものすごく速いのに、データが入っているメインメモリ(RAM)は意外と遠い。RAMまで取りに行くと、CPUの体感で何十回分もの待ち時間が発生します。そこでCPUは、よく使うデータを手元の小さな引き出し=キャッシュに置いておきます。近いほど速いが、小さい。これがL1 / L2 / L3という階層の正体です。

下の図1で、RAMにあるブロックを押して「要求」してみてください。CPUはL1→L2→L3→RAMの順に探し、見つかった場所までの距離だけ時間がかかります。一度使ったデータは手前に引き寄せられるので、すぐにもう一度使うと一瞬で返ってきます。

速さの正体は「局所性」

キャッシュが効くのは、プログラムのアクセスにかたより(局所性)があるからです。一度使ったデータは、すぐまた使われやすい(時間的局所性)。だから直近で触ったものを手前のL1に置いておけば、多くのアクセスが一瞬で済みます。図で同じブロックを連打すると累計時間がほとんど伸びないのは、ずっとL1ヒットしているからです。

逆に、毎回バラバラの場所を触る(局所性のない)処理はキャッシュが当たらず、何度もRAMまで取りに行くことになります。「巨大配列をとびとびに舐める」より「連続して舐める」ほうが何倍も速いのは、このためです。階層は近いほど速いが小さいので、本当によく使うものだけが手前に残り、押し出されたものは順に奥(L2→L3→RAM)へ下がっていきます。

まとめ

CPUキャッシュは「近いほど速いが小さい」階層を重ね、よく使うデータを手元に引き寄せておく仕組みです。プログラムを速くしたいとき、計算量(オーダー)が同じでもメモリに連続・局所的にアクセスするだけで体感速度が大きく変わります。キャッシュの存在を意識することが、地味だけれど効く高速化の第一歩です。