¿Por qué es peor inicializar una matriz bidimensional como esta?

Question

for(int i = 0; i<100; i++) 

    for(int j = 0; j<100; j++) 

     array[j][i] = 0; 
     // array[i][j] = 0; 

Mi profesor dijo que era mucho más costoso inicializar una matriz bidimensional de la primera manera que la segunda. ¿Alguien puede explicar lo que está pasando debajo del capó que hace que el caso? O bien, ¿los dos medios de inicialización tienen el mismo rendimiento?

Answer 1

Como @dlev mencionado, esto se debe a locality of reference y tiene que ver con cómo funciona el hardware físico en la computadora.

Dentro de la computadora, hay muchos tipos diferentes de memoria. Típicamente, solo ciertas ubicaciones de memoria (registros) pueden tener operaciones reales realizadas en ellos; el resto del tiempo, si está realizando operaciones en datos, debe cargarlo desde la memoria en un registro, realizar algunos cálculos y luego volver a escribirlos.

La memoria principal (RAM) es mucho, mucho más lenta que los registros, a menudo por un factor de cientos a miles. En consecuencia, la lectura de la memoria debe evitarse si es posible. Para solucionar esto, la mayoría de las computadoras generalmente tienen regiones de memoria especiales llamadas caches. El trabajo de la memoria caché es contener datos a los que se ha accedido recientemente desde la memoria, de modo que si se accede nuevamente a esa misma región de memoria, el valor se puede extraer de la memoria caché (rápido) en lugar de desde la memoria principal (lenta). Normalmente, las memorias caché están diseñadas de modo que si se lee un valor de la memoria, ese valor, más un conjunto completo de valores adyacentes, se extraen en la memoria caché. De esta forma, si itera sobre una matriz, luego de leer el primer valor, el resto de los valores de la matriz se ubicará en la memoria caché y se podrá acceder a ella de manera más eficiente.

El motivo por el que el código es más lento de lo que debe ser es que no accede a los elementos de la matriz de forma secuencial. En C, las matrices 2D se establecen en row-major order, lo que significa que la memoria está dispuesto como

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ... 

En consecuencia, si se utiliza este bucle for:

for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
     // Do something with A[i][j] 
    } 
} 

, entonces obtendrá una excelente localidad, ya que se acceder a los elementos de la matriz en el orden en que aparecen en la memoria. Esto hace que el número de lecturas de la memoria principal sea muy pequeño, ya que todo está típicamente en caché y listo para funcionar.

Sin embargo, si intercambia los bucles, como lo ha hecho, sus accesos saltan en la memoria y no son necesariamente consecutivos. Esto significa que tendrá un montón de falta de memoria caché en la que la dirección de memoria que lee a continuación no está en la memoria caché. Esto aumenta la cantidad de cargas de caché, lo que puede ralentizar drásticamente el programa.

Los compiladores están empezando a ser lo suficientemente inteligentes como para intercambiar los bucles de este modo de forma automática, pero todavía estamos lejos de poder ignorar estos detalles. Como regla general, al escribir código C o C++ para matrices multidimensionales, intente iterar en orden mayor de fila en lugar de orden de columna mayor. Puedes obtener aceleraciones notables en tu programa.

Espero que esto ayude!

Answer 2

Si observa las ubicaciones de memoria a las que accede cada técnica, la segunda accederá a bytes consecutivos, mientras que la primera saltará alrededor de saltos de 100 bytes. La memoria caché funcionará de manera mucho más eficiente si lo haces de la segunda manera.

Answer 3

que probablemente obtendrá downvoted para esto, pero si se está programando C, entonces el "mejor" es más probable:

memset (array, 0, sizeof (matriz));

A continuación, puede aplazar toda la responsabilidad de la optimización (que obviamente le preocupa) a la implementación de memset. Cualquier ventaja específica de hardware se puede hacer allí.

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

Otra observación es que si usted está init'ing a cero, pregúntese por qué? Si su matriz es estática (que para este tamaño es probable que sea?), Entonces cstartup se inicializará a cero para usted. Nuevamente, esto probablemente usará la forma más eficiente para su hardware.

Answer 4

Llego un poco tarde a la fiesta, y ya hay una respuesta excelente. Sin embargo, pensé que podría contribuir demostrando cómo se podría responder esta pregunta de forma experimental utilizando una herramienta de creación de perfiles (en Linux).

Usaré la herramienta perf en el paquete Ubuntu 10.10 linux-tools-common.

Aquí está el pequeño programa en C que escribí para responder a esta pregunta: ¿

// test.c 
#define DIM 1024 

int main() 
{ 
    int v[DIM][DIM]; 
    unsigned i, j; 

    for (i = 0; i < DIM; i++) { 
     for (j = 0; j < DIM; j++) { 
#ifdef ROW_MAJOR_ORDER 
      v[i][j] = 0; 
#else 
      v[j][i] = 0; 
#endif 
     } 
    } 

    return 0; 
} 

a continuación, compilar las dos versiones diferentes:

$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj 
$ gcc test.c -O0 -o row-min 

Nota tengo optimización de lesionados con -O0 por lo gcc no tiene ninguna posibilidad para reorganizar nuestro ciclo para ser más eficiente.

Podemos enumerar las estadísticas de rendimiento disponibles con perf haciendo perf list. En este caso, estamos interesados ​​en errores de caché, que es el evento cache-misses.

Ahora es tan simple como ejecutar cada versión del programa en numerosas ocasiones y tomando un promedio:

$ perf stat -e cache-misses -r 100 ./row-min 

Performance counter stats for './row-min' (100 runs): 

      286468 cache-misses    (+- 0.810%) 

     0.016588860 seconds time elapsed (+- 0.926%) 

$ perf stat -e cache-misses -r 100 ./row-maj 

Performance counter stats for './row-maj' (100 runs): 

       9594 cache-misses    (+- 1.203%) 

     0.006791615 seconds time elapsed (+- 0.840%) 

Y ahora hemos verificado experimentalmente que lo hace, de hecho, ver a dos órdenes de magnitud más fallos de caché con la versión "row-minor".