C#の1次元配列と多次元配列のアクセス速度の違い

前回の記事で紹介した2次元配列の管理クラスですが中身のデータを「1次元配列を2次元配列扱いする」か「C#固有機能の多次元配列」で行ったときの実行速度に触れましたが今回は実際に速度の違いを計測してみました。

takachan.hatenablog.com

タイトルの通り、2次元配列のデータ格納方式各々のアクセス速度を計測します。

確認内容

2次元配列をC#上で扱うためにはいくつかの実装方法があり、各々のアクセス速度を計測します。対象とするデータ形式は以下の通りです。

Item	説明
int[ ]	1次元配列、データアクセスは int[y * STRIDE + x] で行う
int[ ][ ]	2次元配列、ジャグ配列と呼ぶ。アクセス方法は int[y][x]
int[, ]	2次元配列、C#固有の宣言方法。アクセス方法は int[y, x]
List<List>	リストを2次元配列に見立てる。アクセス方法は list[y][x]

確認環境

この実行速度計測は以下環境で確認しています。

Item	Elem
IDE	VisualStudio2019
Runtime	.NET core3.1
OS	Windows10 1909
CPU	Core i7-3770 3.4Ghz（L1:32KB,L2:256KB,L3:8MB）
Memory	16GB

.NET Core3.1 の Release ビルドのExeをコマンドラインから実行して速度を計測しています。

実行結果

先に実行結果を載せておきます。

アクセス方法	int[ ]	int[ ][ ]	int[, ]	List<List>
シーケンシャルアクセス	32.3841msec	32.4754msec	35.0817msec	38.6112msec
シーケンシャル（割合）	1	+0.2%	+8.3%	+19.2%
ランダムアクセス	1010.8107msec	1111.5819msec	1039.6755msec	1244.3971msec
ランダム（割合）	1	+9.96%	+2.8%	+23.1%

Listは論外です。そもそもこういう用途に向いていません。

やはりどのケースでも1次元配列が一番早いです。まぁ何も考えなければこれを使用しましょう。

ジャグ配列と2次元配列はシーケンシャルとランダムで特性が逆になっています。実際に使用す時はランダムアクセスが遅いと問題になりがちなので2次元配列の方が使えるかもしれません。

実行コード

ここでは速度計測に使用したコードを掲載します。

シーケンシャルアクセス

シーケンシャルアクセスは先頭から末尾までの要素を順にアクセスして要素へのアクセス時間を計測します。

public static void Main(string[] args)
{
    // 最初に少しCPUを温めておく
    double d = 0;
    for (int i = 0; i < 1000; i++)
    {
        Console.WriteLine("0");
        d += i*0.77;
    }
    Console.WriteLine(d);

    // --- データ作成と初期化 ---

    // 1024 * 1024 * 10 = 10MB分(L3キャッシュ以上)の領域を取る
    int width = 3238;
    int height = 3238;

    // (1) 1次元配列を2次元配列扱いする
    int[] array = new int[width * height];

    // (2) 2次元配列(=ジャグ配列)
    int[][] jagged = new int[height][];
    for (int i = 0; i < width; i++)
    {
        jagged[i] = new int[width];
    }

    // (3) 2次元配列(C#固有機能)
    int[,] csarray = new int[height, width];

    // (4) List<T>で2次元配列
    var listarray = new List<List<int>>();
    for (int i = 0; i < height; i++)
    {
        listarray.Add(new List<int>());
    }

    // (1) ～ (4) までの入れ物をすべて同じ値で初期化
    var r = new Random();
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            int p = r.Next();
            array[height * y + x] = p;
            jagged[y][x] = p;
            csarray[y, x] = p;
            listarray[y].Add(p);
        }
    }

    // 計測結果平均値を記録する変数
    double total_1 = 0; // (1)
    double total_2 = 0; // (2)
    double total_3 = 0; // (3)
    double total_4 = 0; // (4)

    // 時間計測用のタイマー
    var sw_1 = new Stopwatch(); // (1)
    var sw_2 = new Stopwatch(); // (2)
    var sw_3 = new Stopwatch(); // (3)
    var sw_4 = new Stopwatch(); // (4)

    // アクセス結果を記録するリスト(読み捨て用)
    var _temp = new List<int>();

    // --- ランダムアクセス ---

    // 500回の平均を取る
    int loops = 500;
    for (int i = 0; i < loops; i++)
    {
        // (1) の時間測定
        sw_1.Reset();
        sw_1.Start();
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _temp.Add(array[y * height + x]);
            }
        }
        sw_1.Stop();
        total_1 += sw_1.Elapsed.TotalMilliseconds;
        _temp.Clear();

        // (2) の時間測定
        sw_2.Reset();
        sw_2.Start();
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _temp.Add(jagged[y][x]);
            }
        }
        sw_2.Stop();
        total_2 += sw_2.Elapsed.TotalMilliseconds;

        // (3) の時間測定
        sw_3.Reset();
        sw_3.Start();
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _temp.Add(csarray[y, x]);
            }
        }
        sw_3.Stop();
        total_3 += sw_3.Elapsed.TotalMilliseconds;

        // (4) の時間測定
        sw_4.Reset();
        sw_4.Start();
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _temp.Add(listarray[y][x]);
            }
        }
        sw_4.Stop();
        total_4 += sw_4.Elapsed.TotalMilliseconds;

        Console.WriteLine($"{DateTime.Now:HH:mm:ss.fff}, {i}");
    }

    Console.WriteLine($"(1) 1次元配列  {total_1/loops:F4}msec");
    Console.WriteLine($"(2) ジャグ配列 {total_2/loops:F4}msec");
    Console.WriteLine($"(3) 2次元配列  {total_3/loops:F4}msec");
    Console.WriteLine($"(4) List<T>    {total_4/loops:F4}msec");
    //> (1) 1次元配列  32.3841msec
    //> (2) ジャグ配列 32.4754msec
    //> (3) 2次元配列  35.0817msec
    //> (4) List < T > 38.6112msec
}

ランダムアクセス

ランダムアクセスは要素内の適用な要素を選択し(1)～(4)全て同じ位置にアクセスし各々の時間を計測します。

public static void Main(string[] args)
{
    // 最初に少しCPUを温めておく
    double d = 0;
    for (int i = 0; i < 1000; i++)
    {
        Console.WriteLine("0");
        d += i*0.77;
    }
    Console.WriteLine(d);

    // --- データ作成と初期化 ---

    // 1024 * 1024 * 10 = 10MB分(L3キャッシュ以上)の領域を取る
    int width = 3238;
    int height = 3238;

    // (1) 1次元配列を2次元配列扱いする
    int[] array = new int[width * height];

    // (2) 2次元配列(=ジャグ配列)
    int[][] jagged = new int[height][];
    for (int i = 0; i < width; i++)
    {
        jagged[i] = new int[width];
    }

    // (3) 2次元配列(C#固有機能)
    int[,] csarray = new int[height, width];

    // (4) List<T>で2次元配列
    var listarray = new List<List<int>>();
    for (int i = 0; i < height; i++)
    {
        listarray.Add(new List<int>());
    }

    // (1) ～ (4) までの入れ物をすべて同じ値で初期化
    var r = new Random();
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            int p = r.Next();
            array[height * y + x] = p;
            jagged[y][x] = p;
            csarray[y, x] = p;
            listarray[y].Add(p);
        }
    }

    // 計測結果平均値を記録する変数
    double total_1 = 0; // (1)
    double total_2 = 0; // (2)
    double total_3 = 0; // (3)
    double total_4 = 0; // (4)

    // 時間計測用のタイマー
    var sw_1 = new Stopwatch(); // (1)
    var sw_2 = new Stopwatch(); // (2)
    var sw_3 = new Stopwatch(); // (3)
    var sw_4 = new Stopwatch(); // (4)

    // アクセス結果を記録するリスト(読み捨て用)
    var _temp = new List<int>();

    // --- ランダムアクセス ---

    // 500回の平均を取る
    int loops = 100;
    for (int i = 0; i < loops; i++)
    {
        sw_1.Reset();
        sw_2.Reset();
        sw_3.Reset();
        sw_4.Reset();
        
        _temp.Clear();

        var rand = new Random();

        // 1回あたりの試行回数
        int cnt = width * height;
        for (int p = 0; p < cnt; p++)
        {
            int x = rand.Next(0, width);
            int y = rand.Next(0, height);

            // (1)
            sw_1.Start();
            _temp.Add(array[y * height + x]);
            sw_1.Stop();

            // (2)
            sw_2.Start();
            _temp.Add(jagged[y][x]);
            sw_2.Stop();

            // (3)
            sw_3.Start();
            _temp.Add(csarray[y, x]);
            sw_3.Stop();

            // (4)
            sw_4.Start();
            _temp.Add(listarray[y][x]);
            sw_4.Stop();

        }

        Console.WriteLine($"{DateTime.Now:HH:mm:ss.fff}, {i}");

        total_1 += sw_1.Elapsed.TotalMilliseconds;
        total_2 += sw_2.Elapsed.TotalMilliseconds;
        total_3 += sw_3.Elapsed.TotalMilliseconds;
        total_4 += sw_4.Elapsed.TotalMilliseconds;
    }

    Console.WriteLine($"(1) 1次元配列  {total_1/loops:F4}msec");
    Console.WriteLine($"(2) ジャグ配列 {total_2/loops:F4}msec");
    Console.WriteLine($"(3) 2次元配列  {total_3/loops:F4}msec");
    Console.WriteLine($"(4) List<T>    {total_4/loops:F4}msec");
    //> (1) 1次元配列  1010.8107msec
    //> (2) ジャグ配列 1111.5819msec
    //> (3) 2次元配列  1039.6755msec
    //> (4) List < T > 1244.3971msec
}

長くなりましたが以上です。