¿Por qué mi progtwig es lento cuando se repiten exactamente 8192 elementos?

Aquí está el extracto del progtwig 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, crea 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 queda 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 para el progtwig. Para completar, aquí está lo que viene antes. Ningún código viene 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 progtwig 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 comstackdor es GCC. Por lo que sé, esto se debe a la administración de la memoria, pero realmente no sé mucho sobre ese tema, y ​​es por eso que estoy preguntando aquí.

También la forma de solucionar esto sería agradable, pero si alguien pudiera explicar estos tiempos de ejecución, ya estaría contento.

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

La diferencia está causada por el mismo problema de súper alineación de las siguientes preguntas relacionadas:

  • ¿Por qué la transposición de una matriz de 512×512 es mucho más lenta que la transposición de una matriz de 513×513?
  • Multiplicación de matriz: pequeña diferencia en el tamaño de la matriz, gran diferencia en los tiempos

Pero eso es solo porque hay otro problema con el código.

A partir del bucle original:

 for(i=1;i 

Primero note que los dos bucles internos son triviales. Se pueden desenrollar de la siguiente manera:

 for(i=1;i 

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 en forma de columna en lugar de hacerlo en filas.


Para resolver este problema, debe intercambiar los dos bucles.

 for(j=1;j 

Esto elimina por completo el acceso no secuencial, por lo que ya no se obtienen ralentizaciones aleatorias en grandes potencias de dos.


Core i7 920 @ 3.5 GHz

Código original:

 8191: 1.499 seconds 8192: 2.122 seconds 8193: 1.582 seconds 

Outer-Loops intercambiados:

 8191: 0.376 seconds 8192: 0.357 seconds 8193: 0.351 seconds 

Las siguientes pruebas se han realizado con el comstackdor de Visual C ++ tal como lo utiliza la instalación predeterminada de Qt Creator (supongo que sin indicador de optimización). Al usar GCC, no hay una gran diferencia entre la versión de Mystical y mi código “optimizado”. Así que la conclusión es que las optimizaciones del comstackdor se ocupan de la optimización de micro mejor que los humanos (yo por fin). Dejo el rest de mi respuesta para referencia.


No es eficiente procesar imágenes de esta manera. Es mejor usar arreglos de una dimensión. El procesamiento de todos los píxeles se realiza en un ciclo. 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 sum de tres grupos de píxeles horizontalmente porque se usan tres veces cada uno.

Hice algunas pruebas y creo que vale la pena compartirlas. Cada resultado es un promedio de cinco pruebas.

Código original por user1615209:

 8193: 4392 ms 8192: 9570 ms 

La versión de Mystical:

 8193: 2393 ms 8192: 2190 ms 

Dos pasan usando una matriz 1D: primer pase para sums horizontales, segundo para sum 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 

Dos pasan usando una matriz 1D y un direccionamiento como este:

 for(i=SIZE;i 

Un pase almacenando en caché sums horizontales solo una fila más adelante para que permanezcan en el caché:

 // Horizontal sums for the first two lines for(i=1;i 

Conclusión:

  • No hay beneficios de usar varios punteros y solo incrementos (pensé que habría sido más rápido)
  • El almacenamiento en caché de sums horizontales es mejor que calcularlas varias veces.
  • Dos pases no son tres veces más rápidos, dos veces solamente.
  • Es posible lograr 3.6 veces más rápido utilizando tanto una sola pasada como el almacenamiento en caché de un resultado intermedio

Estoy seguro de que es posible hacerlo mucho mejor.

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

La orden de acceso a los elementos que se cuida allí todavía queda algunas frutas bajas. La acumulación se puede realizar de forma tal que cuando se itera hacia la derecha solo se necesiten 3 valores nuevos de la memoria y se acumulen. El truco es saber cómo soltar la columna más a la izquierda; cuando agrega 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: 3 lectura, 3 adición, 1 división

Piense en la ventana de muestreo como una caja de 3×3 en la que realiza un seguimiento de cada columna (1×3) por separado. Acumula una nueva columna y suelta la más antigua.

La división es una instrucción de alta latencia, por lo que puede ser ventajoso ocultar la latencia, pero antes de ir allí la salida del comstackdor debe inspeccionarse si se elije la división por constante y si el bucle que se desenrolla (por el comstackdor) ya tiene alguna compensación de latencia.

Pero después de la optimización más dramática del uso del caché correctamente, estas son cosas menores.