.NET Rectangular Arrays：如何在循环中访问？
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
基本上你有两种方法可以做到这一点：
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();
}
唯一的区别是内循环中要更改的变量：第一个或第二个。我听说结果因语言而异。
.NET的正确顺序是什么？
解决方案
一个比另一个更快的原因与处理器的缓存有关，以及数据在内存中的布局方式。
有两种常规方法可以将二维数据存储在一维地址空间中，您可以存储第一行的所有数据，然后存储第二行，依此类推（也就是 行主要订单 ），或者您可以按列（也就是< a 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
当您访问一个内存位置时，整个缓存行（根据维基百科可以在8到512字节之间）被加载到缓存中。因此，如果您访问下一个内存位置，它将已经在缓存中。因此，顺序访问存储器比在地址空间中跳转要快得多。因此，对于大型二维数组，选择行或列作为内部循环变量之间可能存在显着的速度差异。
其他提示
您应该确定您的具体情况。
您会认为矩形阵列（即连续分配的内存）没有区别，但是根据这个 MSDN文章存在差异：
你可以获得更好的结果 转换多维数组 成一维数组。如果 你不介意语法，这可以 不重要的;只需使用一个索引作为 偏移。例如，以下内容 声明一维数组 用作二维数组：
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
用于索引此元素 数组，使用以下偏移量：
myArray[row * COLUMN_DIM + column];
这无疑会比这更快 等效的锯齿状或矩形 阵列。
所以我做了基准测试，结果是对arr1的访问速度提高了三倍。
非常有趣，我从未停下来考虑仅仅通过“非顺序”访问数组索引就可以产生如此巨大的差异。我自己试了一下，还发现下面的代码让第二个循环的时间长了2-3倍：
// 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
按Y循环X
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
用X循环Y
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逻辑流程有点类似。我可以观察到的主要区别是第一个循环设法将stloc和ldloc用于第一个数组和X索引变量的位置2和3。到第二个循环时，它已经消耗了maxstack，因此使用了stloc.s和ldloc.s指令。我相信这是引用堆栈上的变量与堆上的变量之间的区别，并导致性能降低。
现在，如果您交换测试循环的顺序，以便首先运行Y by X循环来访问堆栈引用，您将看到计时持续时间被反转。
更新：我错误地引用了堆栈或堆地址。看起来方法中的前四个变量使用专用的stloc.0,1,3,4和ldloc.0,1,3,4操作码更有效率。
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
