Прямоугольные массивы .NET:как получить доступ в цикле?
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?
Решение
Причина, по которой один работает быстрее другого, связана с кешем процессора и способом размещения данных в памяти.
Существует два обычных способа хранения двумерных данных в одномерном адресном пространстве, либо вы можете сохранить все данные для первой строки, затем для второй строки и так далее (иначе основной порядок строк), или вы можете сделать это по столбцам (иначе основной порядок столбцов).Ниже показано, какими будут ячейки памяти для массива 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();
}
Короче говоря, вот выданные фрагменты 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
