Warum wirkt sich die Reihenfolge der Schleifen auf die Leistung aus, wenn über ein 2D-Array iteriert wird?

Unten sind zwei Programme, die fast identisch sind, außer dass ich das umgeschaltet habe i und j Variablen herum. Beide laufen in unterschiedlichen Zeiträumen. Könnte jemand erklären, warum das passiert?

Version 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Version 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

Wie andere gesagt haben, ist das Problem das Speichern an der Speicherstelle im Array: x[i][j]. Hier ist ein kleiner Einblick, warum:

Sie haben ein zweidimensionales Array, aber der Speicher im Computer ist von Natur aus eindimensional. Während Sie sich Ihr Array also so vorstellen:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Ihr Computer speichert es als einzelne Zeile im Speicher:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

Im 2. Beispiel greifen Sie auf das Array zu, indem Sie zuerst die 2. Zahl durchlaufen, dh:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Das bedeutet, dass Sie sie alle der Reihe nach treffen. Betrachten Sie nun die 1. Version. Sie gehen:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Aufgrund der Art und Weise, wie C das 2-D-Array im Speicher angelegt hat, bitten Sie es, überall hin zu springen. Aber jetzt zum Kicker: Warum ist das wichtig? Alle Speicherzugriffe sind gleich, richtig?

Nein: wegen Caches. Daten aus Ihrem Arbeitsspeicher werden in kleinen Blöcken (als „Cache-Zeilen“ bezeichnet), typischerweise 64 Bytes, zur CPU übertragen. Wenn Sie 4-Byte-Ganzzahlen haben, bedeutet das, dass Sie 16 aufeinanderfolgende Ganzzahlen in einem hübschen kleinen Bündel erhalten. Es ist eigentlich ziemlich langsam, diese Speicherblöcke abzurufen; Ihre CPU kann viel Arbeit in der Zeit erledigen, die zum Laden einer einzelnen Cache-Zeile benötigt wird.

Schauen Sie sich nun die Reihenfolge der Zugriffe an: Das zweite Beispiel ist (1) ein Stück von 16 Ints zu greifen, (2) alle zu modifizieren, (3) 4000 * 4000/16 Mal zu wiederholen. Das ist schön schnell und die CPU hat immer etwas zu tun.

Das erste Beispiel ist (1) einen Block von 16 Ints nehmen, (2) nur einen davon ändern, (3) 4000*4000 Mal wiederholen. Das wird die 16-fache Anzahl von “Fetches” aus dem Speicher erfordern. Ihre CPU muss tatsächlich Zeit damit verbringen, herumzusitzen und darauf zu warten, dass dieser Speicher auftaucht, und während sie herumsitzt, verschwenden Sie wertvolle Zeit.

Wichtiger Hinweis:

Nun, da Sie die Antwort haben, hier ein interessanter Hinweis: Es gibt keinen inhärenten Grund dafür, dass Ihr zweites Beispiel das schnelle sein muss. Beispielsweise wäre in Fortran das erste Beispiel schnell und das zweite langsam. Das liegt daran, dass Fortran, anstatt Dinge in konzeptionelle “Zeilen” zu erweitern, wie es C tut, in “Spalten” erweitert, dh:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Das Layout von C heißt „row-major“ und das von Fortran „column-major“. Wie Sie sehen, ist es sehr wichtig zu wissen, ob Ihre Programmiersprache zeilen- oder spaltenorientiert ist! Hier ist ein Link für weitere Informationen: http://en.wikipedia.org/wiki/Row-major_order

Nichts mit Montage zu tun. Das ist wegen Cache-Fehlschläge.

C Mehrdimensionale Arrays werden mit der letzten Dimension als der schnellsten gespeichert. Die erste Version wird also den Cache bei jeder Iteration verpassen, während die zweite Version dies nicht tut. Die zweite Version sollte also wesentlich schneller sein.

Siehe auch: http://en.wikipedia.org/wiki/Loop_interchange.

Version 2 läuft viel schneller, da sie den Cache Ihres Computers besser nutzt als Version 1. Wenn Sie darüber nachdenken, sind Arrays nur zusammenhängende Speicherbereiche. Wenn Sie ein Element in einem Array anfordern, bringt Ihr Betriebssystem wahrscheinlich eine Speicherseite in den Cache, die dieses Element enthält. Da sich die nächsten paar Elemente jedoch auch auf dieser Seite befinden (weil sie zusammenhängend sind), wird der nächste Zugriff bereits im Cache sein! Dies ist, was Version 2 tut, um seine Geschwindigkeit zu erhöhen.

Version 1 hingegen greift spaltenweise und nicht zeilenweise auf Elemente zu. Diese Art des Zugriffs ist auf Speicherebene nicht zusammenhängend, sodass das Programm das OS-Caching nicht so stark nutzen kann.

Der Grund ist der Cache-lokale Datenzugriff. Im zweiten Programm scannen Sie den Speicher linear, was von Caching und Prefetching profitiert. Das Speichernutzungsmuster Ihres ersten Programms ist viel weiter verbreitet und hat daher ein schlechteres Cache-Verhalten.

Neben den anderen hervorragenden Antworten zu Cache-Treffern gibt es auch einen möglichen Optimierungsunterschied. Ihre zweite Schleife wird wahrscheinlich vom Compiler in etwas Äquivalentes optimiert:

for (j=0; j<4000; j++) {
  int *p = x[j];
  for (i=0; i<4000; i++) {
    *p++ = i+j;
  }
}

Dies ist für die erste Schleife weniger wahrscheinlich, da sie den Zeiger “p” jedes Mal um 4000 erhöhen müsste.

BEARBEITEN: p++ und sogar *p++ = .. kann in den meisten CPUs zu einem einzelnen CPU-Befehl kompiliert werden. *p = ..; p += 4000 kann, daher ist es weniger sinnvoll, es zu optimieren. Es ist auch schwieriger, weil der Compiler die Größe des inneren Arrays kennen und verwenden muss. Und es kommt in normalem Code in der inneren Schleife nicht so oft vor (es kommt nur bei mehrdimensionalen Arrays vor, bei denen der letzte Index in der Schleife konstant gehalten wird und der vorletzte schrittweise wird), sodass die Optimierung weniger Priorität hat .

Diese Zeile der Übeltäter:

x[j][i]=i+j;

Die zweite Version verwendet fortlaufenden Speicher und wird daher wesentlich schneller sein.

Ich habe es mit versucht

x[50000][50000];

und die Ausführungszeit beträgt 13 s für Version 1 gegenüber 0,6 s für Version 2.

_{Ich versuche eine allgemeine Antwort zu geben.}

Da i[y][x] ist eine Abkürzung für *(i + y*array_width + x) in C (probieren Sie die classy int P[3]; 0[P] = 0xBEEF;).

Während Sie iterieren yiterieren Sie über Größenblöcke array_width * sizeof(array_element). Wenn Sie das in Ihrer inneren Schleife haben, dann haben Sie es array_width * array_height Iterationen über diese Chunks.

Wenn Sie die Bestellung umdrehen, haben Sie nur noch array_height Chunk-Iterationen und zwischen allen Chunk-Iterationen haben array_width Iterationen von nur sizeof(array_element).

Während dies auf wirklich alten x86-CPUs keine große Rolle spielte, übernehmen die heutigen x86er eine Menge Prefetching und Caching von Daten. Sie produzieren wahrscheinlich viele Cache-Fehlschläge in Ihrer langsameren Iterationsreihenfolge.