Qué ordenamiento de bucles anidados para iterar sobre una matriz 2D es más eficiente
performance for-loop (10)
Para el conjunto [100] [100]: ambos son iguales, si el caché L1 es más grande que 100 * 100 * sizeof (int) == 10000 * sizeof (int) == [usualmente] 40000. Nota en Sandy Bridge - 100 * 100 enteros deberían ser elementos suficientes para ver la diferencia, ya que la caché L1 es solo 32k.
Los compiladores probablemente optimicen este código de todos modos
Suponiendo que no hay optimizaciones del compilador, y la matriz no cabe en la memoria caché L1, el primer código es mejor debido al rendimiento de la memoria caché [por lo general]. Cada vez que un elemento no se encuentra en la memoria caché, obtienes una falta de memoria caché , y necesitas ir a la memoria caché RAM o L2 [que son mucho más lentos]. Tomar elementos de la memoria RAM a la memoria caché [relleno de caché] se realiza en bloques [generalmente 8/16 bytes], por lo que en el primer código, se obtiene una tasa de error de
1/4[suponiendo 16 bytes de bloque de caché, 4 bytes de entrada] mientras en el segundo código no tiene límites, y puede ser incluso 1. En el segundo complemento de código, se quitaron los elementos que ya estaban en el caché [insertados en el relleno del caché para los elementos adyacentes], y se obtiene un error de caché redundante.- Esto está estrechamente relacionado con el principio de localidad , que es la suposición general utilizada al implementar el sistema de caché. El primer código sigue este principio mientras que el segundo no; por lo tanto, el rendimiento de la memoria caché del primero será mejor que el del segundo.
Conclusión: Para todas las implementaciones de caché de las que tengo conocimiento, la primera no será peor que la segunda. Pueden ser lo mismo, si no hay ninguna memoria caché o toda la matriz cabe en la caché por completo, o debido a la optimización del compilador.
¿Cuál de los siguientes ordenamientos de bucles anidados para iterar en una matriz 2D es más eficiente en términos de tiempo (rendimiento de la memoria caché)? ¿Por qué?
int a[100][100];
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[i][j] = 10;
}
}
o
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[j][i] = 10;
}
}
El primer método es ligeramente mejor, ya que las celdas que se asignan se colocan una al lado de la otra.
Primer método:
[ ][ ][ ][ ][ ] ....
^1st assignment
^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment
Segundo método:
[ ][ ][ ][ ][ ] ....
^1st assignment
^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
En el segundo método, caché se pierde, porque el caché almacena datos contiguos. por lo tanto, el primer método es eficiente que el segundo método.
En general, una mejor localidad (notada por la mayoría de los que responden) es solo la primera ventaja para el rendimiento del bucle n. ° 1.
La segunda ventaja (pero relacionada) es que para bucles como # 1: el compilador normalmente puede auto-vectorizar de manera eficiente el código con el patrón de acceso de memoria stride-1 (zancada-1 significa que hay acceso contiguo a elementos de matriz uno por cada próxima iteración). Por el contrario, para bucles como # 2 , las auto-vectorizaciones normalmente no funcionarán bien, porque no hay acceso iterativo de zancada-1 consecutiva a bloques contiguos en la memoria.
Bueno, mi respuesta es general. Para bucles muy simples exactamente como # 1 o # 2, podría haber optimizaciones de compilador aún más simples y agresivas (clasificando cualquier diferencia) y también el compilador normalmente podrá auto-vectorizar # 2 con zancada-1 para bucle externo (especialmente con # pragma simd o similar).
En su segundo fragmento, el cambio en j en cada iteración produce un patrón con baja localidad espacial. Recuerde que detrás de las escenas, una referencia de matriz calcula:
( ((y) * (row->width)) + (x) )
Considere una caché L1 simplificada que tenga suficiente espacio para solo 50 filas de nuestra matriz. Durante las primeras 50 iteraciones, pagará el costo ineludible de 50 fallas de caché, pero ¿qué ocurre? Para cada iteración de 50 a 99, aún se almacenará en caché y se tendrá que recuperar desde L2 (y / o RAM, etc.). Luego, x cambia a 1 y y comienza de nuevo, lo que da como resultado otra falta de caché porque la primera fila de su matriz ha sido desalojada de la memoria caché, y así sucesivamente.
El primer fragmento no tiene este problema. Accede a la matriz en orden de fila mayor , que logra una ubicación mejor: solo tiene que pagar por errores de caché una vez como máximo (si una fila de la matriz no está presente en la memoria caché en el momento en que se inicia el ciclo) por fila.
Dicho esto, esta es una pregunta muy dependiente de la arquitectura, por lo que debería tener en cuenta los detalles (tamaño de caché L1, tamaño de línea de caché, etc.) para llegar a una conclusión. También debe medir ambas formas y realizar un seguimiento de los eventos de hardware para obtener datos concretos de los que extraer conclusiones.
En tu caso (completa todo el valor de la matriz 1), será más rápido:
for(j = 0; j < 100 * 100; j++){
a[j] = 10;
}
y aún podrías tratar a matriz de 2 dimensiones.
EDITAR : Como mencionó Binyamin Sharet, puedes hacerlo si tu a se declara de esa manera:
int **a = new int*[100];
for(int i = 0; i < 100; i++){
a[i] = new int[100];
}
Este es un problema clásico sobre el cache line bouncing
En la mayoría de los casos, el primero es mejor, pero creo que la respuesta exacta es: DEPENDE , la arquitectura diferente puede ser un resultado diferente.
Este tipo de microoptimización depende de la plataforma, por lo que deberá perfilar el código para poder llegar a una conclusión razonable.
La primera opción es mejor, ya que podemos almacenar a[i] in a temp variable dentro del primer ciclo y luego buscar el índice j en eso. En este sentido, se puede decir como variable almacenada en caché.
Teniendo en cuenta que C ++ es hilera principal, creo que el primer método será un poco más rápido. En la memoria, una matriz 2D se representa en una matriz de dimensión única y el rendimiento depende del acceso a ella, ya sea mediante fila principal o columna principal.