For vs Foreach on arrays and lists

January 29, 2009 jonskeet 27 Comments

As promised earlier in the week, here are the results of benchmarking for and foreach.

For each of int and double, I created an array and a List<T>, filled it with random data (the same for the list as the array) and ran each of the following ways of summing the collection:

A simple for loop, testing the index against the array length / list count each time
A for loop with an initial variable remembering the length of the array, then comparing the index against the variable each time
A foreach loop against the collection with the type known at compile and JIT time
A foreach loop against the collection as IEnumerable<T>
Enumerable.Sum

I won’t show the complete code in this post, but it’s you can download it and then build it against the benchmarking framework. Here’s a taste of what it looks like – the code for a list instead of an array, and double instead of int is pretty similar:

List<int> intList = Enumerable.Range(0, Size)
.Select(x => rng.Next(100))
.ToList();
int[] intArray = intList.ToArray();

…

static int IEnumerableForEach(IEnumerable<int> input)
{
    int sum = 0;
    foreach (int d in input)
    {
        sum += d;
    }
    return sum;
}

(I don’t normally format code quite like that, and wouldn’t even use a lambda for that sort of code – but it shows everything quite compactly for the sake of blogging.)

Before I present the results, a little explanation:

I considered int and double entirely separately – so I’m not comparing the int[] results against the double[] results for example.
I considered array and list results together – so I am comparing iterating over an int[] with iterating over a List<int>.
The result for each test is a normalized score, where 1.0 means “the best of the int summers” or “the best of the double summers” and other scores for that type of summation show how much slower that test ran (i.e. a score of 2.0 would mean it was twice as slow – it got through half as many iterations).
I’m not currently writing out the number of iterations each one completes – that might be interesting to see how much faster it is to sum ints than doubles.

Happy with that? Here are the results…

——————– Doubles ——————–
============ double[] ============
For                 1.00
ForHoistLength      1.00
ForEach             1.00
IEnumerableForEach 11.47
Enumerable.Sum     11.57

============ List<double> ============
For                 1.99
ForHoistLength      1.44
ForEach             3.19
IEnumerableForEach 18.78
Enumerable.Sum     18.61

——————– Ints ——————–
============ int[] ============
For                 1.00
ForHoistLength      2.03
ForEach             1.36
IEnumerableForEach 15.22
Enumerable.Sum     15.73

============ List<int> ============
For                 2.82
ForHoistLength      3.49
ForEach             4.78
IEnumerableForEach 25.71
Enumerable.Sum     26.03

I found the results interesting to say the least. Observations:

When summing a double[] any of the obvious ways are good.
When summing an int[] there’s a slight benefit to using a for loop, but don’t try to optimise it yourself – I believe the JIT recognizes the for loop pattern and removes array bounds checking, but not when the length is hoisted. Note the lack of difference when summing doubles – I suspect that this is because the iteration part is more significant when summing ints because integer addition is blindingly fast. This is important – adding integers is about as little work as you’re liikely to do in a loop; if you’re doing any real work (even as trivial as adding two doubles together) the difference between for and foreach is negligible
Our IEnumerableForEach method has pretty much the same performance as Enumerable.Sum – which isn’t really surprising, as it’s basically the same code. (At some point I might include Marc Gravell’s generic operators to see how they do.)
Using a general IEnumerable<T> instead of the specific List<T> makes a pretty huge difference to the performance – I assume this is because the JIT inlines the List<T> code, and it doesn’t need to create an object because List<T>.Enumerator is a value type. (The enumerator will get boxed in the general version, I believe.)
When using a for loop over a list, hosting the length in the for loop helped in the double version, but hindered in the int version. I’ve no idea why this happens.

If anyone fancies running this on their own box and letting me know if they get very different results, that would be really interesting. Likewise let me know if you want me to add any more tests into the mix.

27 thoughts on “For vs Foreach on arrays and lists”

Jarrod Dixon says:

January 29, 2009 at 11:04 pm

I usually pick between a ‘for’ or a ‘foreach’ loop, depending on if the inner loop’s logic will require an incrementing (or decrementing) integer.

Very interesting about the ‘for’ loop’s bounds and hoisting – I’d have wagered that there would have been a slight advantage towards hoisting. Very glad I’ll NOT have to refactor any code :)

Excellent post and I’m going to try out your benchmarking framework; the example code is very concise!

LikeLike

Reply
Chris Nahr says:

January 30, 2009 at 3:27 am

Quite an interesting test suite. The results are generally what I’d expect, though I have no idea why hoisting the length would sometimes help and sometimes hinder with List. For now I’m inclined to call these effects random variations and blame them on hardware and software setup, cosmic rays, the awakening of Cthulhu, etc.

The performance of Enumerable.Sum is really rather tragic, of course. Although I like the idea of LINQ, I’ve decided not to use LINQ to Objects at all because of such performance issues. Irrelevant when you’re streaming in data from XML files or databases, but crippling when you’re frequently operating on some short List.

LikeLike

Reply
Vincent Croquette says:

January 30, 2009 at 6:10 am

Hi Jon

It seems like it have better results than yours concerning the enumerables tests…

Or am I missing something?

——————– Doubles ——————–
============ double[] ============
For 1.21
ForHoistLength 1.00
ForEach 1.00
IEnumerableForEach 2.20
Enumerable.Sum 1.64

============ List ============
For 2.66
ForHoistLength 2.00
ForEach 2.00
IEnumerableForEach 2.83
Enumerable.Sum 2.72

——————– Ints ——————–
============ int[] ============
For 1.12
ForHoistLength 1.00
ForEach 1.28
IEnumerableForEach 2.74
Enumerable.Sum 2.09

============ List ============
For 2.60
ForHoistLength 1.97
ForEach 2.12
IEnumerableForEach 3.67
Enumerable.Sum 3.40

LikeLike

Reply
skeet says:

January 30, 2009 at 7:22 am

Vincent: That’s really interesting. What’s your machine? I assume you were running an optimised build, not under debug? I think I need to include the raw numbers as well, so we can check actual figures…

LikeLike

Reply
JG says:

January 30, 2009 at 8:40 am

============ double[] ============
For 1.00
ForHoistLength 1.00
ForEach 2.00
IEnumerableForEach 7.77
Enumerable.Sum 7.68

============ List ============
For 2.67
ForHoistLength 2.01
ForEach 4.35
IEnumerableForEach 13.99
Enumerable.Sum 13.83

============ int[] ============
For 1.00
ForHoistLength 1.00
ForEach 1.00
IEnumerableForEach 10.57
Enumerable.Sum 8.75

============ List ============
For 2.73
ForHoistLength 1.64
ForEach 4.86
IEnumerableForEach 17.91
Enumerable.Sum 14.59

LikeLike

Reply
Alexey Romanov says:

January 30, 2009 at 8:45 am

What about a more generic version of IEnumerableForEach?

static int IEnumerableForEach(TEnumerable input) where TEnumerable : IEnumerable
{
int sum = 0;
foreach (int d in input)
{
sum += d;
}
return sum;
}

LikeLike

Reply
Chris Barrett says:

January 30, 2009 at 9:27 am

I showed similar results to Vincent… that is until I remembered to change to Release mode! Clearly the optimisation around for loops is much better than anything MS have put in for Enumerable.Sum().

Full release mode results for your benchmark test (run on a 1.6GHz laptop) below… certainly still a fair variation on Jon’s original results – mine are without SP1 installed, which could be a factor.

——————– Doubles ——
============ double[] ============
For 1.01
ForHoistLength 1.22
ForEach 1.00
IEnumerableForEach 12.53
Enumerable.Sum 8.03

============ List =========
For 2.38
ForHoistLength 2.43
ForEach 8.28
IEnumerableForEach 18.90
Enumerable.Sum 14.59

——————– Ints ———
============ int[] ============
For 1.09
ForHoistLength 1.48
ForEach 1.00
IEnumerableForEach 11.20
Enumerable.Sum 11.39

============ List ============
For 2.38
ForHoistLength 1.99
ForEach 8.09
IEnumerableForEach 20.35
Enumerable.Sum 20.50

LikeLike

Reply
skeet says:

January 30, 2009 at 9:35 am

@Alexey: That wouldn’t work with a double array though, I don’t think… and it certainly wouldn’t do double additions, like the other tests. Marc’s operator work would sort it though :)

LikeLike

Reply
Vincent Croquette says:

January 30, 2009 at 9:37 am

My machine’s details:
Inter core 2 duo
2.33GHz 3G ram
XP professional

VS 2008 SP1
.net framework 3.5 SP1

and most strangely no, it’s compiled in debug mode

I re ran the tests and got almost exactly the same results (worse results!!!)

If I run them in release mode, I get the following results:

——————– Doubles —————
============ double[] ============
For 1.11
ForHoistLength 1.00
ForEach 1.29
IEnumerableForEach 3.74
Enumerable.Sum 3.42

============ List ============
For 3.41
ForHoistLength 2.91
ForEach 3.96
IEnumerableForEach 5.05
Enumerable.Sum 5.64

——————– Ints ——————
============ int[] ============
For 1.05
ForHoistLength 1.00
ForEach 1.29
IEnumerableForEach 2.96
Enumerable.Sum 2.43

============ List ============
For 2.78
ForHoistLength 2.09
ForEach 2.30
IEnumerableForEach 4.14
Enumerable.Sum 3.96

LikeLike

Reply
Alexey Romanov says:

January 30, 2009 at 9:42 am

Of course this is int only, but of course the version for double is similar (just as IEnumerableForEach in your post is for ints only). I am hoping that it might inline the calls made in this way, since versions for both arrays and Lists will be generated, which _could_ present an opportunity for inlining.

LikeLike

Reply
skeet says:

January 30, 2009 at 9:55 am

@Alexey: Ah, I see what you mean. I doubt that it will happen, as they’ll be reference types which means sharing JITted code. However, it’s worth a try.

As people are actually bothering to run the test (which surprises me a bit!) I’ll look into creating the “single .cs file” version of the framework tonight, too.

LikeLike

Reply
Steve Owens says:

January 30, 2009 at 11:35 am

I built the framework and a program, and found a HUGE discrepancy in the *Enumerable numbers between running in a CMD window and the Visual Studio debugger.

My numbers from within Visual Studio are comparable to Vincent’s, my numbers when building an .exe and running in a CMD window are comparable to the ones in the original post.

Here are the results from VS for just List:
Visual Studio (f5) Command Prompt
======= List ======= ======= List =======
For 2.58 For 3.04
ForHoistLength 1.95 ForHoistLength 3.65
ForEach 2.09 ForEach 4.95
IEnumerableForEach 3.63 IEnumerableForEach 27.24
Enumerable.Sum 3.43 Enumerable.Sum 27.43

Why would there be such a difference in the last two?? What magic is VS doing in the background?

LikeLike

Reply
skeet says:

January 30, 2009 at 12:17 pm

@Steve: When you ran it in Visual Studio, did you hit F5 or Ctrl-F5? If you just hit F5 then it’ll be running under the debugger, even if you built the release version. That makes an enormous difference. I’m just going to run it from the command line myself to see if that changes anything…

LikeLike

Reply
skeet says:

January 30, 2009 at 12:41 pm

@Steve: I’ve just tried running it from the command line, and that gave the same results as I posted, which were from Visual Studio (with Ctrl+F5).

LikeLike

Reply
Steve Owens says:

January 30, 2009 at 1:14 pm

@Jon Color me puzzled, but if I run via the VS debugger, why are my *Enumerables so much faster than the command line?

LikeLike

Reply
skeet says:

January 30, 2009 at 2:02 pm

@Steve: It’s not that they’re faster, it’s that they’re *relatively* faster. If you change the code to show the actual duration/iterations, you’ll see that it takes a lot longer under the debugger – but that the heavily optimised loops lose out more, relatively speaking.

LikeLike

Reply
Vincent Croquette says:

January 30, 2009 at 2:03 pm

I ran all my tests under VS (F5) so always in debug mode according to what you say

I’ve already noticed a couple of differences when running from VS rather than executing an application from outside VS (the name of the AppDomain is different for instance) but shouldn’t the performance be better outside VS?

LikeLike

Reply
Vincent Croquette says:

January 30, 2009 at 2:14 pm

Ah OK now I get it
I had forgotten the results were relative to the best result

Thanks for making this clearer

LikeLike

Reply
Sam says:

January 31, 2009 at 5:58 pm

Have you tried looping in the reverse order? On X68 it is faster to compare against zero than any other number.

for(int i=max-1;i>=0;i–)
{
}

etc. Of it it changes the meaning, which is sometimes not useful anyways. This is very interesting, bookmarked. I downloaded the code as well.

LikeLike

Reply
skeet says:

February 1, 2009 at 1:54 am

@Sam: No, haven’t tried that. Even more permutations to try…

LikeLike

Reply
Neil Whitaker says:

December 10, 2014 at 7:13 pm

Thank you for publishing this. I just ran across it and thought I would see if anything has changed in 5 years.

I cut the total run time way down, so my results are rough, but building in Visual Studio 2013 Release mode and running from the command line revealed these trends:
* All non-base cases are now 20-50% faster than in the results you published above.
* Hoisting or not hoisting seems to make no difference.

LikeLike

Reply
1. Neil Whitaker says:
  
  December 10, 2014 at 7:18 pm
  
  I just noticed one odd case: List.ForEach measured in at 7.13–much longer than your 4.78.
  
  Here are the numbers:
  ============ double[] ============
  For 1.00
  ForHoistLength 1.00
  ForEach 1.00
  IEnumerableForEach 6.69
  Enumerable.Sum 7.08
  
  ============ List ============
  For 1.01
  ForHoistLength 1.01
  ForEach 3.63
  IEnumerableForEach 10.35
  Enumerable.Sum 10.33
  
  ——————– Ints ——————–
  ============ int[] ============
  For 1.00
  ForHoistLength 1.00
  ForEach 1.01
  IEnumerableForEach 12.15
  Enumerable.Sum 12.53
  
  ============ List ============
  For 1.96
  ForHoistLength 1.95
  ForEach 7.13
  IEnumerableForEach 19.02
  Enumerable.Sum 19.46
  
  LikeLike
  
  Reply
Pingback: .NET Multiple LINQs vs Single foreach | codePERF[dot]NET
Pingback: Why is iterating through List<T> more expensive than iterating through Array in .NET? | Question and Answer
firemystdl says:

May 20, 2016 at 6:12 am

While your comparisons are great, here’s a blog comparison that iterates over multiple kinds of objects, such as DataRows and custom objects, also including the performance of the While loop construct:
http://cc.davelozinski.com/c-sharp/for-vs-foreach-vs-while

At the minimum, it would be great to see your future articles incorporate the while loop too as a comparison, especially over arrays.

LikeLike

Reply
Pingback: Ciekawostki na różny temat | Wiadomości o technologiach IT
Pingback: Merge two dictionaries c# | 일상

Jon Skeet's coding blog

For vs Foreach on arrays and lists

27 thoughts on “For vs Foreach on arrays and lists”

Leave a comment Cancel reply

Share this:

Related

27 thoughts on “For vs Foreach on arrays and lists”

Leave a comment Cancel reply