同じ件数を読む処理でも、メモリを読む順番でキャッシュの効き方が変わる

用語

キャッシュライン

CPUキャッシュがデータを取り込む単位。1要素だけを要求しても、通常はその周辺を含むかたまりで取り込む。大きさは構成による。

空間的局所性

あるアドレスを使った直後に、その近くのアドレスも使う性質。連続配列の順次走査が例。

時間的局所性

同じデータを短い間に再び使う性質。再利用までキャッシュに残っていれば、下位への読み取りを減らせる。

キャッシュミス

調べたキャッシュに必要なデータがないこと。下位のキャッシュや主記憶を読み、取得の時間を払う。

図と例

計算モデル：ラインを64バイト、要素を8バイトとし、先頭をライン境界へそろえた連続配列を読む。キャッシュは初め空で、プリフェッチと他のアクセスは無視する。先頭8要素は1ラインに収まる。64バイトずつ離れた8要素なら8ラインにまたがる。読む要素は同じ8件でも、触れるラインは1本と8本になる。これはライン数の比較で、8倍速くなる実測ではない。

実際のサービス・製品では

• Cornell Virtual Workshop

  Cornellの性能最適化教材は、Intelプロセッサの64バイトラインを例に、連続したアドレスの利用とキャッシュ内のデータの再利用を説明する。このTipの64バイトは、その例に合わせた仮定である。

  資料を読む

解説

大量の配列処理や集計で、計算量を改善しても遅いときに使う。連続配置の配列を順に読む、小さなブロックへ分けて再利用するなどを比べる。意味上隣り合う要素が物理的にも連続しているとは限らないため、言語とデータ構造の配置を確認する。速度は実測し、ラインの使用率をそのまま高速化の倍率にしない。

CPUの近くには、主記憶より小さく高速なCPUキャッシュがある。欲しい値がなくてキャッシュミスすると、下位のキャッシュや主記憶から、その値を含むキャッシュラインを取り込む。配列を隣の要素へ順に読むと、一度取り込んだラインの残りも使えるため空間的局所性が高い。同じ小さなデータを何度も使う処理には時間的局所性がある。一方、離れた場所へポインターで次々に飛ぶと、取り込んだラインの一部しか使わないことがある。どちらもO(n)の走査でも、メモリアクセスの費用は同じとは限らない。実際の差は配列の配置・キャッシュ容量・プリフェッチ・コンパイラーなどで変わる。

さらに学ぶ

• Cornell CS 3410 — Caches
• Cornell Virtual Workshop — Data Locality Matters

チェック

計算モデル：64バイトのキャッシュライン、8バイト要素、配列先頭はライン境界に一致。先頭から連続した16要素は何本のラインに収まる？

1. 1ライン
2. 2ライン
3. 16ライン