Perché è peggio inizializzare un array bidimensionale come questo?

Question

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

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

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

Il mio professore ha detto che era molto più costoso inizializzare un array bidimensionale nel primo modo rispetto al secondo. Qualcuno può spiegare cosa sta succedendo sotto il cofano che lo rende il caso? Oppure, i due mezzi di inizializzazione hanno prestazioni uguali?

Answer 1

Come @dlev menzionato, questo è dovuto a locality of reference e ha a che fare con il funzionamento dell'hardware fisico nel computer.

All'interno del computer, ci sono molti diversi tipi di memoria. In genere, solo determinate posizioni di memoria (registri) possono avere effettive operazioni eseguite su di esse; il resto del tempo, se stai eseguendo operazioni sui dati, devi caricarlo dalla memoria in un registro, eseguire alcuni calcoli, quindi riscriverli.

La memoria principale (RAM) è molto, molto più lenta dei registri, spesso di un fattore da centinaia a migliaia. Di conseguenza, la lettura dalla memoria dovrebbe essere evitata se possibile. Per risolvere questo problema, la maggior parte dei computer dispone di aree di memoria speciali chiamate caches. Il lavoro della cache è di conservare i dati a cui è stato recentemente effettuato l'accesso dalla memoria in modo tale che, se si accede nuovamente alla stessa area di memoria, il valore può essere estratto dalla cache (veloce) anziché dalla memoria principale (lento). In genere, le cache sono progettate in modo che se un valore viene letto dalla memoria, quel valore, più un intero gruppo di valori adiacenti, viene inserito nella cache. In questo modo, se si esegue un'iterazione su un array, dopo aver letto il primo valore, il resto dei valori dell'array si troverà nella cache e sarà possibile accedervi in ​​modo più efficiente.

Il motivo per cui il codice è più lento di quello che deve essere è che non accede agli elementi dell'array in modo sequenziale. In C, gli array 2D sono disposti in row-major order, il che significa che la memoria è organizzato come

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] ... 

Di conseguenza, se si utilizza questo ciclo for:

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

Quindi si ottiene eccellente località, perché si accedere agli elementi dell'array nell'ordine in cui appaiono in memoria. Questo rende il numero di letture della memoria principale molto piccolo, dato che tutto è tipicamente in cache e pronto a partire.

Tuttavia, se scambiate i loop, come avete fatto, i vostri accessi saltano in memoria e non sono necessariamente consecutivi. Ciò significa che avrete un sacco di errori di memoria nella cache in cui l'indirizzo di memoria che leggete dopo non è nella cache. Ciò aumenta il numero di carichi della cache, che possono rallentare notevolmente il programma.

I compilatori stanno iniziando a diventare abbastanza intelligenti da scambiare automaticamente loop di questo tipo, ma siamo ancora lontani dall'essere in grado di ignorare questi dettagli. Come regola generale, quando si scrive codice C o C++ per matrici multidimensionali, provare ad eseguire l'iterazione in ordine di riga principale anziché in ordine di colonna principale. È possibile ottenere aumenti notevoli nel programma.

Spero che questo aiuti!

Answer 2

Se si guardano le posizioni di memoria a cui si accede da ciascuna tecnica, il secondo accede a byte consecutivi, mentre il primo salterà per salti di 100 byte. La memoria cache funzionerà in modo molto più efficiente se lo fai nel secondo modo.

Answer 3

io probabilmente ottenere downvoted per questo, ma se si sta programmando C, poi il "migliore" è più probabile:

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

Quindi è possibile rinviare tutta la responsabilità dell'ottimizzazione (di cui si è ovviamente preoccupati) all'implementazione di memset. Qui possono essere fatti tutti i vantaggi hardware specifici.

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

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

Un'altra osservazione è che se si sta init'ing a zero, chiedetevi perché? Se la tua matrice è statica (che probabilmente è così?), Allora cstartup verrà inizializzato a zero per te. Di nuovo, questo probabilmente utilizzerà il modo più efficiente per il tuo hardware.

Answer 4

Sono un po 'in ritardo per la festa, e c'è già un'ottima risposta. Tuttavia, ho pensato di poter contribuire dimostrando come si potesse rispondere a questa domanda sperimentalmente usando uno strumento di profilazione (su Linux).

Utilizzerò lo strumento perf nel pacchetto Ubuntu 10.10 linux-tools-common.

Ecco il piccolo programma C che ho scritto per rispondere a questa domanda:

// 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; 
} 

quindi compilare le due versioni differenti:

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

Nota Ho ottimizzazione disabile con -O0 così gcc non ha alcuna possibilità riorganizzare il nostro loop per essere più efficiente.

È possibile elencare le statistiche sul rendimento disponibili con perf facendo perf list. In questo caso, siamo interessati alle miss cache che è l'evento cache-misses.

Ora è facile come eseguire ogni versione del programma numerose volte e prendendo una media:

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

E ora abbiamo verificato sperimentalmente che si fa in effetti vedere due ordini di grandezza più cache miss con la versione "row-minor".