Warum ist das Iterieren von 2D-Array-Zeilen-Major schneller als Spalten-Major?

Hier ist einfacher C++-Code, der das Iterieren von 2D-Array-Zeilenhauptwerten mit Spaltenhauptwerten 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 :

Zeilenmajor: 0,002431

Spaltengröße: 0,017186

d = 10^4 :

Zeilenmajor: 0,237995

Hauptspalte: 2.04471

d = 10^5

Zeilenmajor: 53,9561

Hauptspalte: 444.339

Nun stellt sich die Frage, warum Row Major schneller ist als Column Major?

Es hängt natürlich von der Maschine ab, auf der Sie sich befinden, aber ganz allgemein gesagt:

1. Ihr Computer speichert Teile des Arbeitsspeichers Ihres Programms in einem Cache, der eine viel geringere Latenz als der Hauptspeicher hat (selbst wenn die Cache-Trefferzeit kompensiert wird).

2. C-Arrays werden in einer fortlaufenden Hauptreihenfolge gespeichert. Das heißt, wenn Sie nach Element fragen xdann Element x+1 wird im Hauptspeicher an einer Stelle gespeichert, die direkt auf where folgt x wird gelagert.

3. Es ist typisch, dass Ihr Computer-Cache den Cache “präventiv” mit Speicheradressen füllt, die noch nicht verwendet wurden, die sich aber lokal in der Nähe des Speichers befinden, den Ihr Programm bereits verwendet hat. Stellen Sie sich Ihren Computer so vor, als würde er sagen: “Nun, Sie wollten Speicher an Adresse X, also gehe ich davon aus, dass Sie in Kürze Speicher an X + 1 wollen, deshalb werde ich das präventiv für Sie holen und in Ihren Cache legen.” .

Wenn Sie Ihr Array über die Reihenhauptreihenfolge aufzählen, zählen Sie es so auf, dass es zusammenhängend im Speicher gespeichert ist, und Ihr Computer hat sich bereits die Freiheit genommen, diese Adressen für Sie vorab in den Cache zu laden da es ahnte, dass Sie es wollten. Dadurch erreichen Sie eine höhere Rate an Cache-Treffern. Wenn Sie ein Array auf eine andere nicht zusammenhängende Weise aufzählen, wird Ihr Computer das von Ihnen angewendete Speicherzugriffsmuster wahrscheinlich nicht vorhersagen, sodass er nicht in der Lage ist, Speicheradressen präventiv für Sie in den Cache zu ziehen, und Sie haben gewonnen Es entstehen nicht so viele Cache-Hits, sodass auf den Hauptspeicher häufiger zugegriffen werden muss, was langsamer ist als Ihr Cache.

Auch dafür könnte es besser geeignet sein https://cs.stackexchange.com/ weil die Art und Weise, wie sich Ihr System-Cache verhält, in Hardware implementiert ist und räumliche Lokalitätsfragen dort besser geeignet zu sein scheinen.

Ihr Array ist eigentlich a zerlumptes Arrayalso ist der Zeilenmajor nicht unbedingt ein Faktor.

Sie sehen eine bessere Leistung beim Iterieren über Spalten als über Zeilen, da der Zeilenspeicher linear angeordnet ist, was für den Cache-Prädiktor durch sequenzielles Lesen leicht vorherzusagen ist, und Sie amortisieren die Dereferenzierung des Zeigers auf die zweite Dimension, da dies nur einmal erfolgen muss pro Zeile.

Wenn Sie über die Zeilen und dann über die Spalten iterieren, kommt es pro Iteration zu einer Zeigerdereferenzierung auf die zweite Dimension. Indem Sie Zeilen durchlaufen, fügen Sie also eine Zeiger-Dereferenzierung hinzu. Abgesehen von den intrinsischen Kosten ist es schlecht für die Cache-Vorhersage.

Wenn Sie ein echtes zweidimensionales Array wollen, das im Speicher mit Row-Major-Ordnung angeordnet ist, möchten Sie …

int A[1000][1000];

Dadurch wird der Speicher zusammenhängend in Zeilenhauptreihenfolge angeordnet, anstelle eines Arrays von Zeigern auf Arrays (die nicht zusammenhängend angeordnet sind). Das Iterieren über dieses Array unter Verwendung von Row-Major würde aufgrund der räumlichen Lokalität und der Cache-Vorhersage immer noch schneller ablaufen als das Iterieren von Column-Major.

Die kurze Antwort lautet CPU-Caches. Scott Mayers erklärt es sehr deutlich Hier