読者です 読者をやめる 読者になる 読者になる

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

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

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秒!



なんとさっきの6倍以上の時間がかかった。
理論的には分かった気になっていたけど、
こんなにも時間差が生じるのか・・・。想像以上だった。

実際に動かしてみるのって大事。

今回みたいな変なアクセスの仕方はしないにしても、
こういうことをちゃんと考えてコードを書こうと思ったのだった。

おまけ

後のほうが、最初の6倍かかったっていうのは、
私のパソコンのキャッシュが32バイト単位くらいで保持されてるとすれば、
4バイト x 8 のキャッシュを活用してるか、していないかの違いなので納得できる数字ぽい気がする。
自分のパソコンのキャッシュラインがどれくらいってどうやってわかるんだろう・・・?