キャッシュでメモリが速くなる理由

ある通販会社では、毎晩、大きな売上表を合計する集計を動かしています。担当者が2つのループを入れかえて、行ではなく列の順に足すようにしました。

合計は1円も変わりません。ところが集計にかかる時間が、何倍にもなりました。仕事の量は同じで、変わったのは順番だけです。原因はキャッシュです。

プロセッサは、足し算を1ナノ秒よりずっと短い時間で行います。ところがメインメモリを読むには、その100倍ほどかかります。

そこでコンピュータは記憶階層を持ちます。プロセッサのすぐそばに、小さくて速いキャッシュがあります。L1、L2、そして多くの場合 L3 です。その後ろにメインメモリ、さらに後ろにディスクがあります。下の段ほど大きく、遅くなります。

cd ~/arch

getconf LEVEL1_DCACHE_LINESIZE

キャッシュは、1バイトだけを写すことはしません。ミスのときは、下の段からキャッシュライン1本、ふつう64バイトをまとめて写します。

これが得になるのは、局所性があるからです。プログラムは、今読んだデータのすぐ隣をまもなく読みます。これが空間的局所性です。同じデータをまた読むこともあります。これが時間的局所性です。どちらの場合も、次の読みこみはヒットになります。

loop.c には、4096行 × 4096列の int の表があります。int は4バイトなので、1行は16384バイトで、64バイトのライン1本には数が16個入ります。

行の順に読むと、1回のミスで次の16個が入るので、16回のうち15回はヒットです。列の順に読むと、次の数はいつも1行先で、別のラインにあります。そのラインに戻ってくるころには、もう追い出されています。

python3 -c "print(4096 * 4096 * 4 // 1024 // 1024, 64 // 4)"

gcc -O2 -o loop loop.c

./loop

ダイレクトマップ方式のキャッシュでは、どの番地も、入れるラインがちょうど1つに決まっています。番地を3つに分けて考えます。

オフセットは、番地をラインの大きさで割った余りで、ラインの中の何バイト目かです。番地をラインの大きさで割った商がブロック番号です。インデックスはブロック番号をライン数で割った余りで、どのラインかを決めます。タグは残りの部分で、今そのラインにどのブロックがあるかを表します。

python3 -c "print(0x3a7c % 32, 0x3a7c // 32 % 16, 0x3a7c // 512)"

sed 's/4096/3000/' loop.c > odd.c で、1辺が3000の表を作るコピーを作ってください。gcc -O2 -o odd odd.c で作り、./odd を何回か実行します。

和は、実行する前に予想しましょう。次に、2つの順番の差を ./loop の差と比べます。1行のバイト数が2の累乗でなくなると何が変わるのか、シミュレータでインデックスを調べて説明してください。