foreach statt for

BAGZZlash

Moderator
Teammitglied
Ich habe zwei geschachtelte Schleifen, bei denen die innere Schleife immer Zeug aus dem Objekt holt, über das die äußere Schleife iteriert. Bisher hatte ich das mit zwei for-Schleifen gemacht, etwa so:

C#:
for (int i = 0; i < RiesigesObjekt.Count; i++) {
  for (int j = 0; j < RiesigesObjekt[i].Count; j++) {
    MachWasMit(RiesigesObjekt[i][j]);
  }
}

Bei einem Datensatz hat das immer gut über sechs Minuten gedauert. Nun habe ich einfach mal aus Spaß das Ganze durch zwei foreach-Schleifen ersetzt, etwa so:

C#:
foreach (Element e in RiesigesObjekt) {
  foreach (UnterElement u in e) { MachWasMit(u); }
}

Ergebnis: Das, was vorher immer deutlich über sechs Minuten gedauert hat, dauert jetzt weniger als zwei Sekunden! 😲 Woran mag das liegen? Ich könnte mir vorstellen, dass die Runtime sich bei der for-Variante immer wieder neu eine Referenz auf die Objekte holen muss, diese aber bei der foreach-Variante bestehen bleiben. Oder so. Was meint Ihr?
 
Das ist ja ein Riesenunterschied. Geht er auch wirklich durch alle Objekte durch?

Kannst ja mal gucken, wie das iterator/enumerable Interface implementiert ist und mit deinen For-Schleifen vergleichen.
 
Bin mit C# nicht sonderlich vertraut, aber ein paar Gedanken dazu ...
for (int i = 0; i < RiesigesObjekt.Count; i++) {
Bei jeder Iteration wird die Eigenschaft RiesigesObjekt.Count aus dem Objekt gelesen.
i++ ist theoretisch komplexer als ++i da der ursprüngliche Wert von i in einen Cache wandert um zurückgegeben zu werden nachdem i inkrementiert wurde.

for (int j = 0; j < RiesigesObjekt[i].Count; j++) {
Der Zugriff auf RiesigesObjekt[i].Count ist noch mal etwas komplexer. Wenn man davon ausgehen kann dass hinter den Kulissen mit Pointern gearbeitet wird, hast du hier so etwas wie "addiere i zum Pointer auf das erste Element, dereferenziere, und greife dann auf die Eigenschaft zu".

MachWasMit(RiesigesObjekt[i][j]);
Die gleiche Additions- und Dereferenzierungsgeschichte, nur im Doppelpack und wirklich in jeder Iteration die die innere Schleife jemals durchläuft.

Dagegen wird foreach in der Implementierung wohl letztlich einfach nur Pointer inkrementieren und dereferenzieren. Ich weiß aber nicht wie hoch hier das Abstraktionslevel ist und ob du jemals so tief in die Implementierung hinein schauen kannst um meine Theorien zu bestätigen oder zu widerlegen.
 
EDIT Wenn ich mir den Performanceunterschied anschaue, würde ich bei deinen Objekten von Linked List Implementierungen ausgehen, mit O(n) statt O(1) Komplexität für den Subscript Operator [], da wirklich jedes Element durchlaufen werden muss um den Pointer auf das nächste zu bekommen.
 
Hm, und wie macht man das?

Wenn das wie in Java ist, dann erwartet foreach eine Interface-Implementierung, die ihm sagt, wie über das Objekt iteriert werden soll. Wenn der bei dir die Standardimplementierung von Arrays nutzt, ist es vielleicht im Hintergrund parallelisiert.

Also das war meine erste Vermutung gewesen. Dass die Aufgabe beim foreach parallelisiert wird, weil er ungestört mit einer Kopie der Objekte arbeiten kann und bei den 2 for-schleifen hingegen jede Referenz und jeder Aufruf von MachWasMit(RiesigesObjekt[i][j]) blockiert. Der Unterschied ist einfach zu groß.

Aber vielleicht wirken sich tatsächlich die von @german erwähnten Overheads stärker aus als gedacht.
 
Ohne mich mit C# im Spezielle auszukennen, gingen meine ersten Gedanken auch in diese Richtung. RiesigesObjekt[i][j] bedeutet einen Zugriff auf RiesigesObjekt in jedem Durchlauf. Das schränkt die Auswahl möglicher Optimierungen stark ein, während foreach evtl. eine Parallelisierung, aggressiveres Unrolling und/oder weitere Optimierungen erlaubt.
 
Zurück
Oben Unten