Aquí está el extracto del programa en cuestión. La matriz img[][]
tiene el tamaño SIZE × SIZE, y se inicializa en:
img[j][i] = 2 * j + i
Luego, haces una matriz res[][]
, y cada campo aquí está hecho para ser el promedio de los 9 campos a su alrededor 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. Ningún código viene después. Como puede ver, es solo 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 SIZE es un 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é demasiado sobre ese tema, por lo que pregunto aquí.
Además, cómo solucionar esto sería bueno, pero si alguien pudiera explicar estos tiempos de ejecución, ya estaría lo suficientemente feliz.
Ya conozco malloc / free, pero el problema no es la cantidad de memoria utilizada, es simplemente el tiempo de ejecución, por lo que no sé cómo ayudaría eso.
fuente
Respuestas:
La diferencia es causada por el mismo problema de superalineación de las siguientes preguntas relacionadas:
Pero eso es solo porque hay otro problema con el código.
A partir del bucle original:
Primero note que los dos bucles internos son triviales. Se pueden desenrollar de la siguiente manera:
Eso deja los dos bucles externos que nos interesan.
Ahora podemos ver que el problema es el mismo en esta pregunta: ¿Por qué el orden de los bucles afecta el rendimiento al iterar sobre una matriz 2D?
Está iterando la matriz a nivel de columna en lugar de a nivel de fila.
Para resolver este problema, debe intercambiar los dos bucles.
Esto elimina por completo todo el acceso no secuencial, por lo que ya no obtienes ralentizaciones aleatorias en grandes potencias de dos.
Core i7 920 @ 3.5 GHz
Código original:
Bucles exteriores intercambiados:
fuente
Las siguientes pruebas se han realizado con el compilador de Visual C ++, ya que es utilizado por la instalación predeterminada de Qt Creator (supongo que sin bandera de optimización). Cuando uso GCC, no hay una 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 micro optimización mejor que los humanos (yo por fin). Dejo el resto de mi respuesta como referencia.
No es eficiente procesar imágenes de esta manera. Es mejor usar matrices de dimensión única. El procesamiento de todos los píxeles se realiza en un bucle. El acceso aleatorio a los puntos se puede hacer usando:
En este caso particular, es mejor calcular y almacenar en caché la suma de tres grupos de píxeles horizontalmente porque se usan 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 por usuario1615209:
Versión mística:
Dos pases utilizando una matriz 1D: primer pase para sumas horizontales, segundo para suma vertical y promedio. Direccionamiento de dos pasos con tres punteros y solo incrementos como este:
Dos pasadas usando una matriz 1D y direccionando así:
Una pasada almacenando sumas horizontales solo una fila por delante para que permanezcan en la caché:
Conclusión:
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 solo un pseudocódigo. Me pidieron que hiciera pruebas en los comentarios ... Aquí hay una versión completamente refactorizada con pruebas.
fuente