Performance difference for control structures 'for' and 'foreach' in C#
C#PerformanceFor LoopForeachC# Problem Overview
Which code snippet will give better performance? The below code segments were written in C#.
for(int tempCount=0;tempCount<list.count;tempcount++)
{
if(list[tempCount].value==value)
{
// Some code.
}
}
2.
foreach(object row in list)
{
if(row.value==value)
{
//Some coding
}
}
C# Solutions
Solution 1 - C#
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 - C#
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 - C#
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 - C#
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.
Solution 5 - C#
Like other people have mentioned though the performance doesn't actually matter much, the foreach will always be a little bit slower because of the IEnumerable/IEnumerator usage in the loop. The compiler translates the construct into calls on that interface and for every step a function + a property are called in the foreach construct.
IEnumerator iterator = ((IEnumerable)list).GetEnumerator();
while (iterator.MoveNext()) {
var item = iterator.Current;
// do stuff
}
This is the equivalent expansion of the construct in C#. You can imagine how the performance impact can vary based on the implementations of MoveNext and Current. Whereas in an array access, you don't have that dependencies.
Solution 6 - C#
After reading enough arguments that "the foreach loop should be preferred for readability", I can say that my first reaction was "what"? Readability, in general, is subjective and, in this particular instance, even more. For someone with a background in programming(practically, every language before Java), for loops are much easier to read than foreach loops. In addition, the same people claiming that foreach loops are more readable, are also supporters of linq and other "features" that make code hard to read and maintain, something that proves the above point.
About the impact on performance, see the answer to this question.
EDIT: There are collections in C#(like the HashSet) that have no indexer. In these collections, foreach is the only way to iterate and it is the only case I think it should be used over for.
Solution 7 - C#
There is a further interesting fact which can be easy missed when testing the speed of both loops: Using the debug mode doesn't let the compiler optimize the code using the default settings.
This led me to the interesting result that the foreach is faster than for in the debug mode. Whereas the for ist faster than foreach in the release mode. Obviously the compiler has better ways to optimize a for loop than a foreach loop which compromises several method calls. A for loop is by the way such fundamental that it's possible that this is even optimized by the CPU itself.
Solution 8 - C#
In the example you provided, it is definitely better to use foreach loop instead a for loop.
The standard foreach construct can be faster (1,5 cycles per step) than a simple for-loop (2 cycles per step), unless the loop has been unrolled (1.0 cycles per step).
So for everyday code, performance is not a reason to use the more complex for, while or do-while constructs.
Check out this link: 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 ║
╚══════════════════════╩═══════════╩═══════╩════════════════════════╩═════════════════════╝
Solution 9 - C#
you can read about it in Deep .NET - part 1 Iteration
it's cover the results (without the first initialization) from .NET source code all the way to the disassembly.
for example - Array Iteration with a foreach loop:
and - list iteration with foreach loop:
and the end results:
