¿Por qué mi programa es lento cuando se repite sobre exactamente 8192 elementos?

Las siguientes pruebas se han realizado con Visual C++ compiler, ya que es utilizado por la instalación predeterminada de Qt Creator (supongo que sin bandera de optimización). Al usar GCC, no hay gran diferencia entre la versión de Mystical y mi código "optimizado". Así que la conclusión es que las optimizaciones de compiladores se encargan de la micro optimización mejor que los humanos (por fin yo). Dejo el resto de mi respuesta como referencia.

No es eficiente procesar imágenes de esta manera. Es mejor usar single matrices de dimensiones. El procesamiento de todos los píxeles se realiza en un bucle. El acceso aleatorio a los puntos se puede hacer usando:

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

En este caso particular, es mejor calcular y almacenar en caché la suma de tres grupos de píxeles horizontalmente porque se utilizan tres veces cada uno.

He hecho algunas pruebas y creo que vale la pena compartir. Cada resultado es un promedio de cinco pruebas.

Código original de user1615209:

8193: 4392 ms
8192: 9570 ms

Versión mística:

8193: 2393 ms
8192: 2190 ms

Dos pasadas usando una matriz 1D: primer paso para sumas horizontales, segundo para suma vertical y media. Dos pases de direccionamiento con tres punteros y solo incrementos como este:

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

Dos pases usando una matriz 1D y direccionando así:

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

8193: 932 ms
8192: 925 ms

El almacenamiento en caché horizontal de una pasada suma solo una fila por delante para que permanezcan en caché:

// 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

Conclusión:

• No hay beneficios de usar varios punteros y solo incrementos (pensé que habría sido más rápido)
• Almacenar sumas horizontales en caché es mejor que computándolos varias veces.
• Dos pases no es tres veces más rápido, solo dos veces.
• Es posible lograr 3.6 veces más rápido usando tanto un solo pase como almacenando en caché un resultado intermedio

Estoy seguro de que es posible hacerlo mucho mejor.

NOTA Por favor, tenga en cuenta que escribí esta respuesta para apuntar a problemas de rendimiento general en lugar del problema de caché explicado en la excelente respuesta de Mystical. Al principio era sólo pseudo código. Me pidieron que hacer pruebas en los comentarios... Aquí hay una versión completamente refactorizada con pruebas.

El orden de acceso al elemento cuidado todavía quedan unos pocos frutos. La acumulación se puede hacer de una manera que al iterar a la derecha solo 3 nuevos valores necesitan ser recuperados de la memoria y acumulados. El truco es saber cómo soltar la columna más a la izquierda; al agregar una nueva columna recuerde su valor hasta que salga de la ventana de muestreo.

El costo antes: 9 lectura, 9 adición, 1 división El costo después de: 3 leído, 3 adición, 1 división

Piensa en el ventana de muestreo como caja de 3x3 donde se realiza un seguimiento de cada columna (1x3) por separado. Acumula una nueva columna y deja caer la más antigua.

La división es una instrucción de alta latencia, por lo que podría ser ventajoso ocultar la latencia, pero antes de ir allí, la salida del compilador debe inspeccionarse si la división por constante se elude y si el desenrollado del bucle (por el compilador) ya realiza alguna compensación de latencia.

Pero después de la optimización más dramática de usar la caché correctamente son cosas menores.