時間的局所性と空間的局所性
参照局所性とは、アクセス先が時間やアドレス空間の中で偏る性質です。時間的局所性は同じ場所を短い間隔で再び使うこと、空間的局所性は近くの場所を続けて使うことを指します。ループで繰り返し読む係数は前者、配列を先頭から順に読む操作は後者の例です。どちらも「すべてのアクセスが等しく起こる」という仮定から外れるため、小さい高速な記憶領域が役に立ちます。
キャッシュラインで考える
CPUキャッシュは通常、個々の変数より大きいキャッシュラインを単位としてデータを扱います。例としてラインを64バイト、整数を4バイトとすると、整列した連続16要素が同じラインに収まります。先頭の読み出しでラインを取得できれば、その後の近接要素は同じラインから読める可能性があります。ただし実際のラインサイズ、整列、プリフェッチの有無は機種によって異なり、この数値は説明用の条件です。
ループの順番を変える例
行優先で配置された二次元配列では、同じ行を横に進む走査は連続したアドレスを使います。列を固定して行を飛び越える走査では、行幅に応じた大きな間隔が生まれます。どちらも要素数が同じなら計算量は同じですが、必要なライン取得回数は変わり得ます。比較実験では配列の配置方式、要素サイズ、作業集合の大きさを揃え、時間だけでなくキャッシュミスの計測も併せて解釈します。
局所性だけでは性能は決まらない
局所性が良くても、作業集合がキャッシュ容量を超えたり、複数のアドレスが同じ配置先を競ったりするとミスは増えます。複数コアが同じラインを書き換える場合は、データの受け渡しによる負担も発生します。局所性は性能を考える有力な手掛かりですが、処理時間を単独で予測する公式ではありません。アルゴリズムの処理量やメモリ帯域、測定時の他の負荷も分けて確かめる必要があります。
再利用距離を手で追う
容量2ラインの完全連想キャッシュで、LRU置換、初期状態は空と仮定します。参照列A、B、A、C、Aでは、最初のAとBがミス、次のAがヒットです。Cを入れる際は最近使わなかったBを追い出すので、最後のAもヒットし、計3ミス2ヒットになります。参照列A、B、C、A、Bでは5回すべてミスになります。同じ五つの参照でも、再利用までに間に入る別ラインの数が変わると結果が変わります。これは置換規則を固定したモデルの計算であり、実機のプリフェッチや集合の競合を含む測定値ではありません。