CPUより、キャッシュに乗っていないデータへのアクセスが発生するとスローダウンするが、キャッシュの容量は限られている。だから、プログラムやデータをムダに大きくすると実行速度をスローダウンさせる。
……と言われることがよくありますが、どの程度のスローダウンが発生するのでしょうか。
ちょっと気になったので簡単に検証。
題目 §
- C# 3.5で書く (変な最適化をさせないためにデバッグビルドで実行)
- byte配列を確保するが、nバイトごとにのみアクセスし、その間の要素は一切使わない。つまり、1要素ごとに(n-1)バイトのムダなメモリを上乗せする
- nは1,2,4,8,1024とする
- アクセスはランダムアクセスとし、アクセスする要素は乱数を用いてランダムな順番を決定する (シーケンシャルにアクセスするとn=1,2,4の値が大差なかったので、ランダムにやらせてみた)
サンプルソース §
using System;
class Program
{
private static void test(int size, int leave)
{
Random random = new Random(0);
int[] randomMap = new int[size];
for (int i = 0; i < size; i++)
randomMap[i] = random.Next(size) * leave;
byte[] ar = new byte[size * leave];
DateTime start = DateTime.Now;
int sum = 0;
for (int j = 0; j < 10000; j++)
{
for (int i = 0; i < size; i++)
ar[randomMap[i]] = 1;
for (int i = 0; i < size; i++)
sum += ar[randomMap[i]];
}
Console.WriteLine("time={0} leave={1} sum={2}",
DateTime.Now - start, leave, sum);
}
static void Main(string[] args)
{
int size = 100000;
test(size, 1);
test(size, 2);
test(size, 4);
test(size, 8);
test(size, 1024);
}
}
実行結果 §
time=00:00:14.5490000 leave=1 sum=1000000000
time=00:00:14.5230000 leave=2 sum=1000000000
time=00:00:18.9920000 leave=4 sum=1000000000
time=00:00:23.8240000 leave=8 sum=1000000000
time=00:01:52.1110000 leave=1024 sum=1000000000
考察 §
ムダ無しよりも2バイト(1バイトのムダあり)の方が速いのは、単純に誤差の範囲ということでしょう。たぶん。
しかし、4バイト(3バイトのムダあり)の方は、おそらく意味のある歴然とした差が出ています。
従って、以下のような結論を出せることになります。
- 整数の配列にランダムな順序でアクセスする場合、要素の値がbyte型で表現可能な範囲に限られるとすれば、int型からbyte型に変更することで体感可能なスピードアップが実現される可能性がある (ただし、この処理に限れば、であってプログラム全体で体感可能なスピードアップになるかは別問題)
(もちろん、仮想記憶のスワップ頻度も関係するなら、short→byteでもスピードアップの可能性があり得ますが、それはまた別の問題です)
