Performance difference for control structures 'for' and 'foreach' in C#

Which code snippet will give better performance? The below code segments were written in C#.

1.

for(int tempCount=0;tempCount<list.count;tempcount++)
{
    if(list[tempCount].value==value)
    {
        // Some code.
    }
}
foreach(object row in list)
{
    if(row.value==value)
    {
        //Some coding
    }
}

Solution 1:

Well, it partly depends on the exact type of list. It will also depend on the exact CLR you're using.

Whether it's in any way significant or not will depend on whether you're doing any real work in the loop. In almost all cases, the difference to performance won't be significant, but the difference to readability favours the foreach loop.

I'd personally use LINQ to avoid the "if" too:

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

EDIT: For those of you who are claiming that iterating over a List<T> with foreach produces the same code as the for loop, here's evidence that it doesn't:

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

Produces IL of:

.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

The compiler treats arrays differently, converting a foreach loop basically to a for loop, but not List<T>. Here's the equivalent code for an 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

Interestingly, I can't find this documented in the C# 3 spec anywhere...

Solution 2:

A for loop gets compiled to code approximately equivalent to this:

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

Where as a foreach loop gets compiled to code approximately equivalent to this:

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

So as you can see, it would all depend upon how the enumerator is implemented versus how the lists indexer is implemented. As it turns out the enumerator for types based on arrays are normally written something like this:

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

So as you can see, in this instance it won't make very much difference, however the enumerator for a linked list would probably look something like this:

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 you will find that the LinkedList<T> class does not even have an indexer, so you wouldn't be able to do your for loop on a linked list; but if you could, the indexer would have to be written like so:

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

As you can see, calling this multiple times in a loop is going to be much slower than using an enumerator that can remember where it is in the list.

Solution 3:

An easy test to semi-validate. I did a small test, just to see. Here is the 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();

}

And here is the foreach section:

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

When I replaced the for with a foreach -- the foreach was 20 milliseconds faster -- consistently. The for was 135-139ms while the foreach was 113-119ms. I swapped back and forth several times, making sure it wasn't some process that just kicked in.

However, when I removed the foo and the if statement, the for was faster by 30 ms (foreach was 88ms and for was 59ms). They were both empty shells. I'm assuming the foreach actually passed a variable where as the for was just incrementing a variable. If I added

int foo = intList[i];

Then the for become slow by about 30ms. I'm assuming this had to do with it creating foo and grabbing the variable in the array and assigning it to foo. If you just access intList[i] then you don't have that penalty.

In all honesty.. I expected the foreach to be slightly slower in all circumstances, but not enough to matter in most applications.

edit: here is the new code using Jons suggestions (134217728 is the biggest int you can have before System.OutOfMemory exception gets thrown):

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();
}

And here are the results:

Generating data. Calculating for loop: 2458ms Calculating foreach loop: 2005ms

Swapping them around to see if it deals with the order of things yields the same results (nearly).

Solution 4:

Note: this answer applies more to Java than it does to C#, since C# doesn't have an indexer on LinkedLists, but I think the general point still holds.

If the list you're working with happens to be a LinkedList, the performance of the indexer-code (array-style accessing) is a lot worse than using the IEnumerator from the foreach, for large lists.

When you access element 10.000 in a LinkedList using the indexer syntax: list[10000], the linked list will start at the head node, and traverse the Next-pointer ten thousand times, until it reaches the correct object. Obviously, if you do this in a loop, you will get:

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

When you call GetEnumerator (implicitly using the forach-syntax), you'll get an IEnumerator object that has a pointer to the head node. Each time you call MoveNext, that pointer is moved to the next node, like so:

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.

As you can see, in the case of LinkedLists, the array indexer method becomes slower and slower, the longer you loop (it has to go through the same head pointer over and over again). Whereas the IEnumerable just operates in constant time.

Of course, as Jon said this really depends on the type of list, if the list is not a LinkedList, but an array, the behavior is completely different.