Warum ist es schlimmer, ein zweidimensionales Array wie dieses zu initialisieren?

Question

for(int i = 0; i<100; i++) 

    for(int j = 0; j<100; j++) 

     array[j][i] = 0; 
     // array[i][j] = 0; 

Mein Professor sagte, es sei viel kostspieliger, ein zweidimensionales Array auf die erste Weise im Gegensatz zu der zweiten zu initialisieren. Kann jemand erklären, was unter der Motorhaube vor sich geht, die das macht? Oder haben die beiden Initialisierungsmethoden dieselbe Leistung?

Answer 1

Als @dlev erwähnt, ist dies aufgrund locality of reference und hat damit zu tun, wie die physische Hardware im Computer funktioniert.

Im Computer gibt es viele verschiedene Arten von Speicher. Typischerweise können nur bestimmte Speicherstellen (Register) tatsächliche Operationen an ihnen ausführen; den Rest der Zeit, wenn Sie Operationen auf Daten durchführen, müssen Sie es aus dem Speicher in ein Register laden, einige Berechnungen durchführen, dann schreiben Sie es zurück.

Hauptspeicher (RAM) ist viel, viel langsamer als Register, oft um einen Faktor von Hunderten oder Tausenden. Folglich sollte das Lesen aus dem Speicher möglichst vermieden werden. Um dies zu beheben, verfügen die meisten Computer in der Regel über spezielle Speicherbereiche mit der Bezeichnung caches. Die Aufgabe des Cachespeichers besteht darin, Daten aufzubewahren, auf die kürzlich aus dem Speicher zugegriffen wurde, so dass, wenn auf denselben Speicherbereich erneut zugegriffen wird, der Wert aus dem Cache (schnell) anstatt aus dem Hauptspeicher (langsam) gezogen werden kann. Normalerweise werden Caches so entworfen, dass, wenn ein Wert aus dem Speicher eingelesen wird, dieser Wert plus eine ganze Reihe benachbarter Werte in den Cache gezogen wird. Wenn Sie also über ein Array iterieren, werden nach dem Lesen des ersten Werts die restlichen Werte aus dem Array im Cache gespeichert und können effizienter abgerufen werden.

Der Grund dafür, dass Ihr Code langsamer ist, als er sein muss, besteht darin, dass er nicht sequentiell auf die Array-Elemente zugreift. In C sind 2D-Arrays in row-major order angelegt, was bedeutet, dass der Speicher als

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ... 

Folglich angeordnet ist, wenn Sie diese für Schleife verwenden:

for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
     // Do something with A[i][j] 
    } 
} 

Dazu ausgezeichnete Lokalität bekommen, da werden Sie Zugriff auf Array-Elemente in der Reihenfolge, in der sie im Speicher erscheinen. Dies macht die Anzahl der Lesevorgänge des Hauptspeichers sehr klein, da sich alles typischerweise im Cache befindet und betriebsbereit ist.

Allerdings, wenn Sie die Schleifen austauschen, wie Sie getan haben, springen Ihre Zugriffe im Speicher und sind nicht unbedingt aufeinander folgend. Dies bedeutet, dass Sie viele Cache-Fehler haben, in denen die Speicheradresse, die Sie als nächstes lesen, nicht im Cache ist. Dies erhöht die Anzahl der Cache-Ladevorgänge, was das Programm dramatisch verlangsamen kann.

Compiler werden immer intelligenter, um solche Schleifen automatisch auszutauschen, aber wir sind immer noch weit davon entfernt, diese Details ignorieren zu können. Wenn Sie C- oder C++ - Code für mehrdimensionale Arrays schreiben, sollten Sie in der Regel versuchen, in der Reihenfolge der Zeilenreihenfolge und nicht der Spaltenreihenfolge zu iterieren. Sie können bemerkenswerte Beschleunigungen in Ihrem Programm bekommen.

Hoffe, das hilft!

Answer 2

Wenn Sie sich die Speicherorte ansehen, auf die die einzelnen Methoden zugreifen, greift die zweite auf aufeinanderfolgende Bytes zu, während die erste um 100-Byte-Sprünge springt. Der Speicher-Cache wird viel effizienter arbeiten, wenn Sie es auf die zweite Art tun.

Answer 3

Ich werde wahrscheinlich Downvoted dafür bekommen, aber wenn Sie C programmieren, dann ist die "beste" ist höchstwahrscheinlich:

memset (array, 0, sizeof (array));

Dann können Sie alle Verantwortung der Optimierung (die Sie offensichtlich besorgt sind) auf die Implementierung von Memset verschieben. Irgendwelche spezifischen Hardware-Vorteile können dort gemacht werden.

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

Eine weitere Beobachtung ist, dass, wenn Sie auf Null init'ing, fragen Sie sich, warum? Wenn Ihr Array statisch ist (was wahrscheinlich für diese Größe ist?), Wird cstartup für Sie auf Null initialisiert. Auch dies wird wahrscheinlich den effizientesten Weg für Ihre Hardware nutzen.

Answer 4

Ich bin ein bisschen spät auf die Party, und es gibt bereits eine ausgezeichnete Antwort. Ich dachte jedoch, ich könnte einen Beitrag leisten, indem ich demonstriere, wie man diese Frage mit einem Profiling-Tool (unter Linux) experimentell beantworten kann.

Ich werde das perf Werkzeug im Ubuntu 10.10 Paket linux-tools-common verwenden.

Hier ist das kleine C Programm, das ich diese Frage zu beantworten schrieb:

// test.c 
#define DIM 1024 

int main() 
{ 
    int v[DIM][DIM]; 
    unsigned i, j; 

    for (i = 0; i < DIM; i++) { 
     for (j = 0; j < DIM; j++) { 
#ifdef ROW_MAJOR_ORDER 
      v[i][j] = 0; 
#else 
      v[j][i] = 0; 
#endif 
     } 
    } 

    return 0; 
} 

kompilieren Sie die zwei verschiedenen Versionen:

$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj 
$ gcc test.c -O0 -o row-min 

Hinweis Ich habe deaktiviert Optimierung mit -O0 so gcc keine Chance hat um unsere Schleife effizienter zu gestalten.

Wir können die verfügbaren Leistungsstatistiken mit perf unter perf list auflisten. In diesem Fall sind wir an Cache-Fehlern interessiert, bei denen es sich um das Ereignis cache-misses handelt.

Jetzt ist es so einfach wie jede Version des Programms mehrmals ausgeführt und nehmen einen Durchschnitt:

$ perf stat -e cache-misses -r 100 ./row-min 

Performance counter stats for './row-min' (100 runs): 

      286468 cache-misses    (+- 0.810%) 

     0.016588860 seconds time elapsed (+- 0.926%) 

$ perf stat -e cache-misses -r 100 ./row-maj 

Performance counter stats for './row-maj' (100 runs): 

       9594 cache-misses    (+- 1.203%) 

     0.006791615 seconds time elapsed (+- 0.840%) 

Und jetzt haben wir experimentell verifiziert, dass Sie in der Tat sehen zwei Größenordnungen mehr Cache-Misses tun mit die "row-minor" -Version.