.net - .NET 矩形数组：如何循环访问？

Question

基本上你有两种方法可以做到这一点：

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 的正确顺序是什么？

Answer 1

您应该确定您的特定情况。

您会认为矩形数组（即连续分配的内存）没有区别，但是根据这篇MSDN 文章有区别：

通过将多维数组转换为一维数组，您可以获得更好的结果。如果您不介意语法，这可能是微不足道的；只需使用一个索引作为偏移量。例如，以下声明一个单维数组用作二维数组：

double[] myArray = new double[ROW_DIM * COLUMN_DIM];

要索引此数组的元素，请使用以下偏移量：

myArray[row * COLUMN_DIM + column];

这无疑会比等效的锯齿状或矩形阵列更快。

Answer 2

一个比另一个快的原因与处理器的缓存以及数据在内存中的布局方式有关。

将二维数据存储在一维地址空间中有两种常规方法，您可以存储第一行的所有数据，然后是第二行，依此类推（又名行主要顺序），或者您可以按列（又名列主要顺序）来完成。下面是这两个选项的 3x3 阵列的内存位置。

行：

1 2 3
4 5 6
7 8 9

列：

1 4 7
2 5 8
3 6 9

当您访问一个内存位置时，整个缓存行（根据 Wikipedia 可以在 8 到 512 个字节之间）被加载到缓存中。因此，如果您访问下一个内存位置，它将已经在缓存中。因此，顺序访问内存比在地址空间中跳转要快得多。因此，对于大型二维数组，在选择行或列作为内部循环变量之间可能存在显着的速度差异。

Answer 3

所以我做了基准测试，结果是访问 arr1 快了三倍。

Answer 4

非常有趣，我从来没有停下来考虑过，仅仅通过“非顺序”访问数组索引就可以产生如此巨大的差异。我自己试了一下，还发现以下代码的第二个循环要长 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 用于第一个数组的位置 2 和 3 以及 X 索引变量。到第二个循环时，它已经消耗了 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