¿Por qué mi programa es lento cuando recorre exactamente 8192 elementos?

Aquí está el extracto del programa en cuestión. La matriz img[][]tiene el tamaño TAMAÑO × TAMAÑO y se inicializa en:

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

Luego, creas una matriz res[][], y cada campo aquí se convierte en el promedio de los 9 campos que lo rodean en la matriz img. El borde se deja en 0 por simplicidad.

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;
}

Eso es todo lo que hay en el programa. Para completar, esto es lo que viene antes. No viene ningún código después. Como puede ver, es solo una inicialización.

#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;

Básicamente, este programa es lento cuando TAMAÑO es múltiplo de 2048, por ejemplo, los tiempos de ejecución:

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

El compilador es GCC. Por lo que sé, esto se debe a la gestión de la memoria, pero realmente no sé mucho sobre ese tema, por eso pregunto aquí.

También sería bueno cómo solucionar este problema, pero si alguien pudiera explicar estos tiempos de ejecución, ya estaría bastante feliz.

Ya conozco malloc/free, pero el problema no es la cantidad de memoria utilizada, es simplemente el tiempo de ejecución, así que no sé cómo ayudaría eso.

Sep 04 '12 20:09

Las siguientes pruebas se realizaron con el compilador de Visual C++ tal como lo utiliza la instalación predeterminada de Qt Creator (supongo que sin indicador de optimización). Cuando uso GCC, no hay gran diferencia entre la versión de Mystical y mi código "optimizado". Entonces, la conclusión es que las optimizaciones del compilador se encargan de la microoptimización mejor que los humanos (yo al fin). Dejo el resto de mi respuesta como referencia.

No es eficiente procesar imágenes de esta manera. Es mejor utilizar matrices de una sola dimensión. El procesamiento de todos los píxeles se realiza en un solo bucle. El acceso aleatorio a los puntos se puede realizar mediante:

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 compartirlas. Cada resultado es un promedio de cinco pruebas.

Código original del usuario1615209:

8193: 4392 ms
8192: 9570 ms

La versión de Mystical:

8193: 2393 ms
8192: 2190 ms

Dos pasadas usando una matriz 1D: la primera pasada para sumas horizontales, la segunda para suma vertical y promedio. Direccionamiento de dos pasos 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 direccionándose 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

Una pasada de almacenamiento en caché suma las sumas horizontales solo una fila por delante para que permanezcan en el 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 en caché sumas horizontales es mejor que calcularlas varias veces.
• Dos pasadas no son tres veces más rápidas, sólo dos veces.
• Es posible lograr 3,6 veces más rápido utilizando una sola pasada y almacenando en caché un resultado intermedio.

Estoy seguro de que es posible hacerlo mucho mejor.

NOTA Tenga en cuenta que escribí esta respuesta para abordar problemas generales de rendimiento en lugar del problema de caché explicado en la excelente respuesta de Mystical. Al principio era sólo un pseudocódigo. Me pidieron que hiciera pruebas en los comentarios... Aquí hay una versión completamente refactorizada con pruebas.

Sep 04 '2012 17:09 bokan