はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

【C#】2次元配列でループを回す際にアクセス順序によって速度に違いがでるらしい(行優先)

はじめに

先日ネットサーフィンをしていたところ、以下の記事を見つけました。

daeudaeu.com

C言語だと以下のコードに違いがでてくるそうです。

// こっちは低速
for(x = 0; x < 4096; x++){
    for(y = 0; y < 4096; y++){
        array2[y][x] = array1[y][x];
    }
}
// こっちの方が高速
for(y = 0; y < 4096; y++){
    for(x = 0; x < 4096; x++){
        array2[y][x] = array1[y][x];
    }
}

これがC#でもそうなのか実験してみたいと思います。

結論

先に結論を書いておくと、以下の書き方の方が高速です。

// 高速
for (var i = 0; i < count; i++)
{
    for (var j = 0; j < count; j++)
    {
        array[i, j] = 0;
    }
}

// 低速
for (var j = 0; j < count; j++)
{
    for (var i = 0; i < count; i++)
    {
        array[i, j] = 0;
    }
}

上記のC言語と同様ですね。

実験&結果

static void Main(string[] args)
{
    var stopwatch = new System.Diagnostics.Stopwatch();
    const int count = 50000;

    var array = new int[count, count];

    // パターン1
    stopwatch.Start();
    for (var i = 0; i < count; i++)
    {
        for (var j = 0; j < count; j++)
        {
            array[i, j] = 0;
        }
    }
    stopwatch.Stop();

    // 12279ms
    Console.WriteLine(stopwatch.ElapsedMilliseconds + "ms");

    // パターン2
    stopwatch.Reset();
    stopwatch.Start();
    for (var j = 0; j < count; j++)
    {
        for (var i = 0; i < count; i++)
        {
            array[i, j] = 0;
        }
    }
    stopwatch.Stop();

    // 41239ms
    Console.WriteLine(stopwatch.ElapsedMilliseconds + "ms");
}
パターン 処理速度(ms)
パターン1 12279
パターン2 41239

考察

2次元配列が列優先か行優先かで違いがでてくるらしいです。公式ドキュメントに記載が見つからなかったので間違ってたら申し訳ないのですが、foreachだと以下の画像のような順序で出力されるので、メモリもそのように並んでいて行優先ぽいですね。

// 4行2列の2次元配列
var array = new int[4, 2]
{
    {1,2},
    {3,4},
    {5,6},
    {7,8},
};
            
// 1,2,3,4,5,6,7,8
foreach (var i in array) Console.WriteLine(i);
メモリの配置順

learn.microsoft.com

これもドキュメントに記載されていたわけではないのであくまで推測の域ですが、メモリが近い値はキャッシュメモリが利用され、高速にアクセスすることができるからが原因のようです。

myoga.web.fc2.com