Прямоугольные массивы .NET: как получить доступ в цикле?

Чтобы быть уверенным, вам следует сравнить свои конкретные обстоятельства.

Вы могли бы подумать, что для прямоугольных массивов (т.е. непрерывно выделенной памяти) не будет никакой разницы, НО согласно этому Статья MSDN есть разница:

You can get even better results by converting a multidimensional array into a single-dimensional array. If you don't mind the syntax, this can be trivial; just use one index as an offset. For example, the following declares a single-dimensional array to be used as a two-dimensional array:

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

For indexing the elements of this array, use the following offset:

myArray[row * COLUMN_DIM + column];

This will undoubtedly be faster than an equivalent jagged or rectangular array.

Итак, я провел тест, и результаты показали, что доступ к arr1 стал в три раза быстрее.

Причина, по которой один быстрее другого, связана с кешем процессора и способом размещения данных в памяти.

Существует два обычных способа хранения двумерных данных в одномерном адресном пространстве: либо вы можете сохранить все данные для первой строки, затем для второй строки и так далее (также известного как основной порядок строк), либо вы можете сделать это по столбцам (иначе основной порядок столбца). Ниже показано расположение памяти для массива 3x3 для обоих этих вариантов.

Ряды:

1 2 3
4 5 6
7 8 9

Столбцы:

1 4 7
2 5 8
3 6 9

Когда вы обращаетесь к одной области памяти, в кеш загружается вся строка кэша (которая может быть от 8 до 512 байт, согласно Википедии). Таким образом, если вы получите доступ к следующей ячейке памяти, она уже будет в кеше. Таким образом, последовательный доступ к памяти может быть намного быстрее, чем переход по адресному пространству. Таким образом, с большими двумерными массивами может быть значительная разница в скорости между выбором строк или столбцов в качестве переменной внутреннего цикла.

Очень интересно, я никогда не переставал думать, что может быть такая огромная разница, просто обращаясь к индексам массива «непоследовательно». Я сам попробовал и также обнаружил, что в следующем коде второй цикл занимает от 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();
}

Вкратце, вот сгенерированные фрагменты кода IL для цикла X by Y и Y by X.

Исходный код до цикла,

.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 в чем-то похож. Основное различие, которое я могу заметить, заключается в том, что в первом цикле удается использовать stloc и ldloc для позиций 2 и 3 для первого массива и переменной индекса X. К тому времени, когда он дошел до второго цикла, он израсходовал максимальный стек и, таким образом, использовал инструкции stloc.s и ldloc.s. Я считаю, что это разница между ссылками на переменные в стеке и в куче, что способствует снижению производительности.

Теперь, если вы поменяете местами порядок, в котором тестируются циклы, так, чтобы цикл Y на X запускался первым для доступа к ссылкам на стек, вы увидите, что временные интервалы меняются на противоположные.

ОБНОВЛЕНИЕ: я ошибался, ссылаясь на адреса стека или кучи. Просто кажется, что первые четыре переменные в методе более эффективны для ссылки с помощью специальных кодов операций stloc.0, 1, 3, 4 и ldloc.0, 1, 3, 4.

http://weblogs.asp.net/mnolton/archive/2004/01/09/48992.aspx