Patrick Smacchia [MVP C#]

An easy and efficient way to improve .NET code performances

Currently, I am getting serious about measuring and improving performances of .NET code. I’ll post more about this topic within the next weeks. For today I would like to present an efficient optimization I found on something we all use massively: loops on collections. I talk here about the cost of the loop itself, i.e for and foreach instructions, not the cost of the code executed in the loop. I basically found that:

• for loops on List<T> are a bit more than 2 times cheaper than foreach loops on List<T>.

• Looping on array is around 2 times cheaper than looping on List<T>.

• As a consequence, looping on array using for is 5 times cheaper than looping on List<T> using foreach (which I believe, is what we all do).

The foreach syntax sugar is a blessing and for many complex loops it is not worth transforming foreach into for. But for certain kind of loops, like short loops made of one or two instructions nested in some other loops, these 5 times factor can become a huge bonus. And the good news is that the code of NDependhas plenty of these nested short loops because of algorithm such as Ranking, Level and dependencies transitive closure computation.

Here is the code used to benchmark all this:

static void IterateForeachOnList(List<int> list) { foreach(int i in list) { int j = i; } } static void IterateForOnListWithoutCountOptimization(List<int> list) { for(int i=0; i < list.Count; i++) { int j = list [ i ] ; } } static void IterateForOnListWithCountOptimization(List<int> list) { int count = list.Count; for (int i = 0; i < count; i++) { int j = list [ i ] ; } } static void IterateForeachOnArray(int[] array) { foreach (int i in array) { int j = i; } } static void IterateForOnArrayWithoutCountOptimization(int[] array) { for (int i = 0; i < array.Length; i++) { int j = array [ i ] ; } } static void IterateForOnArrayWithCountOptimization(int[] array) { int length = array.Length; for (int i = 0; i < length; i++) { int j = array [ i ] ; } }

Here are the results obtained with the System.Diagnostics.Stopwatch class:

The fact that for is more efficient than foreach results from the fact that foreach is using an enumerator object behind the scene.

The fact that iterating on array is cheaper than iterating on List<T> comes from the fact that the IL has instructions dedicated for array iteration. Here is the Reflector view of the methods:

In the console output, we can see that foreach on array is a tiny bit more costly than for on array. Interestingly enough, I just checked that the C# compiler doesn’t use an enumerator object behind the scene for foreach on array.

Some more interesting finding. The profiler dotTrace v3.1 gives some unrealistic results for this benchmark. IterateForeachOnList is deemed more than 40 times more costly than IterateForOnArray (instead of 5 times). I tested both RecordThreadTime and RecordWallTime mode of the profiler:

Thus I also ran the benchmark with ANTS Profiler v4.1 and got some more realistic results, still not perfect however (IterateForeachOnList is now deemed 8 times more costly than IterateForOnArray,instead of 5 times).

You can download the code of the benchmark here. All tests have been done with release compilation mode.