Почему моя программа работает медленно, когда зацикливается ровно на 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, но проблема не в объеме используемой памяти, а в просто времени выполнения, поэтому я не знаю, как это могло бы помочь.

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

• Почему транспонирование матрицы 512x512 намного медленнее, чем транспонирование матрицы 513x513?
• Умножение матриц: небольшая разница в размере матрицы, большая разница во времени

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

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

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

Вывод:

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

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

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