Acceder a elementos de una matriz por filas versus por columnas

una matriz A[i][j] es dado. Si queremos sumar los elementos de la matriz, ¿qué método es mejor y por qué?

1. columna sabia
2. fila sabia

Desde mi punto de vista, la fila inteligente es mejor porque en la representación de la matriz los elementos se almacenan en ubicaciones de memoria contiguas, por lo que acceder a ellos lleva menos tiempo. Pero dado que en la RAM, obtener cada ubicación lleva el mismo tiempo, ¿importa?

Tomar ventaja de Localidad espacial

En C, las matrices se almacenan en rorden mayor. Así que si accedes al elemento a[i][j]un elemento de acceso a[i][j+1] es probable que golpee el caché. No se realizará ningún acceso a la memoria principal. Los cachés son más rápidos que la memoria principal, por lo que el patrón de acceso sí importa.

Por supuesto, se deben tener en cuenta más factores, como el acceso de escritura/acceso de lectura, la política de escritura (escritura simultánea, reescritura/asignación de escritura, asignación sin escritura), cachés multinivel, etc. Pero eso parece una exageración para esta pregunta.

Diviértete con una herramienta de creación de perfiles, como cachegrindy compruébelo usted mismo.

Por ejemplo, considere un programa ficticio que accede a matrices de 4 MB. Consulte las diferencias entre las tasas de fallas en cada patrón de acceso.

acceso a la columna

$ cat col_major.c 
#include <stdio.h>

int main(){

    size_t i,j;

    const size_t dim = 1024 ;

    int matrix [dim][dim];

    for (i=0;i< dim; i++){
        for (j=0;j <dim;j++){
            matrix[j][i]= i*j;
        }
    }
    return 0;
}

$ valgrind --tool=cachegrind ./col_major 

==3228== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3228== D1  misses:     1,049,704  (      968 rd   + 1,048,736 wr)
==3228== L2d misses:     1,049,623  (      893 rd   + 1,048,730 wr)
==3228== D1  miss rate:        9.9% (      0.0%     +      98.3%  )
==3228== L2d miss rate:        9.9% (      0.0%     +      98.3%  )

acceso a la fila

$ cat row_major.c 
#include <stdio.h>

int main(){
    size_t i,j;
    const size_t dim = 1024 ;
    int matrix [dim][dim];

    for (i=0;i< dim; i++)
        for (j=0;j <dim;j++)
            matrix[i][j]= i*j;

    return 0;
}

$ valgrind --tool=cachegrind ./row_major 

==3524== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3524== D1  misses:        66,664  (      968 rd   +    65,696 wr)
==3524== L2d misses:        66,583  (      893 rd   +    65,690 wr)
==3524== D1  miss rate:        0.6% (      0.0%     +       6.1%  )
==3524== L2d miss rate:        0.6% (      0.0%     +       6.1%  )

Si las matrices son pequeñas, no es importante. Si son grandes, el tiempo de lectura puede verse afectado. El gran problema es el caché. Si no puede esperar que su matriz completa se cargue en el caché de una vez, entonces desea minimizar la cantidad de errores de caché que encuentre, porque lidiar con un error de caché lleva relativamente tiempo.

Si las matrices son realmente grandes, entonces podría recibir impactos de rendimiento aún mayores al causar más intercambio de páginas de lo necesario.

Para C, la mejor manera de manejar arreglos multidimensionales es:

int a[MAX_I][MAX_J];
for (i = 0; i < MAX_I; ++i) {
   for (j = 0; j < MAX_J; ++j) {
      /* process a[i][j] */
   }
}

La razón de esto es que el lenguaje C maneja las matrices como punteros con compensaciones, consulte: El lenguaje de programación C.