多次元配列の速度比較

C#

行列のような2次元配列のデータをC#上で表現するとき、それにはいくつか方法があります。それぞれの処理速度を比べてみます。

Jagged Array

配列の配列です。Javaと同じ。

double[][] matJagged = new double[100][];
for (int i = 0; i < matJagged.Length; i++)
{
    matJagged[i] = new double[100];
}

Rectangular Array

狭義の多次元配列です。Javaにはありません。

double[,] matRectangular = new double[100, 100];

Linear Array

普通の1次元配列を、行または列ごとに1列に並べてある行列とみなします。Rectangular Arrayも内部では1次元配列になっています。

double[] matLinear = new double[100 * 100];

行ごとに並べるか(C)、列ごとに並べるか(Fortran)の方式の違いがあります。例えば2行2列のaという2次元配列が合った場合、Cでは、

a[0][0], a[0][1], a[1][0], a[1][1]

とメモリ上に要素が並びますが、Fortranでは、

a(0,0), a(1,0), a(0,1), a(1,1)

となります。C#はCと同じように並んでいる（はず）なので、今回はCの方式にします。

速度比較

サイズを 10000x10000 の行列として、全ての要素にアクセスする時間を計りました。

手法 処理時間(ms)
Jagged 1209
Rectangular 1597
Linear 1053

1次元配列が速いのは順当ですが、間接参照が多いJagged Arrayが速いのが意外かもしれません。これは、1次元配列のアクセスにはIL上で特別な命令があるためのようです。Jagged Arrayは1次元配列の入れ子なので、それが効くようです。

unsafe + fixed

そのものずばりの多次元配列であるRectangular Arrayが遅いのは浮かばれません。しかし、先頭のポインタを取得して1次元配列と同じようにしてアクセスすると大幅に高速化できます。

unsafe
{
    int rows = matRectangular.GetLength(0);
    int cols = matRectangular.GetLength(1);
    fixed (double* p = &matRectangular[0, 0])
    {
        for (int r = 0; r < rows; r++)
        {
            for (int c = 0; c < cols; c++)
            {
                p[r * rows + c] = r * c;
            }
        }
    }
}

処理時間を計測すると、だいたい3分の1ぐらいまで速くなりました。この方法はメモリ領域が連続しているからこそ出来るので、Jagged Arrayでは（このままの方法では）できません。

まとめ

高速化を求めるならば1次元配列を使うべきですが、わかりにくいのであればJagged Arrayを使うのがよさそうです。ただし初期化が面倒です。

また、Jagged ArrayはP/Invokeの際は面倒です。C側で2次元配列を引数に取るところにそのままでは渡せません。memcpyで配列データを一気にコピーしたりも出来ません。

結局は用途次第ですね。

テストコード

const int Size = 10000;
double[][] matJagged = new double[Size][];
for (int i = 0; i < matJagged.Length; i++)
{
    matJagged[i] = new double[Size];
}
double[,] matRectangular = new double[Size, Size];
double[] matLinear = new double[Size * Size];

Stopwatch watch = Stopwatch.StartNew();
for (int r = 0; r < Size; r++)
{
    for (int c = 0; c < Size; c++)
    {
        matJagged[r][c] = r * c;
    }
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);

watch.Reset();
watch.Start();
for (int r = 0; r < Size; r++)
{
    for (int c = 0; c < Size; c++)
    {
        matRectangular[r, c] = r * c;
    }
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);

watch.Reset();
watch.Start();
for (int r = 0; r < Size; r++)
{
    for (int c = 0; c < Size; c++)
    {
        matLinear[r * Size + c] = r * c;
    }
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);

unsafe
{
    watch.Reset();
    watch.Start();
    fixed (double* p = &matRectangular[0, 0])
    {
        for (int r = 0; r < Size; r++)
        {
            for (int c = 0; c < Size; c++)
            {
                p[r * Size + c] = r * c;
            }
        }
    }
    watch.Stop();
    Console.WriteLine(watch.ElapsedMilliseconds);
}