前回の記事で紹介した2次元配列の管理クラスですが中身のデータを「1次元配列を2次元配列扱いする」か「C#固有機能の多次元配列」で行ったときの実行速度に触れましたが今回は実際に速度の違いを計測してみました。
タイトルの通り、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] |
確認環境
この実行速度計測は以下環境で確認しています。
- .NET 7 + VisualStudio2022
- BenchmarkNet 0.13.10
- Windows11 22H2
- Ryzen 5900X 3.7GHz
- 32GB メモリー
.NET 7 Release ビルドの Exe をコマンドラインから実行して速度を計測しています。
実行結果
先に実行結果を載せておきます。それぞれ 3238 x 3238 の 1048万回アクセスを試行して計測しています。
| アクセス方法 | int[ ] | int[ ][ ] | int[, ] | List<List |
|---|---|---|---|---|
| シーケンシャルアクセス(時間) | 2.259ms | 4.456ms | 5.595ms | 7.784ms |
| シーケンシャル（割合） | x1.0 | x1.97 | x2.47 | x3.44 |
| ランダムアクセス(時間) | 15.35ms | 44.58ms | 217.97ms | 32.34ms |
| ランダム（割合） | x1.0 | x2.9 | x14.19 | x2.1 |
総合的に見て1次元配列を(x, y)でアクセスするのが一番よさそうでした。
なんか C# 固有の [, ] という二次元配列はランダムアクセスでめちゃくちゃパフォーマンスが悪いですがこれどうなってるんでしょうね？
あと List クラスが .NET 7以降高速化されてるのでアクセス速度がめちゃくちゃ早くなってるみたいです。動的にサイズを変えるケースがあるなら List でもいいのかもしれません。
実行コード
ここでは速度計測に使用したコードを掲載します。
シーケンシャルアクセス
シーケンシャルアクセスは先頭から末尾までの要素を順にアクセスして要素へのアクセス時間を計測します。
using BenchmarkDotNet.Attributes; [MemoryDiagnoser] [RankColumn] public class Test1 { // 合計1048万グリッド const int WIDTH = 3238; const int HEIGHT = 3238; // (1) 1次元配列を2次元配列扱いする int[] _array; // (2) 2次元配列(=ジャグ配列) int[][] _jagged; // (3) 2次元配列(C#固有機能) int[,] _csarray; // (4) List<T>で2次元配列 List<List<int>> _listArray; [GlobalSetup] public void Setup() { // (1)のデータ構を初期化 _array = new int[WIDTH * HEIGHT]; // (2)のデータ構造を初期化 _jagged = new int[HEIGHT][]; for (int i = 0; i < WIDTH; i++) { _jagged[i] = new int[WIDTH]; } // (3)のデータ構造を初期化 _csarray = new int[HEIGHT, WIDTH]; // (4)のデータ構造を初期化 _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); } } } // (1) に対するシーケンシャルアクセス [Benchmark] public void _1_Seq() { //var temp = new List<int>(); for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { int value = _array[y * HEIGHT + x]; //temp.Add(value); } } } // (2) に対するシーケンシャルアクセス [Benchmark] public void _2_Seq() { //var temp = new List<int>(); for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { int value = _jagged[y][x]; //temp.Add(value); } } } // (3) に対するシーケンシャルアクセス [Benchmark] public void _3_Seq() { //var temp = new List<int>(); for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { int value = _csarray[y, x]; //temp.Add(value); } } } // (4) に対するシーケンシャルアクセス [Benchmark] public void _4_Seq() { //var temp = new List<int>(); for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { int value = _listArray[y][x]; //temp.Add(value); } } } } | Method | Mean | Error | StdDev | Median | Rank | Allocated | |------- |---------:|----------:|----------:|---------:|-----:|----------:| | _1_Seq | 2.259 ms | 0.0364 ms | 0.0340 ms | 2.233 ms | 1 | 2 B | | _2_Seq | 4.456 ms | 0.0063 ms | 0.0059 ms | 4.456 ms | 2 | 4 B | | _3_Seq | 5.595 ms | 0.0151 ms | 0.0134 ms | 5.593 ms | 3 | 4 B | | _4_Seq | 7.784 ms | 0.0122 ms | 0.0114 ms | 7.786 ms | 4 | 4 B |
ランダムアクセス
ランダムアクセスは要素内の適用な要素を選択し(1)～(4)全て同じ位置にアクセスし各々の時間を計測します。
[MemoryDiagnoser] [RankColumn] public class Test2 { const int WIDTH = 3238; const int HEIGHT = 3238; // (1) 1次元配列を2次元配列扱いする int[] _array; // (2) 2次元配列(=ジャグ配列) int[][] _jagged; // (3) 2次元配列(C#固有機能) int[,] _csarray; // (4) List<T>で2次元配列 List<List<int>> _listArray; // ランダムアクセスの回数 const int CNT = WIDTH * HEIGHT; // ランダムアクセス用のインデックス List<(int x, int y)> _randList = new List<(int x, int y)>(); [GlobalSetup] public void Setup() { // (1)のデータ構を初期化 _array = new int[WIDTH * HEIGHT]; // (2)のデータ構造を初期化 _jagged = new int[HEIGHT][]; for (int i = 0; i < WIDTH; i++) { _jagged[i] = new int[WIDTH]; } // (3)のデータ構造を初期化 _csarray = new int[HEIGHT, WIDTH]; // (4)のデータ構造を初期化 _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); } } // ランダムアクセス用の乱数の初期化 var rand = new Random(); for (int i = 0; i < CNT; i++) { _randList.Add((rand.Next(0, WIDTH), rand.Next(0, HEIGHT))); } } // (1) に対するランダムアクセス [Benchmark] public void _1_Rand() { //var temp = new List<int>(); foreach (var (x, y) in _randList) { int value = _array[y * HEIGHT + x]; //temp.Add(value); } } // (2) に対するランダムアクセス [Benchmark] public void _2_Rand() { //var temp = new List<int>(); foreach (var (x, y) in _randList) { int value = _jagged[y][x]; //temp.Add(value); } } // (3) に対するランダムアクセス [Benchmark] public void _3_Rand() { //var temp = new List<int>(); foreach (var (x, y) in _randList) { int value = _csarray[y, x]; //temp.Add(value); } } // (4) に対するランダムアクセス [Benchmark] public void _4_Rand() { //var temp = new List<int>(); foreach (var (x, y) in _randList) { int value = _listArray[y][x]; //temp.Add(value); } } } | Method | Mean | Error | StdDev | Rank | Allocated | |-------- |----------:|---------:|---------:|-----:|----------:| | _1_Rand | 15.35 ms | 0.255 ms | 0.226 ms | 1 | 8 B | | _2_Rand | 44.58 ms | 0.886 ms | 1.055 ms | 2 | 42 B | | _3_Rand | 217.98 ms | 3.918 ms | 3.473 ms | 4 | 168 B | | _4_Rand | 82.34 ms | 1.640 ms | 3.600 ms | 3 | 72 B |
長くなりましたが以上です。
