- ブラウザURL入力
- DNS名前→IP
- ルータ経路選択
- ロードバランサ振り分け
- Nginx受け口
- アプリ処理今ここ
- DB保存
CPUがいくら速くても、データが届かなければ計算できません。今回はCPUとメモリの速度差をどう埋めているかを見ます。
まず結論
速い記憶装置は小さく高価、大きい記憶装置は遅い。この制約からは逃れられないので、小さく速いものを手前に、大きく遅いものを奥に置いて段を作ります。これが記憶階層です。
この仕組みが効くのは、プログラムのメモリの使い方に強い偏りがあるからです。同じ場所を繰り返し使い(時間的局所性)、近い場所をまとめて使う(空間的局所性)。この偏りが無ければキャッシュは役に立ちません。
CPUがメインメモリ(DRAM)からデータを1つ取ってくる間に、CPUは何サイクルぶん待つことになるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
CPUは、ほとんどの時間を待って過ごしている
ここまでCPUの高速化を見てきました。パイプラインで重ね、分岐を予測し、命令を次々流す。ところが、それら全部を台無しにしかねない問題があります。
データが届かないのです。
CPUがメインメモリからデータを1つ取ってくる間、200〜400サイクル程度待つことになります。前回学んだ分岐予測ミスの損失が15〜20サイクルでしたから、その10倍以上です。
これがどれほど深刻か、身近な比率に直してみます。CPUが1サイクルを1秒だと感じるとすると、メモリからのデータ待ちは約3〜7分(200〜400秒)待たされる感覚です。どれだけ計算回路を速くしても、数分ごとに手が止まっていては意味がありません。
速さと大きさは、どうしても両立しない
なぜメモリは遅いのでしょうか。答えは単純で、大きいからです。
記憶装置には逃れられない制約があります。容量を大きくすると、遅くなる。目的の場所を探し出す手間が増え、信号の通り道も長くなるためです。
階層 容量の目安 遅延(サイクル) 遅延(ns)レジスタ 数百バイト 0〜1 ほぼ0L1キャッシュ 32〜48 KB 4〜5 約1 nsL2キャッシュ 0.5〜2 MB 12〜16 約3〜4 nsL3キャッシュ 8〜32 MB 40〜125 約10〜35 nsメインメモリ 8〜64 GB 200〜400 約60〜110 ns─────────────────────────────────────────────────────※ CPU世代・モデルで変動する(サーバ向けはL3が遅い例がある)。桁感覚として捉えること
この表を眺めると、容量が増えるほど遅くなる関係がはっきり見えます。L1は32KBしかない代わりに1ナノ秒、メインメモリは数十GB入る代わりに100ナノ秒前後です。100倍の差があります。
だから階層にします。すべてをL1の速度で作れるなら階層など要りません。作れないから、小さく速い段を手前に、大きく遅い段を奥に置くのです。
なぜL1キャッシュを32MBまで大きくしないのでしょうか。
なぜ小さいキャッシュで間に合うのか
ここで疑問が湧くはずです。32KBしかないL1に、数GBのメモリのうち何を置けばいいのでしょうか。 必要なデータがそこにある確率は、単純に考えれば絶望的に低そうです。
ところが実際にはうまくいきます。理由は、プログラムのメモリの使い方が、まったく均等ではないからです。偏りは2種類あります。
時間的局所性 — 一度使った場所は、すぐまた使われる。ループのカウンタ変数は、ループが回るたびに何千回も読み書きされます。
空間的局所性 — 使った場所の近くが、続けて使われる。配列を順に処理すれば、隣の要素が次に必要になります。
この偏りがあるおかげで、「直近に使ったもの」と「その近く」を手元に置いておくだけで、必要なデータの大半がキャッシュで見つかります。
64バイトまとめて持ってくる
空間的局所性を活かすため、キャッシュは1バイトだけ必要でも64バイトまとめてメモリから持ってきます。この単位をキャッシュラインと呼びます。
この性質が、非常に分かりやすい形で性能に現れる例があります。
// 速い: 行に沿って読む(ストライド1)for (i = 0; i < N; i++)for (j = 0; j < N; j++)sum += a[i][j];// 遅い: 列に沿って読む(ストライドN)for (j = 0; j < N; j++)for (i = 0; i < N; i++)sum += a[i][j];
この2つは同じ答えを出し、命令数もほぼ同じです。 それでも大きな配列では何倍も速度が変わります。
理由はキャッシュラインです。Cは行優先なので、同じ行の要素がメモリ上で隣り合っています。行に沿って読めば、64バイトのラインを1回持ってくるだけで16個のintが使えます。ところが列に沿って読むと、持ってきた64バイトのうち使うのは4バイトだけ。残りは捨てて、また次のラインを取りに行きます。
- ・答えは同じ。違うのは速度だけ
- ・FortranやJulia、MATLABは列優先なので、速い方が逆になる
ループの順序を変えると速度が変わるとき、計算結果はどうなりますか。
CPUのキャッシュ(ナノ秒の世界)
32KBのL1が1ナノ秒、数十GBのメインメモリが100ナノ秒。100倍の差を、使用頻度の偏りを利用して埋めています。
L1 32 KB 約1 ns ← 手元L2 1 MB 約3 nsL3 16 MB 約20 nsDRAM 32 GB 約100 ns ← 遠い100倍の速度差を階層で埋める
Webのキャッシュ(ミリ秒の世界)
ブラウザ内のキャッシュが数ミリ秒、地球の裏側のオリジンサーバが数百ミリ秒。やはり100倍前後の差を階層で埋めています。
ブラウザキャッシュ 約1 ms ← 手元CDNエッジ 約20 msオリジンサーバ 約200 ms ← 遠い100倍の速度差を階層で埋める
CPU内部のナノ秒の世界と、Web配信のミリ秒の世界。速度の単位は100万倍違いますが、同じ原理が働いています。それは何でしょうか。
どちらも「速いものは小さく、大きいものは遅い」という同じ制約に直面しています。
この章のまとめ
- メインメモリへのアクセスは200〜400サイクル。分岐予測ミス(15〜20サイクル)の10倍以上で、桁が違う。
- 記憶装置は大きくすると必ず遅くなる。だから小さく速い段と大きく遅い段を重ねる(記憶階層)。
- 階層が機能するのは、プログラムのアクセスに時間的局所性と空間的局所性という偏りがあるから。偏りが無ければキャッシュは効かない。
- キャッシュは64バイト単位(キャッシュライン)でまとめて転送する。だから配列を順に読むと速い。
- ループの順序を変えるだけで何倍も速度が変わることがある。答えは同じで速度だけが変わるのがキャッシュ効果の特徴。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
キャッシュが効果を発揮するのは、プログラムにどんな性質があるからですか。
用語集(5語)
- キャッシュ
- よく使うデータを手元の速い記憶装置に置いておく仕組み。CPU内部にL1・L2・L3の段階で配置される。
- 記憶階層
- レジスタ→L1→L2→L3→メインメモリ→ストレージと、速くて小さいものから遅くて大きいものへ並べた構造。
- 時間的局所性
- 一度アクセスした場所は、近いうちにまたアクセスされやすいという性質。ループ変数などが典型。
- 空間的局所性
- アクセスした場所の近くが、続けてアクセスされやすいという性質。配列を順に読む場合が典型。
- キャッシュライン
- キャッシュがメモリとやり取りする単位。多くのCPUで64バイト。1バイトだけ必要でも64バイトまとめて転送される。