ミスキャッシュのペナルティ
現在のプロセッサ(CPU)はメモリ(DRAM)よりも高速に動作できるため、プロセッサ内部のキャッシュ(cache)にメモリの内容の一部をコピーすることで、メモリの速度の限界よりも速く動作できるようになっています。しかし、アクセスの仕方によってはキャッシュが有効に機能せず、性能を大きく落としてしまいます。
以下は、後述するプログラムを実行した例です。「a」をつけるとキャッシュに有利なアクセス方法になり、結果として速度が5倍弱になっています(環境によっては10倍近くになるものもありました)。
[kimoto@localhost test]$ time ./cachetest real 0m15.528s user 0m15.457s sys 0m0.008s [kimoto@localhost test]$ time ./cachetest a real 0m3.669s user 0m3.644s sys 0m0.008s [kimoto@localhost test]$
この違いは、メモリのアドレスによってキャッシュできない組み合わせがあることにより生じます。つまり、キャッシュの全容量が有効に利用できるわけではないということです。一般のプログラミングで考慮することはまず不可能ですが、プロセッサにはいろいろなタイプの限界があることを体験することができます。
cachetest.c
typedef int W;
typedef unsigned int UW;
typedef short H;
typedef unsigned short UH;
typedef char B;
typedef unsigned int UB;
#define ARRAYSIZE 256
static struct {
UW a;
UW b;
UW c;
UW d; /* 16 bytes = 1 cache-line */
} array[ARRAYSIZE * ARRAYSIZE] = {{1}};
int main(int ac, char **av)
{
W i, j, mul;
mul = (ac > 1)? (ARRAYSIZE + 1) : ARRAYSIZE;
for (i=0; i<1000000; i++)
for (j=0; j<ARRAYSIZE; j++)
array[mul * j].a++;
}
/* end of file */
CygwinまたはLinuxで「gcc -o cachetest cachetest.c」を実行すると、cachetestというプログラムができます。これを、「./cachetest」または「./cachetest a」として実行します(aをつけないとキャッシュに不利な処理になります)。実行時間を計りたい場合は、「time ./cachetest」または「time ./cachetest a」としてください。
