Welche Reihenfolge von verschachtelten Schleifen zum Iterieren über ein 2D-Array ist effizienter [duplicate]

Lesezeit: 7 Minuten

Benutzeravatar von Sachin Mhetre
Sachin Metre

Welche der folgenden Reihenfolgen von verschachtelten Schleifen zum Durchlaufen eines 2D-Arrays ist zeiteffizienter (Cache-Leistung)? Wieso den?

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

oder

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}

  • Kleiner Hinweis: Verwenden Sie “++i” anstelle von “i++”. Es ist schneller (obwohl für Zahlen der Unterschied mit “i++” sehr klein ist, nicht wie für STL-Iteratoren).

    – Raxillan

    27. März 2012 um 11:02 Uhr

  • @Raxillan – dies gilt bei modernen Prozessoren und Compilern nicht mehr in allen Fällen, abhängig von der tatsächlichen Sprache.

    Benutzer177800

    27. März 2012 um 11:10 Uhr

  • @Raxillan das ist einfach falsch. Sie sind gleichermaßen effizient, es sei denn, Sie verwenden einen Compiler aus den 70er Jahren.

    – Luchian Grigore

    27. März 2012 um 11:10 Uhr

  • @Raxillan in diesem Fall nein. Der Optimierer ist intelligent genug, um zu wissen, dass er keine Kopie benötigt.

    – Luchian Grigore

    27. März 2012 um 11:19 Uhr

  • @ Raxillan Warum sollte es? Weder der neue noch der alte Wert werden im selben Ausdruck verwendet, und der Compiler weiß das. Warum sollte es also einen Unterschied machen?

    – glglgl

    27. März 2012 um 12:13 Uhr

Benutzeravatar von MByD
MByD

Die erste Methode ist etwas besser, da die zugewiesenen Zellen nebeneinander liegen.

Erste Methode:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

Zweite Methode:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment

  • Dies bedeutet, dass Sie weniger Cache-Fehler erhalten und der Prozessor besser einschätzen kann, auf welchen Speicher als nächstes zugegriffen wird.

    – tschap

    27. März 2012 um 11:18 Uhr

  • Raymond Chen hat einen etwas ähnlichen Beitrag in seinem Blog, mit Bildern und auch einer guten Erklärung: blogs.msdn.com/b/oldnewthing/archive/2005/08/05/448073.aspx. Stellen Sie sich eine Bitmap als ein größeres Array vor.

    – Chris

    27. März 2012 um 11:48 Uhr

  • Fun-Benchmark: Auf meinem speziellen Computer und Compiler (i5-Prozessor, Linux, gcc -O3) und mit einer viel größeren Matrix dauerte die erste Methode 2 Sekunden und die zweite 19 Sekunden.

    – Thomas Padron-McCarthy

    27. März 2012 um 11:54 Uhr


  • Benchmarks auf meinem Computer kamen ebenfalls zu dem Schluss, dass die erste Methode effizienter ist.

    – Jess Gut

    27. März 2012 um 11:57 Uhr

  • @Leo: wenn du eine zu schnelle innere Schleife hast, ja, sonst: nein. Die Sache ist, dass die Zugriffe im zweiten Fall immer noch sehr vorhersehbar sind (schrittweise), außer bei Spaltensprüngen, jede moderne CPU wird diese Cache-Zeilen vorab abrufen, bevor Sie sie brauchen.

    – KillianDS

    27. März 2012 um 14:45 Uhr


Benutzeravatar von amit
zustimmen

  1. Für Array[100][100] – Sie sind beide gleich, wenn der L1-Cache größer als 100*100*sizeof(int) == 10000*sizeof(int) == ist [usually] 40000. Hinweis in Sandy Bridge – 100*100 Ganzzahlen sollten ausreichen, um einen Unterschied zu sehen, da der L1-Cache nur 32 KB groß ist.

  2. Compiler werden diesen Code wahrscheinlich trotzdem optimieren

  3. Unter der Annahme, dass keine Compileroptimierungen vorgenommen wurden und die Matrix nicht in den L1-Cache passt, ist der erste Code aufgrund der Cacheleistung besser [usually]. Jedes Mal, wenn ein Element nicht im Cache gefunden wird, erhalten Sie eine Cache-Miss – und müssen in den RAM- oder L2-Cache gehen [which are much slower]. Elemente aus dem RAM in den Cache übernehmen [cache fill] erfolgt blockweise [usually 8/16 bytes] – so erhalten Sie im ersten Code maximal Missrate von 1/4 [assuming 16 bytes cache block, 4 bytes ints] während es im zweiten Code unbegrenzt ist und sogar 1 sein kann. Im zweiten Code Snap – Elemente, die bereits im Cache waren [inserted in the cache fill for the adjacent elements] – herausgenommen wurden, und Sie erhalten einen redundanten Cache-Mißerfolg.

    • Dies hängt eng mit der zusammen Prinzip der Lokalität, was die allgemeine Annahme ist, die beim Implementieren des Cache-Systems verwendet wird. Der erste Code folgt diesem Prinzip, der zweite nicht – die Cache-Leistung des ersten ist also besser als die des zweiten.

Fazit:
Bei allen Cache-Implementierungen, die mir bekannt sind, wird die erste nicht schlechter sein als die zweite. Sie könnten gleich sein – wenn überhaupt kein Cache vorhanden ist oder das gesamte Array vollständig in den Cache passt – oder aufgrund der Compiler-Optimierung.

  • K…. Das bedeutet also, dass der erste immer effizient ist… Wir können viel schneller auf Elemente zugreifen…

    – Sachin Metre

    27. März 2012 um 11:07 Uhr

  • @SachinMhetre: Für alle Cache-Implementierungen, die mir bekannt sind, wird die erste nicht schlechter sein als die zweite. Sie könnten gleich sein – wenn überhaupt kein Cache vorhanden ist oder das gesamte Array in den Cache passt.

    – amit

    27. März 2012 um 11:10 Uhr

  • Es ist wahrscheinlich erwähnenswert, dass es zwei Probleme gibt: wie lange es dauert, bis der Speicher vom L2-Cache zu den Registern gelangt, und die Bandbreite zwischen L2-Cache und Registern. Wenn dies nur eine Frage der Latenz wäre, dann könnte das Prefetching (entweder in Software oder Hardware) den größten Teil des Unterschieds zwischen den beiden Arten des Zugriffs auf die Daten eliminieren. Die harte Grenze hier ist jedoch Bandbreite; Da jeder Speicherzugriff eine ganze Cache-Zeile und nicht ein einzelnes Int liest, muss ein Zugriffsmuster mit Ihren Annahmen insgesamt viermal so viel Speicher lesen.

    Benutzer1084944

    28. Februar 2015 um 13:09 Uhr


  • @amit Könnten Sie bitte erklären, wie Sie diese Fehlraten geschätzt haben 1/4 und 1?

    – sgnsajgon

    17. Januar 2017 um 15:45 Uhr

Diese Art der Mikrooptimierung ist plattformabhängig, sodass Sie den Code profilieren müssen, um eine vernünftige Schlussfolgerung ziehen zu können.

  • Ich würde dafür stimmen, wenn jemand tatsächlich eine reale Plattform zeigen würde, bei der die erste Version langsamer war als die zweite. Ja, es ist Mikrooptimierung. Ja, es macht wahrscheinlich keinen merklichen Unterschied. Nein, Sie sollten Ihre Zeit nicht damit verschwenden, Ihre Schleifen neu zu schreiben, es sei denn, der Profiler gibt an, dass sie leistungskritisch sind. Aber wenn Sie zwischen zwei gleichermaßen einfachen, klaren und gültigen Möglichkeiten wählen müssen, um einen Code zu schreiben, und Sie kennen nur eine Faustregel, die besagt, dass einer von ihnen mindestens nicht langsamer ist als der andere, warum wählen Sie dann nicht den nicht langsameren?

    – Ilmari Karonen

    28. März 2012 um 3:41 Uhr


  • @IlmariKaronen Ich habe für deinen Kommentar gestimmt. Aber beachten Sie, dass es zumindest sprachabhängig ist. Fortran zum Beispiel legt das Array im Speicher umgekehrt an, so dass für Fortran die erste Version wahrscheinlich langsamer sein wird als die zweite.

    – fischnah

    19. Januar 2017 um 15:29 Uhr

Benutzeravatar von Michael Foukarakis
Michael Foukarakis

In Ihrem zweiten Snippet die Änderung in j erzeugt in jeder Iteration ein Muster mit geringer räumlicher Lokalität. Denken Sie daran, dass eine Array-Referenz im Hintergrund Folgendes berechnet:

( ((y) * (row->width)) + (x) ) 

Stellen Sie sich einen vereinfachten L1-Cache vor, der genügend Platz für nur 50 Zeilen unseres Arrays bietet. Für die ersten 50 Iterationen zahlen Sie die unvermeidbaren Kosten für 50 Cache-Misses, aber was passiert dann? Für jede Iteration von 50 bis 99 werden Sie immer noch Misses zwischenspeichern und müssen aus L2 (und/oder RAM usw.) abrufen. Dann, x ändert sich zu 1 und y beginnt von vorn, was zu einem weiteren Cache-Mißerfolg führt, da die erste Zeile Ihres Arrays aus dem Cache entfernt wurde, und so weiter.

Das erste Snippet hat dieses Problem nicht. Es greift auf das Array in zu Zeilenhauptordnungwodurch eine bessere Lokalität erreicht wird – Sie müssen nur höchstens einmal pro Zeile für Cache-Fehler bezahlen (wenn eine Zeile Ihres Arrays zu Beginn der Schleife nicht im Cache vorhanden ist).

Allerdings ist dies eine sehr architekturabhängige Frage, sodass Sie die Besonderheiten (L1-Cache-Größe, Cache-Zeilengröße usw.) berücksichtigen müssten, um eine Schlussfolgerung zu ziehen. Sie sollten auch beide Wege messen und Hardwareereignisse verfolgen, um konkrete Daten zu haben, aus denen Sie Rückschlüsse ziehen können.

In Anbetracht der Tatsache, dass C ++ ein Zeilenhaupt ist, glaube ich, dass die erste Methode etwas schneller sein wird. Im Speicher wird ein 2D-Array in einem Single-Dimension-Array dargestellt, und die Leistung hängt davon ab, ob der Zugriff darauf entweder mit Row Major oder Column Major erfolgt

Benutzeravatar von llj098
llj098

Dies ist ein klassisches Problem cache line bouncing

In den meisten Fällen ist der erste besser, aber ich denke, die genaue Antwort lautet: ES HÄNGT DAVON AB, OBunterschiedliche Architektur kann zu unterschiedlichen Ergebnissen führen.

Benutzeravatar von Parag
Parag

Bei der zweiten Methode Cache-Mißerfolg, weil der Cache zusammenhängende Daten speichert.
daher ist das erste Verfahren effizienter als das zweite Verfahren.

1416870cookie-checkWelche Reihenfolge von verschachtelten Schleifen zum Iterieren über ein 2D-Array ist effizienter [duplicate]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy