Credo che quello che stai vedendo sono gli effetti di locality of reference nella gerarchia di memoria del computer.
Tipicamente, la memoria del computer è segregato in diverse tipologie che hanno diverse caratteristiche prestazionali (questo è spesso chiamato il memory hierarchy). La memoria più veloce è nei registri del processore, che possono (solitamente) essere letti e letti in un singolo ciclo di clock. Tuttavia, di solito ci sono solo una manciata di questi registri (di solito non più di 1 KB). La memoria principale del computer, d'altra parte, è enorme (ad esempio, 8 GB), ma è molto più lenta da accedere. Al fine di migliorare le prestazioni, il computer è solitamente costruito fisicamente per avere several levels of caches tra il processore e la memoria principale. Queste cache sono più lente dei registri ma molto più veloci della memoria principale, quindi se si fa un accesso alla memoria che sembra qualcosa nella cache tende ad essere molto più veloce che se si debba andare alla memoria principale (tipicamente, tra 5-25x Più veloce). Quando si accede alla memoria, il processore prima controlla la cache di memoria per quel valore prima di tornare alla memoria principale per leggere il valore. Se si accede costantemente ai valori nella cache, si otterranno prestazioni molto migliori rispetto a quando si salta memoria, accesso casuale ai valori.
La maggior parte dei programmi sono scritti in modo tale che se un singolo byte in memoria viene letto in memoria, il programma in seguito legge più valori diversi da quella regione di memoria. Di conseguenza, queste cache sono in genere progettate in modo che quando si legge un singolo valore dalla memoria, un blocco di memoria (in genere da qualche parte tra 1 KB e 1 MB) di valori attorno a quel singolo valore viene anche inserito nella cache. In questo modo, se il tuo programma legge i valori vicini, sono già nella cache e non devi andare alla memoria principale.
Ora, un ultimo dettaglio - in C/C++, gli array sono memorizzati in ordine di riga maggiore, il che significa che tutti i valori in una singola riga di una matrice sono memorizzati uno accanto all'altro. Così in memoria la matrice appare come la prima riga, quindi la seconda riga, poi la terza riga, ecc.
Dato questo, diamo un'occhiata al tuo codice. La prima versione si presenta così:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Ora, diamo un'occhiata a quella linea più interna di codice. Ad ogni iterazione, il valore di k sta cambiando in aumento. Ciò significa che quando si esegue il ciclo più interno, è probabile che ciascuna iterazione del ciclo abbia un errore di cache durante il caricamento del valore di b[k][j].La ragione di ciò è che, poiché la matrice è memorizzata in ordine di riga principale, ogni volta che si incrementa k, si salta su un'intera riga della matrice e si passa molto più in profondità nella memoria, probabilmente oltre i valori che si sono memorizzati nella cache . Tuttavia, non si ha una mancanza quando si guarda su c[i][j] (dal i e j sono gli stessi), né probabilmente si perde a[i][k], perché i valori sono in ordine di riga principale e se il valore di a[i][k] viene memorizzato nella cache dal precedente iterazione, il valore di a[i][k] letto su questa iterazione proviene da una posizione di memoria adiacente. Di conseguenza, in ogni iterazione del ciclo più interno, è probabile che si abbia un errore di cache.
Ma considerare questa seconda versione:
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Ora, dal momento che si sta sempre più j ad ogni iterazione, pensiamo a quante di cache manca è probabile che sia sulla dichiarazione più interno. Poiché i valori sono in ordine di riga principale, è probabile che il valore di c[i][j] sia in-cache, poiché il valore di c[i][j] dall'iterazione precedente è probabilmente memorizzato nella cache e pronto per essere letto. Analogamente, b[k][j] è probabilmente memorizzato nella cache e poiché i e k non cambiano, è probabile che lo stesso sia a[i][k]. Ciò significa che su ogni iterazione del ciclo interno, è probabile che non ci siano errori di cache.
Nel complesso, questo significa che è improbabile che la seconda versione del codice abbia errori di cache su ogni iterazione del ciclo, mentre la prima versione quasi certamente lo farà. Di conseguenza, è probabile che il secondo ciclo sia più veloce del primo, come hai visto.
È interessante notare che molti compilatori stanno iniziando ad avere il supporto del prototipo per rilevare che la seconda versione del codice è più veloce della prima. Alcuni cercheranno di riscrivere automaticamente il codice per massimizzare il parallelismo. Se si dispone di una copia di Purple Dragon Book, il capitolo 11 illustra come funzionano questi compilatori.
Inoltre, è possibile ottimizzare ulteriormente le prestazioni di questo ciclo utilizzando loop più complessi. Una tecnica denominata blocking, ad esempio, può essere utilizzata per aumentare notevolmente le prestazioni suddividendo l'array in sottoregioni che possono essere trattenute più a lungo nella cache, quindi utilizzando più operazioni su questi blocchi per calcolare il risultato complessivo.
Spero che questo aiuti!
+1 Ottima spiegazione! Anche il suggerimento @Kerrek SB fatto sul debug della cache aggiunge molti più dettagli tecnici. – rbaleksandar