先日、北陸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);
}