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

Happy My Life

日常とか技術とか

2次キャッシュを意識してコーディングしてる?

先日、北陸twitterオフで、2次元配列をx,yの順でアクセスするのと、y,xの順でアクセスするのでは、実行速度が違うんだよ、という話をしていたのだが、正直このネタは4、5年前にMIPSを使っていたときの事なので、今でも有効なのか?と思いベンチマークプログラムを作成して検証してみた。

内容

Integer型二次元配列の内容を処理する時に、アドレス順に行う(キャッシュにヒットしやすい)場合と、そうでない(キャッシュにヒットしにくい)場合を比較してみた。

環境

結果

X Y キャッシュヒット キャッシュミス diff
1024 1024 0.002351 sec 0.062166 sec x 26.44
1024 2048 0.004840 sec 0.133981 sec x 27.68
2048 1024 0.004880 sec 0.122917 sec x 25.18

結論

今でも有効な手法という事が判明。Core2Duoの2次キャッシュも十分大きいので、そんな大差がつかないだろうと思っていたのだが、思ったより差がついたので、自分でもビックリ。遅いと言っても、それでも十分早いが。

コードは下にある通り。プログラム自体の差は、見た目ほどんど分からないが、実行時間となると結構差が出てくる。

詳しい解説

Intel Core 2 Duo - Test (page 6: Caches, memory and prefetch) - BeHardwareの資料を元に話を進める。

2次キャッシュは、コードを格納するコードキャッシュとデータを格納するデータキャッシュの2種類がある。今回のプログラム程度ではコードは全部キャッシュに載るので、あとはデータキャッシュをいかにヒットさせるかが焦点となってくる。

2次キャッシュはページ単位で管理されており、Core2Duoは1ページ32KBでキャッシュを管理している。つまり、データは32KB以内の領域を連続してアクセスする場合は2次キャッシュにヒットするのでCPUと同等の速度でデータを取得し計算を行う事ができる。しかし、32KBより外側のデータを取得する必要がある場合は、キャッシュミスとなるので、いったんメインメモリから2次キャッシュにデータを格納した後、CPUが計算を行うのである。

通常CPUのクロック速度に比べ、メインメモリへのアクセス速度が遅いのが一般的。今回の場合も、アドレスを飛び飛びでアクセスする事でキャッシュミスが頻発し、CPUは結構ストール(待たされる)が発生していたのではないかと思われる。これが、今回速度の差が出た原因である。

Core2Duoのキャッシュを正しく把握した上でループを最適化してやれば、もっと速くなる可能性もあるが、今回はここまで。

2次キャッシュを意識せよ

プログラムを高速に動作させるのは、データ構造&アルゴリズムが一番大切だが、その次に「いかに2次キャッシュにヒットさせるか」を意識したコーディングを行う事で、処理速度が速くなる事が立証された。

今回のように、可読性を損わずに最適化を行う事も十分可能なのである。

コード

#include 
#include  

#define Y_SIZE (1024)
#define X_SIZE (1024)
#define LOOP_COUNT (100)

double cachehit_times[LOOP_COUNT];
double cachemiss_times[LOOP_COUNT];

double time_diff( struct timeval*, struct timeval*);
void print_result( char *message, double *list);

void init_buf(int *buf)
{
    int x,y;
    for (y = 0; y < Y_SIZE; y++)
    {
        for (x = 0; x < X_SIZE; x++)
        {
            buf[x+y*X_SIZE] = x % 100;
        }
    }
}

main() {
    int *buf = (int*)malloc(Y_SIZE*X_SIZE*sizeof(int));
    struct timeval start, end;
    int x,y;

// cache hit
    init_buf(buf);
    int i,tmp;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        gettimeofday(&start, NULL);
        for (y = 0; y < Y_SIZE; y++)
        {
            for (x = 0; x < X_SIZE; x++)
            {
                tmp = buf[x+y*X_SIZE];
                buf[x+y*X_SIZE] = tmp + 1;
            }
        }
        gettimeofday(&end, NULL);
        cachehit_times[i] = time_diff(&start,&end)/1000000.0;
    }
    print_result("cache hit (average): %f secn", cachehit_times);

// cache miss
    init_buf(buf);
    for (i = 0; i < LOOP_COUNT; i++)
    {
        gettimeofday(&start, NULL);
        for (x = 0; x < X_SIZE; x++)
        {
            for (y = 0; y tv_sec - st->tv_sec ) * 1000000 + ( et->tv_usec - st->tv_usec );
}

void print_result(char *message, double *list)
{
    double time = 0;
    int i;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        time += list[i];
    }
    printf(message, time/LOOP_COUNT);
}