キャッシュを無駄遣いするとどうなるか試してみた

コンピュータさんは、すぐに使いそうなデータをキャッシュにいれてくれる。

CPU がメインメモリからデータを読み出すとき、必ず小さなメモリチャンクをキャッシュ上にロードする。ロード単位はプロセッサによるけど、だいたい 8 ～ 512 バイト。このロード単位をキャッシュラインと呼ぶ。
アクセス対象のデータが既にキャッシュに載ってる場合は、メインメモリじゃなくてキャッシュを読みに行く。ない場合はメインメモリにアクセスするけど、そのデータはもしかしたら既にキャッシュラインに載ってキャッシュに読み込まれてる途中かもしれないから、いまのキャッシュラインがロードされるのを待って、欲しいデータがキャッシュに載らなかったのを確認してから、改めて欲しいデータをキャッシュラインに載せる。これがキャッシュミスヒット。遅い。

by CPU とキャッシュのはなし - graphics.hatenablog.com

早い処理をしたいときは、キャッシュを最大限に有効活用できるようなコードを書きたい。
でもそれじゃあ逆に。キャッシュを無駄遣いすると何がどう変わるのか調べてみた。

書いたのはこんな感じの適当なのコード

#include <iostream>
#include <ctime>

using namespace std;

int arr[1000][1000][1000];
int main(int argc, const char * argv[]){
    clock_t startTime, endTime;
    startTime = clock();
    int sum = 0;
    
    for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 1000; j++) {
            for (int k = 0; k < 1000; k++) {
                arr[i][j][k] = i * j * k;
                sum += arr[i][j][k];
            }
        }
    }
    
    endTime = clock();
    cout << sum << endl;
    cout << (double)(endTime - startTime) / CLOCKS_PER_SEC << endl;
}

普通に配列をまわして端から値をいれていくだけ。
これを実行した結果が以下
f:id:cocodrips:20140126132815p:plain
大体5秒くらいかかった。

つぎに、このコードのfor文の部分を、こんなふうに書き換えた。

    for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 1000; j++) {
            for (int k = 0; k < 1000; k++) {
                arr[k][j][i] = i * j * k;
                sum += arr[k][j][i];
            }
        }
    }

arr[i][j][k] -> arr[k][j][i]になったわけだ。
配列の構造的には、arr[0][0][0], arr[0][0][1], arr[0][0][2]...
となってるわけだから、おそらくキャッシュはarr[0][0][0]にアクセスした時に、
arr[0][0][0] ~ arr[0][0][n] (nは2 ~ 64くらい?)の部分を取ってくるだろう。

だからarr[0][0][0], arr[1][0][0], arr[2][0][0]....とアクセスするのは、
そのキャッシュを全部無駄にしていることになる。

とにかく実行してみた。

...

( ˘ω˘)ｽﾔｧ

...

f:id:cocodrips:20140126133703p:plain
やっと終わった！32秒！