Warum wird die iterierende 2D-Array-Zeile schneller als die Spaltenhauptreihe?

Question

Hier ist einfacher C++ - Code, der das Iterieren von 2D-Array-Zeilenmajor mit Spaltenmajor vergleicht.

#include <iostream> 
#include <ctime> 

using namespace std; 

const int d = 10000; 

int** A = new int* [d]; 

int main(int argc, const char * argv[]) { 
    for(int i = 0; i < d; ++i) 
     A[i] = new int [d]; 

    clock_t ColMajor = clock(); 

    for(int b = 0; b < d; ++b) 
     for(int a = 0; a < d; ++a) 
      A[a][b]++; 

    double col = static_cast<double>(clock() - ColMajor)/CLOCKS_PER_SEC; 

    clock_t RowMajor = clock(); 
    for(int a = 0; a < d; ++a) 
     for(int b = 0; b < d; ++b) 
      A[a][b]++; 

    double row = static_cast<double>(clock() - RowMajor)/CLOCKS_PER_SEC; 



    cout << "Row Major : " << row; 
    cout << "\nColumn Major : " << col; 

    return 0; 
} 

Ergebnis für verschiedene Werte von d:

d = 10^3:

Row-Dur: 0,002431

Spaltenhaupt: 0,017186

= 0

d 10^4:

Zeilenhaupt: 0,237995

Spaltenhaupt: 2,04471

d = 10^5

Zeilenhaupt: 53.9561

Spalte Haupt: 444.339

Jetzt ist die Frage, warum Zeile Haupt schneller als Spalte Haupt ist?

Answer 1

Es ist offensichtlich auf der Maschine ab, die Sie sind auf, aber sehr allgemein gesprochen:

1. Ihr Computer speichert Teile Ihrer Programme Speicher in einem Cache, der eine viel geringere Latenz als Hauptspeicher hat (auch wenn kompensierte für die Cache-Trefferzeit).

2. C-Arrays werden in einer zusammenhängenden Reihenfolge gespeichert. Das heißt, wenn Sie nach dem Element x fragen, dann wird das Element x+1 im Hauptspeicher an einer Stelle gespeichert, die direkt hinter der Adresse x liegt.

3. Es ist typisch für Ihren Computer-Cache, den Cache "vorbeugend" mit Speicheradressen zu füllen, die noch nicht verwendet wurden, die sich jedoch lokal im Speicher befinden, den Ihr Programm bereits verwendet hat. Denken Sie an Ihren Computer mit den Worten: "Nun, Sie wollten Speicher an Adresse X, also gehe ich davon aus, dass Sie in Kürze Speicher bei X + 1 wollen, also werde ich das für Sie präventiv aufnehmen und in Ihren Cache legen" .

Deshalb, wenn Sie Ihre Array über den Zeilenhaupt aufzuzählen, bist du es so aufzählt, wo sie in einer zusammenhängenden Weise im Speicher gespeichert ist, und das Gerät ist bereits die Freiheit Vorladen diejenigen genommen Adressen in den Cache für Sie weil es vermutete, dass Sie es wollten. Daher erzielen Sie eine höhere Rate von Cache-Treffern. Wenn Sie ein Array auf eine andere, nicht zusammenhängende Weise aufzählen, wird Ihr Rechner wahrscheinlich das von Ihnen angewendete Speicherzugriffsmuster nicht vorhersagen, so dass es nicht in der Lage ist, Speicheradressen für Sie vorab in den Cache zu ziehen Cache-Treffer, so dass häufiger auf den Hauptspeicher zugegriffen werden muss, der langsamer ist als Ihr Cache.

auch, dies könnte besser für https://cs.stackexchange.com/ geeignet sein, weil die Art, wie sich Ihr System-Cache verhält, in Hardware implementiert ist, und räumliche Ortungsfragen scheinen dort besser geeignet zu sein.

Answer 2

Ihr Array ist eigentlich ein ragged array, so Reihe Haupt ist nicht ganz ein Faktor.

Sie sehen eine bessere Leistung bei der Iteration über Spalten und Zeilen, da der Zeilenspeicher linear angeordnet ist. Das sequenzielle Lesen ist für den Cachepridektor einfach, und Sie amortisieren die Zeigerdereferenz auf die zweite Dimension, da sie nur benötigt wird einmal pro Zeile durchgeführt werden.

Wenn Sie über die Zeilen und dann die Spalten iterieren, entsteht eine Zeigerdereferenz auf die zweite Dimension pro Iteration. Wenn Sie also über Zeilen iterieren, fügen Sie eine Zeigerdereferenz hinzu. Abgesehen von den intrinsischen Kosten ist es schlecht für die Cache-Vorhersage.

Wenn Sie eine echte zweidimensionale Anordnung wollen, legte in Speicher aus Zeilenhaupt Bestellung verwenden, würden Sie wollen, ...

int A[1000][1000]; 

Dies legt den Speicher fortlaufend in Reihe-Großauftrag aus, statt eines Arrays von Zeigern zu Arrays (die nicht zusammenhängend ausgelegt sind). Das Iterieren über dieses Array unter Verwendung von Zeilenmajor würde immer noch schneller als das Iterieren des Spaltenmajors aufgrund räumlicher Lokalisierung und Cache-Vorhersage durchführen.

Answer 3

Die kurze Antwort ist CPU-Caches. Scott Mayers erklärt es sehr klar here