Perché questo migliora le prestazioni?

Question

Ho due cicli for che fondamentalmente cercano due array diversi (ciascuno con una dimensione di circa 2-4k al massimo) e impostano un valore in un terzo array basato su questi valori. Per qualche strana ragione c'è una differenza di fattore due tra le prestazioni di questo pezzo di codice in base all'ordine in cui metto i due per loops.

Questa è la prima configurazione. Esegue a ~ 150 millisecondi sul mio PC:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

Ora se cambio nulla, ma l'ordine dei loop come questo

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

Il tempo totale di esecuzione del metodo scende a circa ~ 400 millisecondi . In che modo un semplice scambio di ordini in loop migliora le prestazioni di quasi il 300%? Suppongo che sia una sorta di caching o puntatore?

Answer 1

È una soluzione di dati. Pensa alla memoria come a una singola dimensione. Ecco come sono effettivamente disposte le cose su disco (per quanto riguarda il computer.) Quindi, quando si creano array multidimensionali, quando si modifica l'ordine del loop si cambia il modo in cui l'array viene attraversato. Invece di leggere in ordine, stai saltando da una posizione all'altra.

---

Un array multi-dimensione sembra che questo a voi:

E come questo per il computer. Il modo ottimale di traslazione ha indici seguenti la freccia in basso:

Quindi, quando si cambia si serie loop l'array è attraversato in questo modo:

Così si ottiene di più i fallimenti della cache e un algoritmo meno performanti .

Answer 2

E 'molto probabile che si riferisca alla cache di colpi/mancati. La differenza sta nell'accesso sequenziale e disperso che si trova nelle dimensioni al di sopra della dimensione di una linea della cache.

Per semplici loop C++, sarebbe utile anche fare i loop all'indietro per ottenere un po 'di prestazioni sul loop. Non sono sicuro di come si adatti a .NET.

Answer 3

Località, località, località dei dati. Da Wikipedia (che lo dice meglio di quanto avrei):

Strutture dati lineari: la località spesso si verifica perché il codice contiene cicli che tendono a fare riferimento a matrici o altre strutture dati per indici. La località sequenziale, un caso speciale di località spaziale, si verifica quando gli elementi di dati rilevanti sono disposti e acceduti in modo lineare. Ad esempio, il semplice attraversamento di elementi in una matrice unidimensionale, dall'indirizzo di base all'elemento più alto, sfrutta la località sequenziale dell'array in memoria. [2] La località equidistante più generale si verifica quando l'attraversamento lineare si trova su un'area più lunga di strutture di dati adiacenti aventi struttura e dimensioni identiche, e in aggiunta a ciò, non tutte le strutture sono in accesso, ma solo gli stessi elementi delle strutture reciprocamente corrispondenti. Questo è il caso in cui una matrice viene rappresentata come una matrice sequenziale di righe e il requisito è quello di accedere a una singola colonna della matrice.

Answer 4

Mi ricordo di aver letto questo in Code Complete.Nella maggior parte delle lingue, gli array vengono impostati con l'ultimo indice impostato in modo sequenziale, quindi si accede ai byte direttamente in una riga quando si esegue l'iterazione sull'ultimo indice, invece di saltare quando si esegue l'iterazione sul primo.

Answer 5

Il tuo intuito ha ragione, si tratta di un problema di memorizzazione nella cache. @ Mike Daniels postare alla domanda qui sotto in sostanza sta descrivendo esattamente lo stesso problema. Il secondo bit di codice otterrà molti più colpi di cache.

Fastest way to loop through a 2d array?

Ma, shhhh non dovremmo preoccuparsi di destra prestazioni? :)

Answer 6

Vorrei anche pensare che le dimensioni relative degli array a e b farebbero la differenza.

Se a.lunghezza è grande e b.lunghezza è piccola, la seconda opzione dovrebbe essere più veloce. Al contrario, se a.length è piccolo e b.length è grande, la prima opzione sarebbe più veloce. Il problema è evitare il costo di setup/teardown del loop interno.

BTW, perché devi

int Alen = a.length;

Ma poi chiamare anche a.Lunghezza direttamente? Sembra che dovresti scegliere l'uno o l'altro.