Leistungsunterschied für Kontrollstrukturen 'für' und 'foreach' in C #

105

Welches Code-Snippet bietet eine bessere Leistung? Die folgenden Codesegmente wurden in C # geschrieben.

1.

for(int counter=0; counter<list.Count; counter++)
{
    list[counter].DoSomething();
}

2.

foreach(MyType current in list)
{
    current.DoSomething();
}
Kthevar
quelle
31
Ich stelle mir vor, dass es nicht wirklich wichtig ist. Wenn Sie Leistungsprobleme haben, liegt dies mit ziemlicher Sicherheit nicht daran. Nicht, dass Sie die Frage nicht stellen sollten ...
Darasd
2
Wenn Ihre App nicht sehr leistungskritisch ist, würde ich mir darüber keine Sorgen machen. Es ist weitaus besser, sauberen und leicht verständlichen Code zu haben.
Fortyrunner
2
Es macht mir Sorgen, dass einige der Antworten hier von Leuten gepostet werden, die einfach nirgendwo in ihrem Gehirn das Konzept eines Iterators haben und daher kein Konzept von Enumeratoren oder Zeigern.
Ed James
3
Dieser 2. Code wird nicht kompiliert. System.Object hat kein Mitglied namens 'value' (es sei denn, Sie sind wirklich böse, haben es als Erweiterungsmethode definiert und vergleichen Delegierte). Geben Sie Ihren foreach stark ein.
Trillian
1
Der erste Code wird auch nicht kompiliert, es sei denn, der Typ von hat listtatsächlich ein countMitglied anstelle von Count.
Jon Skeet

Antworten:

130

Nun, es hängt teilweise von der genauen Art ab list. Dies hängt auch von der genauen CLR ab, die Sie verwenden.

Ob es in irgendeiner Weise von Bedeutung ist oder nicht, hängt davon ab, ob Sie echte Arbeit in der Schleife leisten. In fast allen Fällen ist der Unterschied zur Leistung nicht signifikant, aber der Unterschied zur Lesbarkeit begünstigt die foreachSchleife.

Ich persönlich würde LINQ verwenden, um das "Wenn" zu vermeiden:

foreach (var item in list.Where(condition))
{
}

BEARBEITEN: Für diejenigen unter Ihnen, die behaupten, dass das Iterieren über a List<T>mit foreachdenselben Code wie die forSchleife erzeugt, gibt es hier Beweise dafür, dass dies nicht der Fall ist:

static void IterateOverList(List<object> list)
{
    foreach (object o in list)
    {
        Console.WriteLine(o);
    }
}

Produziert IL von:

.method private hidebysig static void  IterateOverList(class [mscorlib]System.Collections.Generic.List`1<object> list) cil managed
{
  // Code size       49 (0x31)
  .maxstack  1
  .locals init (object V_0,
           valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object> V_1)
  IL_0000:  ldarg.0
  IL_0001:  callvirt   instance valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!0> class [mscorlib]System.Collections.Generic.List`1<object>::GetEnumerator()
  IL_0006:  stloc.1
  .try
  {
    IL_0007:  br.s       IL_0017
    IL_0009:  ldloca.s   V_1
    IL_000b:  call       instance !0 valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>::get_Current()
    IL_0010:  stloc.0
    IL_0011:  ldloc.0
    IL_0012:  call       void [mscorlib]System.Console::WriteLine(object)
    IL_0017:  ldloca.s   V_1
    IL_0019:  call       instance bool valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>::MoveNext()
    IL_001e:  brtrue.s   IL_0009
    IL_0020:  leave.s    IL_0030
  }  // end .try
  finally
  {
    IL_0022:  ldloca.s   V_1
    IL_0024:  constrained. valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>
    IL_002a:  callvirt   instance void [mscorlib]System.IDisposable::Dispose()
    IL_002f:  endfinally
  }  // end handler
  IL_0030:  ret
} // end of method Test::IterateOverList

Der Compiler behandelt Arrays unterschiedlich und konvertiert eine foreachSchleife grundsätzlich in eine forSchleife, jedoch nicht List<T>. Hier ist der entsprechende Code für ein Array:

static void IterateOverArray(object[] array)
{
    foreach (object o in array)
    {
        Console.WriteLine(o);
    }
}

// Compiles into...

.method private hidebysig static void  IterateOverArray(object[] 'array') cil managed
{
  // Code size       27 (0x1b)
  .maxstack  2
  .locals init (object V_0,
           object[] V_1,
           int32 V_2)
  IL_0000:  ldarg.0
  IL_0001:  stloc.1
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.2
  IL_0004:  br.s       IL_0014
  IL_0006:  ldloc.1
  IL_0007:  ldloc.2
  IL_0008:  ldelem.ref
  IL_0009:  stloc.0
  IL_000a:  ldloc.0
  IL_000b:  call       void [mscorlib]System.Console::WriteLine(object)
  IL_0010:  ldloc.2
  IL_0011:  ldc.i4.1
  IL_0012:  add
  IL_0013:  stloc.2
  IL_0014:  ldloc.2
  IL_0015:  ldloc.1
  IL_0016:  ldlen
  IL_0017:  conv.i4
  IL_0018:  blt.s      IL_0006
  IL_001a:  ret
} // end of method Test::IterateOverArray

Interessanterweise kann ich dies nirgendwo in der C # 3-Spezifikation finden ...

Jon Skeet
quelle
Aus Interesse Jon, das Szenario mit Liste <T> oben ... gilt das auch für andere Sammlungen? Und woher wusstest du das (ohne dass Böswilligkeit beabsichtigt war) ... wie in ... bist du buchstäblich darüber gestolpert, als du vor einiger Zeit versucht hast, diese Frage zu beantworten? Es ist so ... zufällig / geheim :)
Pure.Krome
5
Ich bin mir der Array-Optimierungen schon eine Weile bewusst - Arrays sind eine "Kern" -Sammlung; Der C # -Compiler ist sich ihrer bereits sehr bewusst, daher ist es sinnvoll, sie anders zu behandeln. Der Compiler hat (und sollte) keine besonderen Kenntnisse darüber List<T>.
Jon Skeet
Cheers :) und yeah ... Arrays waren das erste Sammlungskonzept, das mir vor Jahren an der Uni beigebracht wurde. Es würde also Sinn machen, dass der Compiler klug genug ist, um mit einem der (wenn nicht dem) primitivsten Typen umzugehen Sammlung. Prost nochmal!
Pure.Krome
3
@JonSkeet Wenn Sie den Listeniterator entfernen, ändert sich das Verhalten, wenn die Liste während der Iteration geändert wird. Sie verlieren die Ausnahme, wenn sie geändert wird. Es ist weiterhin möglich zu optimieren, es muss jedoch überprüft werden, ob keine Änderungen vorgenommen wurden (auch bei anderen Threads, nehme ich an).
Craig Gidney
5
@VeeKeyBee: So sagte Microsoft im Jahr 2004. a) Dinge ändern sich; b) Die Arbeit müsste bei jeder Iteration winzige Mengen an Arbeit leisten, damit dies signifikant ist. Beachten Sie, dass foreachüber ein Array forsowieso gleichbedeutend ist. Immer Code zur besseren Lesbarkeit zuerst, dann nur Mikro-optimize , wenn Sie haben Beweise , dass es einen messbaren Leistungsvorteil ergibt.
Jon Skeet
15

Eine forSchleife wird zu einem Code kompiliert, der ungefähr dem entspricht:

int tempCount = 0;
while (tempCount < list.Count)
{
    if (list[tempCount].value == value)
    {
        // Do something
    }
    tempCount++;
}

Wobei als foreachSchleife ein Code kompiliert wird, der ungefähr dem entspricht:

using (IEnumerator<T> e = list.GetEnumerator())
{
    while (e.MoveNext())
    {
        T o = (MyClass)e.Current;
        if (row.value == value)
        {
            // Do something
        }
    }
}

Wie Sie sehen, hängt alles davon ab, wie der Enumerator implementiert ist und wie der Listenindexer implementiert ist. Wie sich herausstellt, wird der Enumerator für auf Arrays basierende Typen normalerweise wie folgt geschrieben:

private static IEnumerable<T> MyEnum(List<T> list)
{
    for (int i = 0; i < list.Count; i++)
    {
        yield return list[i];
    }
}

Wie Sie sehen, macht es in diesem Fall keinen großen Unterschied, aber der Enumerator für eine verknüpfte Liste würde wahrscheinlich ungefähr so ​​aussehen:

private static IEnumerable<T> MyEnum(LinkedList<T> list)
{
    LinkedListNode<T> current = list.First;
    do
    {
        yield return current.Value;
        current = current.Next;
    }
    while (current != null);
}

In .NET werden Sie feststellen, dass die LinkedList <T> -Klasse nicht einmal über einen Indexer verfügt, sodass Sie Ihre for-Schleife nicht für eine verknüpfte Liste ausführen können. aber wenn Sie könnten, müsste der Indexer so geschrieben werden:

public T this[int index]
{
       LinkedListNode<T> current = this.First;
       for (int i = 1; i <= index; i++)
       {
            current = current.Next;
       }
       return current.value;
}

Wie Sie sehen können, ist das mehrmalige Aufrufen in einer Schleife viel langsamer als die Verwendung eines Enumerators, der sich daran erinnern kann, wo er sich in der Liste befindet.

Martin Brown
quelle
12

Ein einfacher Test zur Halbvalidierung. Ich habe einen kleinen Test gemacht, nur um zu sehen. Hier ist der Code:

static void Main(string[] args)
{
    List<int> intList = new List<int>();

    for (int i = 0; i < 10000000; i++)
    {
        intList.Add(i);
    }

    DateTime timeStarted = DateTime.Now;
    for (int i = 0; i < intList.Count; i++)
    {
        int foo = intList[i] * 2;
        if (foo % 2 == 0)
        {
        }
    }

    TimeSpan finished = DateTime.Now - timeStarted;

    Console.WriteLine(finished.TotalMilliseconds.ToString());
    Console.Read();

}

Und hier ist der foreach-Abschnitt:

foreach (int i in intList)
{
    int foo = i * 2;
    if (foo % 2 == 0)
    {
    }
}

Als ich das for durch ein foreach ersetzte - das foreach war 20 Millisekunden schneller - konstant . Das For war 135-139 ms, während das Foreach 113-119 ms betrug. Ich habe mehrmals hin und her gewechselt, um sicherzugehen, dass es kein Prozess war, der gerade erst begonnen hat.

Als ich jedoch das foo und die if-Anweisung entfernte, war das for um 30 ms schneller (foreach war 88 ms und for war 59 ms). Sie waren beide leere Muscheln. Ich gehe davon aus, dass foreach tatsächlich eine Variable übergeben hat, bei der for nur eine Variable inkrementiert hat. Wenn ich hinzufügte

int foo = intList[i];

Dann wird das for um ca. 30ms langsam. Ich gehe davon aus, dass dies damit zu tun hat, dass foo erstellt, die Variable im Array erfasst und foo zugewiesen wird. Wenn Sie nur auf intList [i] zugreifen, haben Sie diese Strafe nicht.

Um ehrlich zu sein. Ich habe erwartet, dass der Foreach unter allen Umständen etwas langsamer ist, aber nicht genug, um in den meisten Anwendungen eine Rolle zu spielen.

Bearbeiten: Hier ist der neue Code mit Jons Vorschlägen (134217728 ist der größte Int, den Sie haben können, bevor die System.OutOfMemory-Ausnahme ausgelöst wird):

static void Main(string[] args)
{
    List<int> intList = new List<int>();

    Console.WriteLine("Generating data.");
    for (int i = 0; i < 134217728 ; i++)
    {
        intList.Add(i);
    }

    Console.Write("Calculating for loop:\t\t");

    Stopwatch time = new Stopwatch();
    time.Start();
    for (int i = 0; i < intList.Count; i++)
    {
        int foo = intList[i] * 2;
        if (foo % 2 == 0)
        {
        }
    }

    time.Stop();
    Console.WriteLine(time.ElapsedMilliseconds.ToString() + "ms");
    Console.Write("Calculating foreach loop:\t");
    time.Reset();
    time.Start();

    foreach (int i in intList)
    {
        int foo = i * 2;
        if (foo % 2 == 0)
        {
        }
    }

    time.Stop();

    Console.WriteLine(time.ElapsedMilliseconds.ToString() + "ms");
    Console.Read();
}

Und hier sind die Ergebnisse:

Daten generieren. Berechnung für Schleife: 2458 ms Berechnung für jede Schleife: 2005 ms

Wenn Sie sie austauschen, um zu sehen, ob es sich um die Reihenfolge der Dinge handelt, erhalten Sie (fast) die gleichen Ergebnisse.

Kenny Mann
quelle
6
Es ist besser, Stoppuhr als DateTime zu verwenden. Jetzt - und ich würde keinem Lauf so schnell vertrauen, um ehrlich zu sein.
Jon Skeet
8
Ihre foreach-Schleifen werden schneller ausgeführt, da ein 'for' die Bedingung bei jeder Iteration auswertet. In Ihrem Beispiel bedeutet dies einen zusätzlichen Methodenaufruf (um list.count zu erhalten). Kurz gesagt, Sie vergleichen zwei verschiedene Codeteile, daher Ihre seltsamen Ergebnisse. Versuchen Sie 'int max = intlist.Count; for (int i = 0; i <max; i ++) ... 'und die' for'-Schleife laufen erwartungsgemäß immer schneller!
AR
1
Nach und nach der Kompilierung optimieren Sie für und foreach genau das Gleiche, wenn Sie mit Grundelementen arbeiten. Erst wenn Sie List <T> einführen, unterscheiden sie sich (stark) in der Geschwindigkeit.
Anthony Russell
9

Hinweis: Diese Antwort gilt mehr für Java als für C #, da C # keinen Indexer aktiviert hat LinkedLists, aber ich denke, der allgemeine Punkt gilt immer noch.

Wenn es sich bei dem list, mit dem Sie arbeiten, um a handelt LinkedList, ist die Leistung des Indexer-Codes ( Zugriff im Array-Stil ) viel schlechter als bei Verwendung des IEnumeratorfrom -Codes foreachfür große Listen.

Wenn Sie LinkedListmit der Indexersyntax: auf ein Element 10.000 zugreifen list[10000], beginnt die verknüpfte Liste am NextKopfknoten und durchläuft den Zeiger zehntausend Mal, bis das richtige Objekt erreicht ist. Wenn Sie dies in einer Schleife tun, erhalten Sie natürlich:

list[0]; // head
list[1]; // head.Next
list[2]; // head.Next.Next
// etc.

Wenn Sie aufrufen GetEnumerator(implizit mit der forach-syntax), erhalten Sie ein IEnumeratorObjekt, das einen Zeiger auf den Kopfknoten hat. Bei jedem Aufruf MoveNextwird dieser Zeiger wie folgt zum nächsten Knoten verschoben:

IEnumerator em = list.GetEnumerator();  // Current points at head
em.MoveNext(); // Update Current to .Next
em.MoveNext(); // Update Current to .Next
em.MoveNext(); // Update Current to .Next
// etc.

Wie Sie sehen können, wird im Fall von LinkedLists die Array-Indexer-Methode immer langsamer, je länger Sie eine Schleife ausführen (sie muss immer wieder denselben Kopfzeiger durchlaufen). Während der IEnumerableGerechte in konstanter Zeit arbeitet.

Natürlich, wie Jon sagte, hängt dies wirklich von der Art ab list, wenn das listnicht ein LinkedList, sondern ein Array ist, ist das Verhalten völlig anders.

Tom Lokhorst
quelle
4
LinkedList in .NET verfügt nicht über einen Indexer, ist also eigentlich keine Option.
Jon Skeet
Na ja, das löst das Problem dann :-) Ich schaue mir nur die LinkedList<T>Dokumente auf MSDN an und es hat eine ziemlich anständige API. Am wichtigsten ist, dass es keine get(int index)Methode gibt, wie es Java tut. Dennoch denke ich, dass der Punkt immer noch für jede andere listenartige Datenstruktur gilt, die einen Indexer verfügbar macht, der langsamer als ein bestimmter ist IEnumerator.
Tom Lokhorst
2

Wie andere Leute bereits erwähnt haben, obwohl die Leistung eigentlich nicht viel ausmacht, wird der foreach aufgrund der IEnumerable/ IEnumeratorVerwendung in der Schleife immer etwas langsamer sein . Der Compiler übersetzt das Konstrukt in Aufrufe an dieser Schnittstelle und für jeden Schritt werden eine Funktion + eine Eigenschaft im foreach-Konstrukt aufgerufen.

IEnumerator iterator = ((IEnumerable)list).GetEnumerator();
while (iterator.MoveNext()) {
  var item = iterator.Current;
  // do stuff
}

Dies ist die äquivalente Erweiterung des Konstrukts in C #. Sie können sich vorstellen, wie sich die Auswirkungen auf die Leistung je nach den Implementierungen von MoveNext und Current unterscheiden können. Während bei einem Array-Zugriff diese Abhängigkeiten nicht bestehen.

Charles Prakash Dasari
quelle
4
Vergessen Sie nicht, dass es einen Unterschied zwischen einem Array-Zugriff und einem Indexer-Zugriff gibt. Wenn die Liste List<T>hier ist, gibt es immer noch den Treffer (möglicherweise inline), den Indexer aufzurufen. Es ist nicht so, als wäre es ein Bare-Metal-Array-Zugang.
Jon Skeet
Sehr richtig! Es ist eine weitere Eigenschaftsausführung, und wir sind der Implementierung ausgeliefert.
Charles Prakash Dasari
1

Nachdem ich genug Argumente gelesen habe, dass "die foreach-Schleife aus Gründen der Lesbarkeit bevorzugt werden sollte", kann ich sagen, dass meine erste Reaktion "was" war? Die Lesbarkeit ist im Allgemeinen subjektiv und in diesem speziellen Fall sogar noch größer. Für jemanden mit Programmierhintergrund (praktisch jede Sprache vor Java) sind for-Schleifen viel einfacher zu lesen als foreach-Schleifen. Darüber hinaus unterstützen dieselben Personen, die behaupten, dass foreach-Schleifen besser lesbar sind, auch linq und andere "Funktionen", die das Lesen und Verwalten von Code erschweren, was den obigen Punkt beweist.

Informationen zu den Auswirkungen auf die Leistung finden Sie in der Antwort auf diese Frage.

BEARBEITEN: Es gibt Sammlungen in C # (wie das HashSet), die keinen Indexer haben. In diesen Sammlungen foreach ist der einzige Weg zu iterieren , und es ist der einzige Fall , ich denke , es sollte verwendet werden , über für .

ThunderGr
quelle
0

Es gibt eine weitere interessante Tatsache, die beim Testen der Geschwindigkeit beider Schleifen leicht übersehen werden kann: Durch die Verwendung des Debug-Modus kann der Compiler den Code nicht mit den Standardeinstellungen optimieren.

Dies führte mich zu dem interessanten Ergebnis, dass foreach schneller ist als im Debug-Modus. Während das for im Release-Modus schneller ist als foreach. Offensichtlich hat der Compiler bessere Möglichkeiten, eine for-Schleife zu optimieren als eine foreach-Schleife, die mehrere Methodenaufrufe gefährdet. Eine for-Schleife ist übrigens so grundlegend, dass es möglich ist, dass dies sogar von der CPU selbst optimiert wird.

Sam
quelle
0

In dem von Ihnen angegebenen Beispiel ist es definitiv besser, eine foreachSchleife anstelle einer forSchleife zu verwenden.

Das Standardkonstrukt foreachkann schneller sein (1,5 Zyklen pro Schritt) als ein einfaches for-loop(2 Zyklen pro Schritt), es sei denn, die Schleife wurde abgewickelt (1,0 Zyklen pro Schritt).

Also für den täglichen Code ist, Leistung kein Grund , die komplexeren zu verwenden for, whileoder do-whileKonstrukte.

Schauen Sie sich diesen Link an: http://www.codeproject.com/Articles/146797/Fast-and-Less-Fast-Loops-in-C


╔══════════════════════╦═══════════╦═══════╦════════════════════════╦═════════════════════╗
        Method         List<int>  int[]  Ilist<int> onList<Int>  Ilist<int> on int[] 
╠══════════════════════╬═══════════╬═══════╬════════════════════════╬═════════════════════╣
 Time (ms)             23,80      17,56  92,33                   86,90               
 Transfer rate (GB/s)  2,82       3,82   0,73                    0,77                
 % Max                 25,2%      34,1%  6,5%                    6,9%                
 Cycles / read         3,97       2,93   15,41                   14,50               
 Reads / iteration     16         16     16                      16                  
 Cycles / iteration    63,5       46,9   246,5                   232,0               
╚══════════════════════╩═══════════╩═══════╩════════════════════════╩═════════════════════╝

rpax
quelle
4
Möglicherweise lesen Sie den von Ihnen verknüpften Code-Projektartikel erneut. Es ist ein interessanter Artikel, aber er sagt das genaue Gegenteil Ihres Beitrags. Außerdem erstellt die von Ihnen neu erstellte Tabelle die Leistung beim direkten Zugriff auf ein Array und eine Liste oder über deren IList-Schnittstellen. Weder haben etwas mit der Frage zu tun. :)
Paul Walls
0

Sie können darüber in Deep .NET - Teil 1 Iteration lesen

Es deckt die Ergebnisse (ohne die erste Initialisierung) vom .NET-Quellcode bis zur Demontage ab.

Beispiel: Array-Iteration mit einer foreach-Schleife: Geben Sie hier die Bildbeschreibung ein

und - Iteration mit foreach-Schleife auflisten: Geben Sie hier die Bildbeschreibung ein

und das Endergebnis: Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

Oder Yaacov
quelle