c++ - ¿Por qué mi programa es lento cuando se repite exactamente 8192 elementos?

performance memory-management

Question

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, crea una matriz res[][] , y cada campo aquí está hecho para ser 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 para el programa. Para completar, aquí está lo que viene antes. Ningún código viene después. Como puedes ver, es sólo la 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é mucho sobre ese tema, por eso lo pregunto aquí.

También sería bueno cómo solucionar esto, pero si alguien pudiera explicar estos tiempos de ejecución, ya sería lo suficientemente feliz.

Ya sé de 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.

Answer 1

El orden de acceso a los elementos que se cuida aún quedan algunos frutos bajos. La acumulación se puede hacer de manera que cuando se itera a la derecha, solo se deben recuperar 3 valores nuevos de la memoria y acumular. El truco es saber cómo soltar la columna de la izquierda; cuando agregue una nueva columna, recuerde su valor hasta que salga de la ventana de muestreo.

El costo anterior: 9 lecturas, 9 adicionales, 1 división El costo posterior: 3 lecturas, 3 adicionales, 1 división

Piense en la ventana de muestreo como un cuadro de 3x3 en el que realiza un seguimiento de cada columna (1x3) 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 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 elimina y si el bucle que se desenrolla (por el compilador) ya hace alguna compensación de latencia.

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

Answer 2

La diferencia se debe al mismo problema de superalineación de las siguientes preguntas relacionadas:

• ¿Por qué la transposición de una matriz de 512x512 es mucho más lenta que la de una matriz de 513x513?
• Multiplicación de matrices: 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<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;
}

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

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Así que 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 en fila.

Para resolver este problema, debes intercambiar los dos bucles.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Esto elimina todo el acceso no secuencial por completo, por lo que ya no tendrá 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

Bucles externos intercambiados:

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

Answer 3

Las siguientes pruebas se realizaron con el compilador de Visual C ++, ya que se utiliza en 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 compilador se ocupan de la micro optimización mejor que los humanos (por fin yo). Dejo el resto de mi respuesta para referencia.

No es eficiente procesar imágenes de esta manera. Es mejor usar matrices de una sola dimensión. El procesamiento de todos los píxeles es el hecho 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 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:

8193: 4392 ms
8192: 9570 ms

La versión mística:

8193: 2393 ms
8192: 2190 ms

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

Un paso que almacena sumas horizontales solo una fila adelante 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é las sumas horizontales es mejor que calcularlas varias veces.
• Dos pasadas no son tres veces más rápidas, solo dos veces.
• 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 Por favor, tenga en cuenta que escribí esta respuesta para tratar los problemas generales de rendimiento en lugar del problema de caché explicado en la excelente respuesta de Mystical. Al principio era solo un pseudo código. Me pidieron que hiciera pruebas en los comentarios ... Aquí hay una versión completamente refactorizada con pruebas.