Вот выдержка из рассматриваемой программы. Матрица 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, но проблема не в объеме используемой памяти, а в просто времени выполнения, поэтому я не знаю, как это могло бы помочь.
Разница вызвана той же проблемой супер-выравнивания из следующих связанных вопросов:
Но это только потому, что есть еще одна проблема с кодом.
Начиная с оригинального цикла:
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
Следующие тесты были выполнены с компилятором 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
Заключение:
Я уверен, что можно сделать намного лучше.
НОТА
Пожалуйста, обратите внимание, что я написал этот ответ для общих проблем с производительностью, а не для проблемы с кешем, описанной в превосходном ответе Mystical. В начале это был просто псевдокод. Меня попросили сделать тесты в комментариях … Вот полностью переработанная версия с тестами.
Порядок доступа к элементам позаботился о том, что осталось еще несколько низко висящих фруктов. Накопление может быть сделано таким образом, что при итерации вправо только 3 новых значения должны быть извлечены из памяти и накоплены. Хитрость заключается в том, чтобы уметь отбрасывать крайний левый столбец; при добавлении нового столбца помните его значение, пока оно не выйдет из окна выборки.
Стоимость до: 9 прочитанных, 9 дополнений, 1 деление
Стоимость после: 3 чтения, 3 сложения, 1 деление
Думайте об окне выборки как окошке 3х3, где вы отслеживаете каждый столбец (1х3) отдельно. Накопите новый столбец и отбросьте самый старый.
Деление — это команда с высокой задержкой, поэтому может быть выгодно скрыть задержку, но перед переходом туда следует проверить выходные данные компилятора, если исключено деление на константу и если разворачивание цикла (компилятором) уже выполняет некоторую компенсацию задержки.
Но после самой драматической оптимизации правильного использования кеша это действительно мелочи.