Самая быстрая адресация массива

Question

Я выполняю код анализа изображения в массиве, хранящем информацию об изображении. К сожалению, код очень тяжелый и занимает в среднем 25 секунд, чтобы пройти через один кадр. Основная проблема, которую я вижу, это адресация массива. Какой самый быстрый для запуска через 2d массив и есть ли какие-либо различия в

по горизонтали, затем по вертикали

for (int y = 0; y < array.Length; ++y)
    for (int x = 0; x < array[].Length; ++x)
        //Code using array[y][x]

а по вертикали то по горизонтали?

for (int x = 0; x < array[].Length; ++x)
    for (int y = 0; y < array.Length; ++y)
        //Code using array[y][x]

Кроме того, я старался избегать прямой адресации и вместо этого использовал указатели.

for (int y = 0; y < array.Length; ++y)
    int* ptrArray = (int*)array[0];
    for (int x = 0; x < array[].Length; ++x, ++ptrArray)
        //Code using ptrArray for array[y][x]

или

for (int x = 0; x < array[].Length; ++x)
    int* ptrArray = (int*)array[0];
    for (int y = 0; y < array.Length; ++y, ptrArray += array[].Length)
        //Code using ptrArray for array[y][x]

Любая помощь очень ценится. Max

Answer 1

Самое важное правило - это все теория, пока вы не профилируете. Я не верю в тех, кто настаивает на том, что профилирование - это все (без какой-либо теории вы не лучше, чем Культист-грузчик, который кладет кокосы на уши и ждет прибытия самолета), но ваша теория всегда может быть неправильной или неполной, поэтому профилирование имеет решающее значение.

Как правило, мы хотим, чтобы внутреннее сканирование выполнялось горизонтально (с точки зрения массива, а не изображения, хотя для большинства форматов это одно и то же). Причина в том, что с массивом вроде:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

Это будет выложено как:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Вы хотите сканировать по смежным блокам, которые можно загружать в кеши ЦП и затем использовать целиком, а не сканировать от блока к блоку и требовать регулярного изменения содержимого кэша ЦП.

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

Другая вещь - это разница между 2-мерным массивом byte[,], а не массивом массивов byte[][], и ваш комментарий в вашем вопросе "array [y] [x]" заставляет меня задуматься, возможно, вы используете , С первым для получения arr [1,2] логика:

1. Проверить границы
2. Расчет позиции (простая быстрая арифметика)
3. Получить значение.

С последним логика:

1. Проверить границы
2. Получить массив через указатель.
3. Проверить границы
4. Получить значение.

Существует также менее хорошая частота попадания в кэш-память. Последний имеет преимущества, когда нужны «зубчатые» конструкции, но здесь это не так. 2D почти всегда быстрее, чем массив массивов.

Вещи, которые я не вижу, которые могут помочь, но я бы обязательно попробовал их в вашей ситуации:

Вы можете получить импульс от выполнения своей 1d <=> 2d логики. Имейте одномерный массив, где idx = y * width + x. Это не должно иметь заметного значения, но стоит попробовать.

Оптимизации действительно пытаются поднять вызовы на .Length и пропустить ненужную проверку границ, поэтому вы можете обнаружить, что подъем вручную и переключение на арифметику указателей ничего не дает, но в случае, когда вам действительно нужно сократить время это, безусловно, стоит профилировать.

Наконец-то. Вы рассказали, как быстро ваш код сканирует массив и ничего не делает? Возможно, другая часть кода - это настоящее узкое место, и вы исправляете не то.

Answer 2

Один из вариантов - использовать обратную петлю (начните for() loop с array.Length до 0)

Это ускорит процесс abit.

, например,

for (int x = array[].Length-1; x >= 0; --x)
    int* ptrArray = (int*)array[0];
    for (int y = array.Length-1; y >= 0 ; --y, ptrArray += array[].Length)
        //Code using ptrArray for array[y][x]

Answer 3

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

var sw = new Stopwatch();
sw.Start();
ExecuteMyCode();
sw.Stop();
Console.WriteLine("Time: " + sw.Elapsed);

Вы можете ускорить обработку, используя многопоточную конструкцию , например Parallel.ForEach. Это будет хорошо работать, если код в вашем цикле избегает зависимостей между циклами цикла.

Answer 4

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

Обычно это строка вашего изображения.Обратите внимание, что в прямоугольных массивах вы должны сделать это последним индексом: array[y,x].

В этой статье предполагается, что встроенные прямоугольные массивы C # (с несколькими индексами) работают довольно медленно.Я читал это раньше, но это единственная ссылка, которую я получил.Я бы начал с линейного массива и рассчитывал смещение один раз для каждой строки.Неуправляемый поможет вам только в действительно тривиальных случаях.

Если один кадр занимает 25 секунд, то это либо huuuuge, либо вы выполняете очень сложную обработку.В этом случае интересно потратить усилия на оптимизацию доступа к памяти, если вы получаете доступ ко многим входным пикселям для каждого выходного пикселя.

Answer 5

Если это возможно, попробуйте перераспределить ваш массив так, чтобы первое измерение было меньше, чем второе.Это резко ускорило бы ситуацию.Другое решение - перераспределить данные в одномерном массиве, как было предложено выше.

Answer 6

Ты можешь быть небезопасным? Указатель. Проблема с массивом состоит в том, что у вас ЕЩЕ будут проверки границ при каждом доступе. Указатели удаляют это. Обратите внимание, что это полностью поддерживается C #, но вам нужно поместить его в небезопасный блок. Это также означает, что вы должны быть в состоянии выполнить небезопасный код, что не всегда является данностью.

http://msdn.microsoft.com/en-us/library/28k1s2k6.aspx

имеет пример кода.