Warum beeinflusst die Reihenfolge der Schleifen die Leistung bei der Iteration über ein 2D-Array?

Question

Nachfolgend finden Sie zwei Programme, die fast identisch sind, mit der Ausnahme, dass ich die i y j Variablen um. Sie laufen beide in unterschiedlichen Zeitabständen. Kann mir 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; }
   }
}

Answer 1

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

Sie haben ein 2-dimensionales Feld, aber der Speicher im Computer ist von Natur aus 1-dimensional. Stellen Sie sich Ihr Array also wie folgt vor:

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 sie als eine einzige 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 eine Schleife über die zweite Zahl ziehen, d.h.:

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

Das bedeutet, dass du sie alle der Reihe nach triffst. Schauen Sie sich nun die 1. Version an. Sie tun:

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 angeordnet hat, bitten Sie es, überall hin zu springen. Aber jetzt kommt der Knackpunkt: Warum ist das wichtig? Alle Speicherzugriffe sind doch gleich, oder?

Nein: wegen der Caches. Daten aus dem Arbeitsspeicher werden in kleinen Stücken (so genannten "Cache-Zeilen") zur CPU übertragen, in der Regel 64 Byte. 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 Speicherstücke zu holen; Ihre CPU kann in der Zeit, die eine einzelne Cache-Zeile zum Laden braucht, eine Menge Arbeit erledigen.

Schauen Sie sich nun die Reihenfolge der Zugriffe an: Im zweiten Beispiel wird (1) ein Stück von 16 Ints gegriffen, (2) alle geändert, (3) 4000*4000/16 Mal wiederholt. Das ist schön und schnell, und die CPU hat immer etwas zu tun.

Das erste Beispiel besteht darin, (1) ein Stück von 16 Ints zu nehmen, (2) nur eines davon zu ändern, (3) 4000*4000 Mal zu wiederholen. Das erfordert die 16-fache Anzahl von "Abrufen" aus dem Speicher. Ihre CPU muss also Zeit damit verbringen, darauf zu warten, dass der Speicher auftaucht, und währenddessen verschwenden Sie wertvolle Zeit.

Wichtiger Hinweis:

Nun, da Sie die Antwort kennen, noch ein interessanter Hinweis: Es gibt keinen zwingenden Grund dafür, dass Ihr zweites Beispiel das schnelle sein muss. In Fortran zum Beispiel wäre das erste Beispiel schnell und das zweite langsam. Das liegt daran, dass Fortran die Dinge nicht wie C in konzeptionelle "Zeilen" expandiert, sondern in "Spalten", d.h.:

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 wird als "Zeilen-Dur" und das von Fortran als "Spalten-Dur" bezeichnet. Wie Sie sehen, ist es sehr wichtig zu wissen, ob Ihre Programmiersprache zeilenmajor oder spaltenmajor ist! Hier ist ein Link für weitere Informationen: http://en.wikipedia.org/wiki/Row-major_order

Answer 2

Das hat nichts mit Montage zu tun. Dies ist zurückzuführen auf Cache-Missgeschicke .

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

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

Answer 3

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

Version 1 hingegen greift auf die Elemente spaltenweise und nicht zeilenweise zu. Diese Art des Zugriffs ist auf Speicherebene nicht zusammenhängend, so dass das Programm die Zwischenspeicherung des Betriebssystems nicht so stark nutzen kann.

Answer 4

Der Grund dafür ist der cache-lokale Datenzugriff. Im zweiten Programm durchsuchen Sie den Speicher linear, was durch Caching und Prefetching begünstigt wird. Das Speichernutzungsmuster Ihres ersten Programms ist viel breiter gestreut und hat daher ein schlechteres Cache-Verhalten.

Answer 5

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

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

Dies ist bei der ersten Schleife weniger wahrscheinlich, da sie den Zeiger "p" jedes Mal um 4000 erhöhen müsste.

EDITAR: p++ und sogar *p++ = .. kann in den meisten CPUs zu einem einzigen CPU-Befehl kompiliert werden. *p = ..; p += 4000 nicht, so dass eine Optimierung weniger sinnvoll ist. Es ist auch schwieriger, weil der Compiler die Größe des inneren Arrays kennen und verwenden muss. Außerdem kommt es in der inneren Schleife in normalem Code nicht so häufig vor (es kommt nur bei mehrdimensionalen Arrays vor, bei denen der letzte Index in der Schleife konstant gehalten wird und der vorletzte Index gestuft wird), so dass die Optimierung weniger wichtig ist.