Почему моя программа работает медленно при обходе ровно 8192 элементов?

Вопрос был о производительности обработки изображений, и ниже представлены результаты тестов, проведённых с компилятором Visual C++, который используется в стандартной установке Qt Creator (предполагаю, без флагов оптимизации). При использовании GCC значительной разницы между версией Mystical и моим "оптимизированным" кодом не обнаружено. Вывод таков: оптимизации компилятора лучше справляются с микрооптимизациями, чем люди (по крайней мере, чем я). Остальную часть ответа оставляю для справки.

Избытком памяти не следует обрабатывать изображения подобным образом. Лучше использовать одномерные массивы. Обработка всех пикселей выполняется в одном цикле. Доступ к точкам можно осуществлять следующим образом:

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

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

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

Исходный код от пользователя user1615209:

8193: 4392 мс
8192: 9570 мс

Версия Mystical:

8193: 2393 мс
8192: 2190 мс

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

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 мс
8192: 974 мс

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

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

Результаты:

8193: 932 мс
8192: 925 мс

Один проход, кэшируя горизонтальные суммы только на одну строку вперёд, чтобы они оставались в кэше:

// Горизонтальные суммы для первых двух строк
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Остальная часть вычислений
for(;i<totalSize;i++){
    // Вычисление горизонтальной суммы для следующей строки
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Финальный результат
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

Результаты:

8193: 599 мс
8192: 652 мс

Выводы:

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

Уверен, что можно добиться ещё больших результатов.

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