Прямоугольные массивы .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

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

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

Ряды:

1 2 3
4 5 6
7 8 9

Колонки:

1 4 7
2 5 8
3 6 9

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

Answer 3

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

Answer 4

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