Verwirrung um unterschiedliche Laufzeiten zweier Algorithmen in C [duplicate]

Ich habe ein Array, long matrix[8*1024][8*1024]und zwei Funktionen sum1 und sum2:

long sum1(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (i=0; i < ROWS; i++) {
        for (j=0; j < COLS; j++) {
            sum += m[i][j];
        }
    }
    return sum;
}

long sum2(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (j=0; j < COLS; j++) {
        for (i=0; i < ROWS; i++) {
            sum += m[i][j];
        }
    }

    return sum;
}

Wenn ich die beiden Funktionen mit dem angegebenen Array ausführe, erhalte ich Laufzeiten:

Summe1: 0,19 s

Summe2: 1,25 s

Kann mir jemand erklären, warum es diesen großen Unterschied gibt?

C verwendet Reihenmajor-Ordnung zum Speichern mehrdimensionaler Arrays, wie in dokumentiert § 6.5.2.1 Array-Subskription, Absatz 3 des C-Standards:

Aufeinanderfolgende tiefgestellte Operatoren bezeichnen ein Element eines mehrdimensionalen Array-Objekts. Wenn E ein n-dimensionales Array (n >= 2) mit den Dimensionen ixjx ist. . . xk, dann wird E (das nicht als lvalue verwendet wird) in einen Zeiger auf ein (n – 1)-dimensionales Array mit den Dimensionen jx konvertiert. . . x k. Wenn der unäre *-Operator explizit oder implizit als Ergebnis der Subskription auf diesen Zeiger angewendet wird, ist das Ergebnis das referenzierte (n – 1)-dimensionale Array, das selbst in einen Zeiger umgewandelt wird, wenn es nicht als Lvalue verwendet wird. Daraus folgt, dass Arrays in der Reihenfolge der wichtigsten Zeilen gespeichert werden (der letzte Index variiert am schnellsten).

Betonung von mir.

Hier ein Bild von Wikipedia das diese Speichertechnik im Vergleich zu der anderen Methode zum Speichern mehrdimensionaler Arrays demonstriert, Spalten-Major-Ordnung:

Die erste Funktion, sum1greift nacheinander auf Daten zu, wie das 2D-Array tatsächlich im Speicher dargestellt wird, sodass sich die Daten aus dem Array bereits im Cache befinden. sum2 erfordert das Abrufen einer anderen Zeile bei jeder Iteration, die sich mit geringerer Wahrscheinlichkeit im Cache befindet.

Es gibt einige andere Sprachen, die für mehrdimensionale Arrays die Sortierung nach Hauptspalten verwenden. darunter sind R, FORTRAN und MATLAB. Wenn Sie äquivalenten Code in diesen Sprachen geschrieben haben, würden Sie eine schnellere Ausgabe feststellen sum2.

Computer verwenden im Allgemeinen Zwischenspeicher um den Zugriff auf den Hauptspeicher zu beschleunigen.

Die normalerweise für den Hauptspeicher verwendete Hardware ist relativ langsam – es kann viele Prozessorzyklen dauern, bis Daten vom Hauptspeicher zum Prozessor gelangen. Ein Computer enthält also im Allgemeinen eine kleinere Menge an sehr schnellem, aber teurem Speicher, der als Cache bezeichnet wird. Computer können mehrere Cache-Ebenen haben, einige davon sind in den Prozessor oder den Prozessorchip selbst eingebaut und einige davon befinden sich außerhalb des Prozessorchips.

Da der Cache kleiner ist, kann er nicht alles im Hauptspeicher halten. Es kann oft nicht einmal alles aufnehmen, was ein Programm verwendet. Der Prozessor muss also Entscheidungen darüber treffen, was im Cache gespeichert wird.

Die häufigsten Zugriffe eines Programms erfolgen auf aufeinanderfolgende Stellen im Speicher. Nachdem ein Programm Element 237 eines Arrays gelesen hat, liest es sehr oft bald 238, dann 239 und so weiter. Es kommt seltener vor, dass 7024 direkt nach dem Lesen von 237 angezeigt wird.

Der Betrieb des Caches ist also so ausgelegt, dass Teile des Hauptspeichers, die aufeinander folgen, im Cache gehalten werden. Dein sum1 Das Programm funktioniert gut damit, weil es den Spaltenindex am schnellsten ändert und den Zeilenindex konstant hält, während alle Spalten verarbeitet werden. Die Array-Elemente, auf die es zugreift, werden nacheinander im Speicher angeordnet.

Dein sum2 Das Programm funktioniert damit nicht gut, da es den Zeilenindex am schnellsten ändert. Dies springt im Speicher herum, so dass viele der Zugriffe nicht vom Cache erfüllt werden und aus dem langsameren Hauptspeicher kommen müssen.

Zugehörige Ressource: Speicherlayout mehrdimensionaler Arrays

Auf einer Maschine mit Daten-Cache (sogar ein 68030 hat einen), ist das Lesen/Schreiben von Daten in aufeinanderfolgenden Speicherstellen viel schneller, da ein Speicherblock (Größe hängt vom Prozessor ab) einmal aus dem Speicher geholt und dann aus dem Cache abgerufen wird ( Leseoperation) oder auf einmal geschrieben (Cache-Flush für Schreiboperation).

Durch das “Überspringen” von Daten (Lesen weit entfernt vom vorherigen Lesen) muss die CPU den Speicher erneut lesen.

Deshalb ist Ihr erstes Snippet schneller.

Für komplexere Operationen (z. B. schnelle Fourier-Transformation), bei denen Daten mehr als einmal gelesen werden (im Gegensatz zu Ihrem Beispiel), schlagen viele Bibliotheken (z. B. FFTW) vor, a zu verwenden schreiten um Ihre Datenorganisation (in Zeilen/in Spalten) unterzubringen. Niemals Verwenden Sie es, transponieren Sie Ihre Daten immer zuerst und verwenden Sie einen Schritt von 1, es wird schneller sein, als zu versuchen, es ohne Transposition zu tun.

Um sicherzustellen, dass Ihre Daten fortlaufend sind, verwenden Sie niemals die 2D-Notation. Positionieren Sie zuerst Ihre Daten in der ausgewählten Zeile und setzen Sie einen Zeiger auf den Anfang der Zeile. Verwenden Sie dann eine innere Schleife für diese Zeile.

for (i=0; i < ROWS; i++) {
    const long *row = m[i];
    for (j=0; j < COLS; j++) {
        sum += row[j];
    }
}

Wenn Sie dies nicht können, bedeutet das, dass Ihre Daten falsch ausgerichtet sind.

Dies ist ein Problem mit dem Cache.

Der Cache liest automatisch Daten, die nach den von Ihnen angeforderten Daten liegen. Wenn Sie also die Daten Zeile für Zeile lesen, befinden sich die nächsten angeforderten Daten bereits im Cache.

Eine Matrix im Speicher ist linear ausgerichtet, sodass die Elemente in einer Reihe im Speicher nebeneinander liegen (spacial locality). Wenn Sie Elemente der Reihe nach so durchgehen, dass Sie alle Spalten in einer Reihe durchlaufen, bevor Sie zur nächsten übergehen, wird die CPU, wenn sie auf einen Eintrag stößt, der noch nicht in ihren Cache geladen wurde, diesen Wert mitladen mit einem ganzen Block anderer Werte in der Nähe im physischen Speicher, sodass die nächsten Werte bereits zwischengespeichert werden, wenn sie gelesen werden müssen.

Wenn Sie sie in die andere Richtung queren, werden die anderen geladenen Werte, die sich in der Nähe des Speichers befinden, nicht die nächsten gelesenen, sodass Sie am Ende viel mehr Cache-Fehler haben und die CPU sitzen und warten muss die Daten werden von der nächsten Schicht der Speicherhierarchie hereingebracht.

Wenn Sie zu einem anderen Eintrag zurückkehren, den Sie zuvor zwischengespeichert hatten, wurde er höchstwahrscheinlich zugunsten aller anderen Daten, die Sie seitdem geladen haben, aus dem Cache gebootet, da er in letzter Zeit nicht mehr verwendet wurde (temporal locality)

Um die anderen Antworten zu erweitern, dass dies auf Cache-Fehler für das zweite Programm zurückzuführen ist, und vorausgesetzt, dass Sie Linux, * BSD oder MacOS verwenden, kann Cachegrind Ihnen Erleuchtung verschaffen. Es ist Teil von valgrind und führt Ihr Programm ohne Änderungen aus und gibt die Cache-Nutzungsstatistik aus. Allerdings läuft er sehr langsam.

http://valgrind.org/docs/manual/cg-manual.html