メモリ階層と性能
C言語の2次元配列a[i][j]を上のように内側のループをjにして走査すると、内側をiにするより速くなりやすい。その理由はどれか。
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[i][j];- A行優先で格納されているため、連続したアドレスを順に読み、キャッシュラインを有効に使えるから
- Bコンパイラがループの中の加算をまとめて取り除き、計算そのものを実行時に省略してしまうから
- C内側をjにするとTLBを一切参照しなくなり、仮想アドレスから物理アドレスへの変換が不要になるから
答えと解説を見る
正解：A. 行優先で格納されているため、連続したアドレスを順に読み、キャッシュラインを有効に使えるから
C言語の2次元配列は行優先(row-major)で格納され、a[i][0]、a[i][1]…がメモリ上に隣り合います。内側をjにすると連続したアドレスを順に読むため、1回のミスで読み込んだ64バイトのキャッシュラインの残りもすぐ使われます。内側をiにすると1行分ずつ離れたアドレスを飛び飛びに読み、ラインのごく一部しか使わないうちに追い出されやすくなります。TLBは使い続けており、アドレス変換が不要になるわけではありません。
- A. 正しい。連続したアドレスを読むので、読み込んだラインの全体を使えます。
- B. 加算は省略されず、どちらの順でも同じ計算をします。
- C. TLBは引き続き使われ、アドレス変換も行われます。