.NET長方形配列：ループでアクセスする方法
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
基本的に、これを行うには2つの方法があります：
for (int x = 0; x < UPPER_X; x++)
for (int y = 0; y < UPPER_Y; y++)
{
arr1[x, y] = get_value();
arr2[y, x] = get_value();
}
唯一の違いは、内側のループでどの変数を変更するかです（最初または2番目）。結果は言語によって異なると聞きました。
.NETの正しい順序は？
解決
一方が他方のプロセッサよりも高速である理由は、プロセッサのキャッシュに関係し、データがメモリに配置される方法です。
1次元のアドレス空間に2次元データを保存するには、通常、2つの方法があります。最初の行、2番目の行などのすべてのデータを保存できます（別名 メジャーオーダーを行 ）、または列（別名< href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> 列の主要順序 ）。以下は、これらの両方のオプションの3x3アレイのメモリ位置です。
行：
1 2 3
4 5 6
7 8 9
列：
1 4 7
2 5 8
3 6 9
1つのメモリロケーションにアクセスすると、キャッシュライン全体（Wikipediaによると8〜512バイト）がキャッシュにロードされます。そのため、次のメモリロケーションにアクセスすると、すでにキャッシュ内にあります。したがって、アドレス空間を飛び回るよりも、メモリに順番にアクセスする方がはるかに高速です。したがって、大きな2次元配列では、行または列を内部ループ変数として選択する際に、大幅な速度差が生じる可能性があります。
他のヒント
確実に特定の状況をベンチマークする必要があります。
長方形の配列（つまり、連続して割り当てられたメモリ）には違いはないと思うでしょうが、この MSDNの記事には違いがあります：
あなたはさらに良い結果を得ることができます 多次元配列の変換 一次元配列に。もし あなたは構文を気にしません、これはすることができます 些細な; 1つのインデックスを オフセット。たとえば、次の 一次元配列を宣言します 2次元配列として使用される：
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
この要素のインデックス作成用 配列、次のオフセットを使用します：
myArray[row * COLUMN_DIM + column];
これは間違いなく高速になります 同等のギザギザまたは長方形 配列。
だからベンチマークを行った結果、arr1へのアクセスが3倍高速になりました。
非常に興味深いのは、配列インデックスに「非順次」アクセスするだけで、このような大きな違いが生じる可能性があると考えることを止めたことはありません。自分で試してみたところ、次のコードでは2〜3倍の時間がかかる2番目のループが見つかりました。
// Hmmm, how to insert blank lines in the code formatter???
static void Main(string[] args)
{
Stopwatch timer = new Stopwatch();
int arraySize = 10000;
// First array, access X by Y
int[,] xbyy = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
xbyy[x, y] = 15;
}
timer.Stop();
TimeSpan duration = timer.Elapsed;
string realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("X by Y took " + realTimeFormat);
// Seecond array, access Y by X
int[,] ybyx = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
ybyx[y, x] = 15;
}
timer.Stop();
duration = timer.Elapsed;
realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("Y by X took " + realTimeFormat);
Console.ReadLine();
}
簡潔にするために、X by YループおよびY by XループのILスニペットを以下に示します。
ループする前の初期コード
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
// Code size 290 (0x122)
.maxstack 4
.locals init ([0] class [System]System.Diagnostics.Stopwatch timer,
[1] int32 arraySize,
[2] int32[0...,0...] xbyy,
[3] int32 x,
[4] int32 y,
[5] valuetype [mscorlib]System.TimeSpan duration,
[6] string realTimeFormat,
[7] int32[0...,0...] ybyx,
[8] int32 V_8,
[9] int32 V_9)
IL_0000: newobj instance void [System]System.Diagnostics.Stopwatch::.ctor()
IL_0005: stloc.0
IL_0006: ldc.i4 0x2710
IL_000b: stloc.1
XをYでループ
IL_000c: ldloc.1
IL_000d: ldloc.1
IL_000e: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0013: stloc.2
IL_0014: ldloc.0
IL_0015: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_001a: ldc.i4.0
IL_001b: stloc.3
IL_001c: br.s IL_003d
IL_001e: ldc.i4.0
IL_001f: stloc.s y
IL_0021: br.s IL_0034
IL_0023: ldloc.2
IL_0024: ldloc.3
IL_0025: ldloc.s y
IL_0027: ldc.i4.s 15
IL_0029: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_002e: ldloc.s y
IL_0030: ldc.i4.1
IL_0031: add
IL_0032: stloc.s y
IL_0034: ldloc.s y
IL_0036: ldloc.1
IL_0037: blt.s IL_0023
IL_0039: ldloc.3
IL_003a: ldc.i4.1
IL_003b: add
IL_003c: stloc.3
IL_003d: ldloc.3
IL_003e: ldloc.1
IL_003f: blt.s IL_001e
IL_0041: ldloc.0
YをXでループ
IL_0090: ldloc.1
IL_0091: ldloc.1
IL_0092: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0097: stloc.s ybyx
IL_0099: ldloc.0
IL_009a: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_009f: ldc.i4.0
IL_00a0: stloc.s V_8
IL_00a2: br.s IL_00c7
IL_00a4: ldc.i4.0
IL_00a5: stloc.s V_9
IL_00a7: br.s IL_00bc
IL_00a9: ldloc.s ybyx
IL_00ab: ldloc.s V_9
IL_00ad: ldloc.s V_8
IL_00af: ldc.i4.s 15
IL_00b1: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_00b6: ldloc.s V_9
IL_00b8: ldc.i4.1
IL_00b9: add
IL_00ba: stloc.s V_9
IL_00bc: ldloc.s V_9
IL_00be: ldloc.1
IL_00bf: blt.s IL_00a9
IL_00c1: ldloc.s V_8
IL_00c3: ldc.i4.1
IL_00c4: add
IL_00c5: stloc.s V_8
IL_00c7: ldloc.s V_8
IL_00c9: ldloc.1
IL_00ca: blt.s IL_00a4
IL_00cc: ldloc.0
ILロジックフローは多少似ています。私が観察できる主な違いは、最初のループが、最初の配列とXインデックス変数の位置2と3にstlocとldlocを使用することです。 2番目のループに到達するまでに、maxstackを使い果たしたため、stloc.sおよびldloc.s命令を使用していました。これは、スタック上の変数とヒープ上の変数の参照の違いであり、パフォーマンスの低下に寄与すると考えています。
ここで、ループがテストされる順序を入れ替えて、YからXループが最初に実行されてスタック参照にアクセスする場合、タイミング期間が逆になることがわかります。
UPDATE：スタックまたはヒープアドレスの参照について間違っていました。メソッドの最初の4つの変数は、専用のstloc.0、1、3、4およびldloc.0、1、3、4オペコードを使用して参照する方が効率的であると思われます。
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
