Acceso a los elementos de una matriz por filas en comparación con las columnas

Question

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

1. columna sabia
2. fila sabia

Desde mi punto de vista, fila sabia es mejor debido a que en conjunto los elementos de representación se almacenan en posiciones de memoria contiguas de manera acceder a ellos tarda menos tiempo.Pero ya que en La RAM que busca cada ubicación requiere el mismo tiempo, ¿es importante?

Answer 1

Aprovechese de Spatial Locality

En C, matrices se almacenan en r ow-major order. Por lo tanto, si accede al elemento a[i][j], es probable que un acceso al elemento a[i][j+1] llegue al 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 otros factores, como el acceso de escritura/lectura, la política de escritura (escritura, escritura/asignación de escritura, asignación de 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 cachegrind, y compruébalo por ti mismo.

Por ejemplo, considere un programa ficticio que acceda a matrices de 4MB. Verifique las diferencias entre las tasas de error 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 filas

$ 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% ) 

Answer 2

Si las matrices son pequeños que no es importante. Si son grandes, entonces 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é a la vez, entonces quiere minimizar el número de fallas de caché que encuentra, porque lidiar con una falta de caché es relativamente lento.

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

Answer 3

Para C, la mejor manera de manejar matrices 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 se encarga de las matrices como punteros con compensaciones, ver: The C Programming Language.