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 NDepend has 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:
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.