wake-up-neo.net

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

Unten sind zwei Programme aufgeführt, die fast identisch sind, mit der Ausnahme, dass ich die Variablen i und j vertauscht habe. Sie laufen beide in unterschiedlichen Zeiträumen. Könnte jemand erklären, warum dies 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; }
   }
}
344
Mark

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

Sie haben ein zweidimensionales Array, aber der Arbeitsspeicher im Computer ist von Natur aus eindimensional. Stellen Sie sich Ihr Array folgendermaßen 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 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 zweiten Beispiel greifen Sie auf das Array zu, indem Sie zuerst die zweite Nummer durchlaufen, d. H .:

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

Das bedeutet, dass Sie alle in der richtigen Reihenfolge treffen. Nun schauen Sie sich die 1. Version an. 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 2D-Array im Speicher angeordnet hat, wird es aufgefordert, über den gesamten Bereich zu springen. Aber jetzt zum Kicker: Warum ist das wichtig? Alle Speicherzugriffe sind gleich, oder?

Nein: wegen Caches. Daten aus Ihrem Speicher werden in kleinen Blöcken (so genannten "Cache-Zeilen") (normalerweise 64 Byte) auf die CPU übertragen. Wenn Sie 4-Byte-Ganzzahlen haben, bedeutet dies, dass Sie 16 aufeinanderfolgende Ganzzahlen in einem ordentlichen kleinen Bündel erhalten. Tatsächlich ist es ziemlich langsam, diese Erinnerungsstücke abzurufen. Ihre CPU kann eine Menge 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 besteht darin, (1) einen Teil von 16 Zoll zu erfassen, (2) alle zu ändern, (3) 4000 * 4000/16-mal zu wiederholen. Das ist schön und schnell und die CPU hat immer etwas zu arbeiten.

Das erste Beispiel ist, (1) einen Block von 16 Zoll zu nehmen, (2) nur einen von ihnen zu modifizieren, (3) 4000 * 4000-mal zu wiederholen. Das wird das 16-fache der Anzahl von "Abrufen" aus dem Speicher erfordern. Ihre CPU wird tatsächlich Zeit damit verbringen müssen, herumzusitzen und auf das Auftauchen dieses Speichers zu warten, und während sie herumsitzt, verschwenden Sie wertvolle Zeit.

Wichtiger Hinweis:

Nun, da Sie die Antwort haben, ist hier eine interessante Anmerkung: Es gibt keinen inhärenten Grund, warum Ihr zweites Beispiel das schnelle sein muss. In Fortran wäre zum Beispiel das erste Beispiel schnell und das zweite langsam. Das liegt daran, dass Fortran die Dinge nicht wie in C in begriffliche "Zeilen" ausdehnt, 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 "Zeilendur" und Fortrans als "Spaltendur" bezeichnet. Wie Sie sehen, ist es sehr wichtig zu wissen, ob Ihre Programmiersprache Zeilen- oder Spaltenmajor ist! Hier ist ein Link für weitere Informationen: http://en.wikipedia.org/wiki/Row-major_order

574
Robert Martin

Nichts mit Montage zu tun. Dies liegt an Cache Misses .

C mehrdimensionale Arrays werden mit der letzten Dimension als der schnellsten gespeichert. Die erste Version wird also bei jeder Iteration den Cache verfehlen, 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 .

66

Version 2 wird viel schneller ausgeführt, da der Cache Ihres Computers besser als in Version 1 genutzt wird. Wenn Sie darüber nachdenken, sind Arrays nur zusammenhängende Speicherbereiche. Wenn Sie ein Element in einem Array anfordern, wird Ihr Betriebssystem wahrscheinlich eine Speicherseite in den Cache bringen, die dieses Element enthält. Da sich jedoch auch die nächsten Elemente auf dieser Seite befinden (weil sie zusammenhängend sind), befindet sich der nächste Zugriff bereits im Cache! Dies ist, was Version 2 tut, um es zu beschleunigen.

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

22
Oleksi

Der Grund ist der Cache-lokale Datenzugriff. Im zweiten Programm scannen Sie linear durch den Speicher, der vom Caching und Prefetching profitiert. Das Speicherverwendungsmuster Ihres ersten Programms ist weitaus weiter verbreitet und weist daher ein schlechteres Cache-Verhalten auf.

12

Neben den anderen hervorragenden Antworten auf Cache-Treffer 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 der Zeiger "p" jedes Mal um 4000 erhöht werden müsste.

EDIT:p++ und selbst *p++ = .. kann in den meisten CPUs zu einer einzelnen CPU-Anweisung kompiliert werden. *p = ..; p += 4000 kann nicht, daher ist die Optimierung weniger vorteilhaft. Es ist auch schwieriger, da der Compiler die Größe des inneren Arrays kennen und verwenden muss. Und es kommt nicht so oft in der inneren Schleife im normalen Code vor (es kommt nur bei mehrdimensionalen Arrays vor, bei denen der letzte Index in der Schleife konstant gehalten wird und der vorletzte schrittweise ausgeführt wird), sodass die Optimierung eine geringere Priorität hat .

10
fishinear

Diese Linie der Täter:

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

Die zweite Version verwendet kontinuierlichen Speicher und ist somit wesentlich schneller.

Ich habe es mit versucht

x[50000][50000];

und die Ausführungszeit beträgt 13s für Version1 gegenüber 0,6s für Version2.

7
Nicolas Modrzyk

Ich versuche eine generische Antwort zu geben.

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

Wenn Sie über y iterieren, iterieren Sie über Blöcke der Größe array_width * sizeof(array_element). Wenn Sie das in Ihrer inneren Schleife haben, werden Sie array_width * array_height Iterationen über diese Abschnitte haben.

Wenn Sie die Reihenfolge umkehren, erhalten Sie nur array_height - Chunk-Iterationen, und zwischen den Chunk-Iterationen erhalten Sie array_width - Iterationen von nur sizeof(array_element).

Während dies auf sehr alten x86-CPUs nicht viel ausmachte, werden heutzutage in x86 viele Daten vorab abgerufen und zwischengespeichert. Sie produzieren wahrscheinlich viele Cache-Fehlschläge in Ihrer langsameren Iterationsreihenfolge.

4
Sebastian Mach