For vs Foreach on arrays and lists

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))
int[] intArray = intList.ToArray();

var intArraySuite = TestSuite.Create(“int[]”, intArray, intArray.Sum())
    .Add(input => { int sum = 0;
        for (int i = 0; i < input.Length; i++) sum += input[i];
        return sum;
    }, “For”)
    .Add(input => { int sum = 0; int length = input.Length;
        for (int i = 0; i < length; i++) sum += input[i];
        return sum;
    }, “ForHoistLength”)
    .Add(input => { int sum = 0;
        foreach (int d in input) sum += d;
        return sum;
    }, “ForEach”)
    .Add(Enumerable.Sum, “Enumerable.Sum”)

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.

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

  1. 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!

  2. 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.

  3. 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

  4. 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…

  5. ============ 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

  6. 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;

  7. 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

  8. @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 :)

  9. 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

  10. 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.

  11. @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.

  12. 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?

  13. @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…

  14. @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).

  15. @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.

  16. 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?

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

    Thanks for making this clearer

  18. 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.

Comments are closed.