Почему моя программа работает медленно, когда зацикливается ровно на 8192 элемента?

Вот выдержка из рассматриваемой программы. Матрица img[][] имеет размер SIZE × SIZE и инициализируется в:

img[j][i] = 2 * j + i

Затем вы делаете матрицу res[][]и каждое поле здесь сделано как среднее из 9 полей вокруг него в матрице img. Граница оставлена ​​на 0 для простоты.

for(i=1;i<SIZE-1;i++)
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
for(k=-1;k<2;k++)
for(l=-1;l<2;l++)
res[j][i] += img[j+l][i+k];
res[j][i] /= 9;
}

Это все, что есть в программе. Для полноты картины вот что предшествует. Код не приходит после. Как видите, это просто инициализация.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
img[j][i] = (2*j+i)%8196;

В основном, эта программа работает медленно, когда SIZE кратен 2048, например, время выполнения:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Компилятор GCC.
Из того, что я знаю, это из-за управления памятью, но я не очень много знаю об этом предмете, поэтому я спрашиваю здесь.

Также, как это исправить, было бы неплохо, но если бы кто-то мог объяснить это время выполнения, я уже был бы достаточно счастлив.

Я уже знаю о malloc / free, но проблема не в объеме используемой памяти, а в просто времени выполнения, поэтому я не знаю, как это могло бы помочь.

712

Решение

Разница вызвана той же проблемой супер-выравнивания из следующих связанных вопросов:

Но это только потому, что есть еще одна проблема с кодом.

Начиная с оригинального цикла:

for(i=1;i<SIZE-1;i++)
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
for(k=-1;k<2;k++)
for(l=-1;l<2;l++)
res[j][i] += img[j+l][i+k];
res[j][i] /= 9;
}

Сначала обратите внимание, что две внутренние петли тривиальны. Их можно развернуть следующим образом:

for(i=1;i<SIZE-1;i++) {
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
res[j][i] += img[j-1][i-1];
res[j][i] += img[j  ][i-1];
res[j][i] += img[j+1][i-1];
res[j][i] += img[j-1][i  ];
res[j][i] += img[j  ][i  ];
res[j][i] += img[j+1][i  ];
res[j][i] += img[j-1][i+1];
res[j][i] += img[j  ][i+1];
res[j][i] += img[j+1][i+1];
res[j][i] /= 9;
}
}

Так что остается два внешних цикла, которые нас интересуют.

Теперь мы видим, что проблема в том же вопросе: Почему порядок циклов влияет на производительность при итерации по двумерному массиву?

Вы перебираете матрицу по столбцам, а не по строкам.


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

for(j=1;j<SIZE-1;j++) {
for(i=1;i<SIZE-1;i++) {
res[j][i]=0;
res[j][i] += img[j-1][i-1];
res[j][i] += img[j  ][i-1];
res[j][i] += img[j+1][i-1];
res[j][i] += img[j-1][i  ];
res[j][i] += img[j  ][i  ];
res[j][i] += img[j+1][i  ];
res[j][i] += img[j-1][i+1];
res[j][i] += img[j  ][i+1];
res[j][i] += img[j+1][i+1];
res[j][i] /= 9;
}
}

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


Core i7 920 @ 3,5 ГГц

Оригинальный код:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Взаимозаменяемые внешние петли:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
900

Другие решения

Следующие тесты были выполнены с компилятором Visual C ++, так как он используется при установке по умолчанию Qt Creator (я думаю, без флага оптимизации). При использовании GCC нет большой разницы между версией Mystical и моим «оптимизированным» кодом. Итак, вывод заключается в том, что оптимизация компилятора заботится о микрооптимизации лучше, чем люди (наконец-то я). Я оставляю остаток моего ответа для справки.


Неэффективно обрабатывать изображения таким образом. Лучше использовать одномерные массивы. Обработка всех пикселей выполняется за один цикл. Произвольный доступ к точкам может быть выполнен с использованием:

pointer + (x + y*width)*(sizeOfOnePixel)

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

Я сделал несколько тестов, и я думаю, что стоит поделиться. Каждый результат в среднем состоит из пяти тестов.

Оригинальный код от пользователя1615209:

8193: 4392 ms
8192: 9570 ms

Мистическая версия:

8193: 2393 ms
8192: 2190 ms

Два прохода с использованием одномерного массива: первый проход для горизонтальных сумм, второй для вертикальной суммы и среднего.
Двухпроходная адресация с тремя указателями и только такими приращениями:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Два прохода с использованием одномерного массива и адресации следующим образом:

for(i=SIZE;i<totalSize-SIZE;i++){
resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Горизонтальные кеширующие за один проход суммы всего на одну строку впереди, поэтому они остаются в кеше

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
// Compute horizontal sum for next line
hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
// Final result
resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Заключение:

  • Никаких преимуществ от использования нескольких указателей и просто приращений (я думал, что это было бы быстрее)
  • Кэшировать горизонтальные суммы лучше, чем вычислять их несколько раз.
  • Два прохода не в три раза быстрее, только в два раза.
  • Можно достичь в 3,6 раза быстрее, используя как один проход, так и кеширование промежуточного результата.

Я уверен, что можно сделать намного лучше.

НОТА
Пожалуйста, обратите внимание, что я написал этот ответ для общих проблем с производительностью, а не для проблемы с кешем, описанной в превосходном ответе Mystical. В начале это был просто псевдокод. Меня попросили сделать тесты в комментариях … Вот полностью переработанная версия с тестами.

53

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

Стоимость до: 9 прочитанных, 9 дополнений, 1 деление
Стоимость после: 3 чтения, 3 сложения, 1 деление

Думайте об окне выборки как окошке 3х3, где вы отслеживаете каждый столбец (1х3) отдельно. Накопите новый столбец и отбросьте самый старый.

Деление — это команда с высокой задержкой, поэтому может быть выгодно скрыть задержку, но перед переходом туда следует проверить выходные данные компилятора, если исключено деление на константу и если разворачивание цикла (компилятором) уже выполняет некоторую компенсацию задержки.

Но после самой драматической оптимизации правильного использования кеша это действительно мелочи.

-1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector