Qué orden de bucles anidados para iterar sobre una matriz 2D es más eficiente

1. Para array[100] [100] - ambos son iguales, si la caché L1 es más grande entonces 100*100*sizeof(int) == 10000*sizeof(int) = = [usualmente] 40000. Nota en Sandy Bridge - 100 * 100 enteros deberían ser suficientes elementos para ver una diferencia, ya que la caché L1 es solo 32k.

2. Los compiladores probablemente optimizarán este código de todos modos

3. Suponiendo que no hay optimizaciones del compilador, y la matriz no cabe en la caché L1 - el primer código es mejor debido a la caché rendimiento [por lo general]. Cada vez que un elemento no se encuentra en caché - se obtiene un cache miss - y necesita ir a la memoria RAM o caché L2 [que son mucho más lentos]. Tomar elementos de la RAM a la caché [relleno de caché] se realiza en bloques[generalmente 8/16 bytes] - por lo que en el primer código, se obtiene a lo sumo tasa de error de 1/4 [suponiendo bloque de caché de 16 bytes, 4 bytes ints] mientras que en el segundo código es ilimitado, y puede ser incluso 1. En el segundo complemento de código-elementos que ya estaban en caché [insertado en el relleno de caché para los elementos adyacentes] - fueron sacados, y se obtiene un error de caché redundante.

   • Esto está estrechamente relacionado con el principio de localidad, que es el supuesto general utilizado cuando se implementa el sistema de caché. El primer código sigue este principio mientras que el segundo no, por lo que el rendimiento de caché del primero será mejor que el del segundo.

Conclusión: Para todas las implementaciones de caché soy consciente de-el primero no será peor que el segundo. Pueden ser los mismos - si no hay caché en absoluto o toda la matriz encaja en la caché por completo-o debido a la optimización del compilador.

Este tipo de microoptimización depende de la plataforma, por lo que necesitará perfilar el código para poder sacar una conclusión razonable.

En el segundo fragmento, el cambio en j en cada iteración produce un patrón con una localidad espacial baja. 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 nuestro array. Para las primeras 50 iteraciones, pagará el costo inevitable de 50 errores de caché, pero ¿entonces qué sucede? Para cada iteración de 50 a 99, todavía se perderá la caché y tendrá que obtener desde L2 (y / o RAM, etc.). Entonces, x cambia a 1 y y comienza de nuevo, lo que lleva a otro error de caché porque la primera fila de su matriz ha sido desalojada de la caché, y así sucesivamente.

El primer fragmento no tiene este problema. Accede a la matriz en fila-orden mayor, lo que logra una mejor localidad - solo tiene que pagar por errores de caché como máximo una vez (si una fila de su matriz no está presente en la caché en el momento en que se inicia el bucle) por fila.

Dicho esto, este es un muy pregunta dependiente de la arquitectura, por lo que tendría que tener en cuenta los detalles (tamaño de caché L1, tamaño de línea de caché, etc.) para sacar una conclusión. También debe medir ambas formas y realizar un seguimiento de los eventos de hardware para tener datos concretos de los que sacar conclusiones.

Considerando que C++ es la fila mayor, creo que el primer método va a ser un poco más rápido. En memoria, una matriz 2D se representa en una matriz de dimensión única y el rendimiento depende del acceso a ella utilizando la fila mayor o la columna mayor

Este es un problema clásico sobre cache line bouncing

En la mayoría de los casos el primero es mejor, pero creo que la respuesta exacta es: DEPENDE, una arquitectura diferente puede ser un resultado diferente.

En el segundo método, Cache miss, porque la caché almacena datos contiguos. por lo tanto, el primer método es eficiente que el segundo método.

En su caso (llene todo el valor de la matriz 1), eso será más rápido:

   for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }

Y todavía podría tratar a como matriz de 2 dimensiones.

EDITAR : Como mencionó Binyamin Sharet, usted podría hacerlo si su a se declara de esa manera:

int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}

En general, una mejor localidad (observada por la mayoría de los respondedores) es solo la primera ventaja para el rendimiento del bucle #1.

La segunda ventaja (pero relacionada), es que para bucles como #1 - compiler es normalmente capaz de de manera eficiente auto-vectorizar el código con el patrón de acceso a memoria stride-1 (stride-1 significa que hay acceso contiguo a los elementos de la matriz uno por uno en cada iteración siguiente). Por el contrario, para bucles como #2 , las auto-vectorizaciones no normalmente funciona bien, porque no hay acceso iterativo stride-1 consecutivo a bloques contiguos en memoria.

Bueno, mi respuesta es general. Para bucles muy simples exactamente como #1 o #2, podría haber optimizaciones de compilador agresivas aún más simples utilizadas (calificando cualquier diferencia) y también el compilador normalmente será capaz de auto-vectorizar #2 con stride - 1 para bucle externo (especialmente con #pragma simd o similar).

La primera opción es mejor ya que podemos almacenar a[i] in a temp variable dentro del primer bucle y luego buscar el índice j en ese. En este sentido se puede decir como variable en caché.