8

I've recently been testing the performance of the for loop vs the foreach loop in C#, and I've noticed that for summing an array of ints into a long, the foreach loop may come out actually faster. Here is the full test program, I've used Visual Studio 2012, x86, release mode, optimizations on.

Here is the assembly code for both loops. The foreach:

            long sum = 0;
00000000  push        ebp 
00000001  mov         ebp,esp 
00000003  push        edi 
00000004  push        esi 
00000005  push        ebx 
00000006  xor         ebx,ebx 
00000008  xor         edi,edi 
            foreach (var i in collection) {
0000000a  xor         esi,esi 
0000000c  cmp         dword ptr [ecx+4],0 
00000010  jle         00000025 
00000012  mov         eax,dword ptr [ecx+esi*4+8] 
                sum += i;
00000016  mov         edx,eax 
00000018  sar         edx,1Fh 
0000001b  add         ebx,eax 
0000001d  adc         edi,edx 
0000001f  inc         esi 
            foreach (var i in collection) {
00000020  cmp         dword ptr [ecx+4],esi 
00000023  jg          00000012 
            }
            return sum;
00000025  mov         eax,ebx 
00000027  mov         edx,edi 
00000029  pop         ebx 
0000002a  pop         esi 
0000002b  pop         edi 
0000002c  pop         ebp 
0000002d  ret 

And the for:

    long sum = 0;
00000000  push        ebp 
00000001  mov         ebp,esp 
00000003  push        edi 
00000004  push        esi 
00000005  push        ebx 
00000006  push        eax 
00000007  xor         ebx,ebx 
00000009  xor         edi,edi 
            for (int i = 0; i < collection.Length; ++i) {
0000000b  xor         esi,esi 
0000000d  mov         eax,dword ptr [ecx+4] 
00000010  mov         dword ptr [ebp-10h],eax 
00000013  test        eax,eax 
00000015  jle         0000002A 
                sum += collection[i];
00000017  mov         eax,dword ptr [ecx+esi*4+8] 
0000001b  cdq 
0000001c  add         eax,ebx 
0000001e  adc         edx,edi 
00000020  mov         ebx,eax 
00000022  mov         edi,edx 
            for (int i = 0; i < collection.Length; ++i) {
00000024  inc         esi 
00000025  cmp         dword ptr [ebp-10h],esi 
00000028  jg          00000017 
            }
            return sum;
0000002a  mov         eax,ebx 
0000002c  mov         edx,edi 
0000002e  pop         ecx 
0000002f  pop         ebx 
00000030  pop         esi 
00000031  pop         edi 
00000032  pop         ebp 
00000033  ret

As you can see, the main loop is 7 instructions for "foreach" and 9 instructions for "for". This translates into approximately a 10% performance difference in my benchmarks.

I'm not very good at reading assembly code however and I don't understand why the for loop wouldn't be at least as efficient as the foreach. What is going on here?

8
  • 1
    I don't read assembly either, but I'd guess that it's the extra overhead of maintaining the i variable.
    – Bobson
    Jan 10, 2013 at 16:29
  • How did you run the program? Were JIT optimizations disabled? (By default running in the debugger disables JIT optimisations) Jan 10, 2013 at 16:31
  • I believe the compiler translates foreach into a while loop, which is quite similar ASM than a for loop (but not identical, there's some extra variables).
    – Bridge
    Jan 10, 2013 at 16:32
  • Yes JIT optimizations were enabled, I made sure of that in the debugger options.
    – Asik
    Jan 10, 2013 at 16:32
  • you should include the 0000001f inc esi in the foreach loop in the foreach example, it's incrementing the index Jan 10, 2013 at 16:33

3 Answers 3

8

As the array is so big the only relevand part is clearly the one inside the loop, this one:

// for loop
00000017  mov         eax,dword ptr [ecx+esi*4+8] 
0000001b  cdq 
0000001c  add         eax,ebx 
0000001e  adc         edx,edi 
00000020  mov         ebx,eax 
00000022  mov         edi,edx 

// foreach loop
00000012  mov         eax,dword ptr [ecx+esi*4+8] 
00000016  mov         edx,eax 
00000018  sar         edx,1Fh 
0000001b  add         ebx,eax 
0000001d  adc         edi,edx 

Since the sum is a long int it is stored in two differenc registers, namely ebx contains its least significant four bytes and edi the most significant four ones. They differ in how collection[i] is (implicitly) casted from int to long:

// for loop
0000001b  cdq 

// foreach loop
00000016  mov         edx,eax 
00000018  sar         edx,1Fh 

Another important thing to notice is that the for-loop version does the sum in "reversed" order:

long temp = (long) collection[i];   // implicit cast, stored in edx:eax
temp += sum;                        // instead of "simply" sum += temp
sum = temp;                         // sum is stored back into ebx:edi

I can't tell ou why the compiler preferred this way instead of sum += temp (@EricLippert could maybe tell us :) ) but I suspect that it is related to some instruction dependency issues that might arise.

2
  • i'm not certain but it might use a temp variable because += itself is not thread safe. Or it could be because the performance hit of this step is so minor that it was much easier to write the compiler to do this code instead of trying to refactor it correctly.
    – Seph
    Jan 11, 2013 at 1:28
  • @Seph threads shouldn't be an issue here as this example is single-threaded (although you're correct in saying that it isn't thread safe as it isn't an atomic operation) but effectively it might be possible that the speed gain isn't worth the added complexity ;)
    – BlackBear
    Jan 11, 2013 at 18:16
6

OK, so here's an annotated version of the assembly code, as you will see the instruction in the loop are very close.

            foreach (var i in collection) {
0000000a  xor         esi,esi                       clear index
0000000c  cmp         dword ptr [ecx+4],0           get size of collection
00000010  jle         00000025                      exit if empty
00000012  mov         eax,dword ptr [ecx+esi*4+8]   get item from collection
                sum += i;
00000016  mov         edx,eax                       move to edx:eax
00000018  sar         edx,1Fh                       shift 31 bits to keep sign only
0000001b  add         ebx,eax                       add to sum
0000001d  adc         edi,edx                       add with carry from previous add
0000001f  inc         esi                           increment index
            foreach (var i in collection) {
00000020  cmp         dword ptr [ecx+4],esi         compare size to index
00000023  jg          00000012                      loop if more
            }
            return sum;
00000025  mov         eax,ebx                       result was in ebx
=================================================
            for (int i = 0; i < collection.Length; ++i) {
0000000b  xor         esi,esi                       clear index
0000000d  mov         eax,dword ptr [ecx+4]         get limit on for
00000010  mov         dword ptr [ebp-10h],eax       save limit
00000013  test        eax,eax                       test if limit is empty
00000015  jle         0000002A                      exit loop if empty
                sum += collection[i];
00000017  mov         eax,dword ptr [ecx+esi*4+8]   get item form collection  
0000001b  cdq                                       convert eax to edx:eax
0000001c  add         eax,ebx                       add to sum
0000001e  adc         edx,edi                       add with carry from previous add
00000020  mov         ebx,eax                       put result in edi:ebx
00000022  mov         edi,edx 
            for (int i = 0; i < collection.Length; ++i) {
00000024  inc         esi                           increment index
00000025  cmp         dword ptr [ebp-10h],esi       compare to limit
00000028  jg          00000017                      loop if more
            }
            return sum;
0000002a  mov         eax,ebx                       result was in ebx
6
  • Thanks. It looks like both loops use basically the same indexing logic, it's mainly the two extra mov instructions in the for loop (lines 20 and 22) that are mysterious to me.
    – Asik
    Jan 10, 2013 at 16:55
  • I'll take a look at those later, it's lunch time here. That cdq and the 31 bit sar are also a bit odd. Probably they are both doing the same thing. Jan 10, 2013 at 17:07
  • 1
    This instructions are for sign extending EAX to EDX:EAX - once using Convert Double to Quad, once by completely shifting the value out of the register to the right keeping only the sign bit. Jan 10, 2013 at 17:17
  • That's what I figured, it's just odd that the convert to quad was used in one and the shift right in the other. Jan 10, 2013 at 17:24
  • The extra moves are to get the result back where it is needed, I've updated the comments on the assembly code Jan 10, 2013 at 17:42
-1

According to the C# Language Specification 4.0, a foreach loop gets broken down to the following by the compiler:

foreach-statement:

foreach ( local-variable-type identifier in expression ) embedded-statement

{
    E e = ((C)(x)).GetEnumerator();
    try {
        V v;
        while (e.MoveNext()) {
            v = (V)(T)e.Current;
            embedded-statement
        }
    }
    finally {
        … // Dispose e
    }
}

This is after the following processing (again from the specs):

If the type X of expression is an array type then there is an implicit reference conversion from X to the System.Collections.IEnumerable interface (since System.Array implements this interface). The collection type is the System.Collections.IEnumerable interface, the enumerator type is the System.Collections.IEnumerator interface and the element type is the element type of the array type X.

Likely a good reason why you aren't seeing the same assembly code from the compiler.

5
  • 1
    The compiler needs to generate something equivalent to, but not identical to this. AFAIK it special-cases arrays. Jan 10, 2013 at 16:32
  • However, the compiler has special optimizations for arrays, so it doesn't actually look anything like that.
    – SLaks
    Jan 10, 2013 at 16:32
  • The spec says the compiler will transform the foreach loop into code that is equivalent to what you've shown. In fact, when you iterate an array with foreach, it is translated to a straightforward index-based loop (which is of course way faster) but still the same semantically. That can be seen in the generated assembly: there are no function calls, and in fact the code is shorter than the for loop.
    – dlev
    Jan 10, 2013 at 16:35
  • @SLaks I added in the processing step that the specs say happens in a foreach loop for arrays at compile-time. Can you link to where the special optimizations are?
    – NominSim
    Jan 10, 2013 at 16:43
  • @dlev I'm looking at the spec right now and it doesn't say that under the foreach statement section. Can you point me to where it does?
    – NominSim
    Jan 10, 2013 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.