foreach vs. for

[cody]

Why is it that given

int C = 13000;
int[] n = new int[C];

foreach (int i in n)
foreach (int j in n)
{
tmp+=i;
tmp+=j;
}

is significantly slower than

for (int i=0; i<n.Length;i++)
for (int j=0; j<n.Length; j++)
{
tmp+=n;
tmp+=n[j];
}

?

 

[Jeremy Todd]

Why is it that given [foreach] is significantly slower than [for] ?

Foreach looks like a basic language construct, but what it's really
doing is taking advantage of the Array class's implementation of the
IEnumerable interface. So, rather than just incrementing a number, it's
doing something like the following:

int C = 13000;
int[] n = new int[C];

IEnumerator arrayEnumerator = n.GetEnumerator;

while (arrayEnumerator.MoveNext) {
tmp += (int) arrayEnumerator.Current;
[do whatever]
}

Since it has to create an IEnumerator for the array as well as call a
method and a property accessor for each iteration, that's going to increase
the overhead. It's a good idea to avoid foreach whenever you're dealing
with numeric indices.

Hope this helps!
Jeremy

 

[Matt Davey]

http://msdn.microsoft.com/library/d...en-us/csref/html/vclrfTheForeachStatement.asp

Its the Enumerator overhead

Later

 

[Guest]

the damn compiler should optimize these

 

[Guest]

How? They are not the same thing, after all

It is entirely possible to use custom logic to decide the order when implementing IEnumerator

The class being enumerated doesn't even need to have an indexer.

 

[cody]

Foreach looks like a basic language construct, but what it's really

doing is taking advantage of the Array class's implementation of the
IEnumerable interface. So, rather than just incrementing a number, it's
doing something like the following:

No. I checked the generated IL-code and there was no method call to
GetEnumerator() or MoveNext() or Current.
A simple foreach-loop over an int-array looks like this:

foreach (int i in a)
WriteLine("test");

generates:

IL_002d: ldloc.2
IL_002e: stloc.s 15
IL_0030: ldc.i4.0
IL_0031: stloc.s 16
IL_0033: br.s IL_004c
IL_0035: ldloc.s 15
IL_0037: ldloc.s 16
IL_0039: ldelem.i4
IL_003a: stloc.3
IL_003b: ldarg.0
IL_003c: ldstr "test"
IL_0041: call instance void Test.MainWindow::WriteLine(object)
IL_0046: ldloc.s 16
IL_0048: ldc.i4.1
IL_0049: add
IL_004a: stloc.s 16
IL_004c: ldloc.s 16
IL_004e: ldloc.s 15
IL_0050: ldlen
IL_0051: conv.i4
IL_0052: blt.s IL_0035

I do not understand much about IL-code but that looks pretty much for a
simple loop.
I can see 2 branches in that code and the array-element is popped on the
stack although
the array is never used within the loop. Additionally what does "conv.i4"
do? if it converts the long length to an int32
why do we need a 64 bit lenght if it is casted down to int32 used anyway???

 

[Jeremy Todd]

No. I checked the generated IL-code and there was no method call to
GetEnumerator() or MoveNext() or Current.

Interesting. I'm surprised the compiler doesn't consistently use the
Enumerator on a foreach; that seems like it could cause unexpected behavior
in some (rare) instances.

Well, check the MSIL for the "for" version and see how that comes out.
That should answer your performance question, hopefully.

Jeremy

 

[Guest]

Hi Charlie -
I was wrong on this, I take it back.

 

[Justin Rogers]

A for loop using the .Length property for the array will almost always
perform better, since behind the scenes the JIT removes some extra
bounds checking code that is normally in place. In the IL this won't be
apparent because you see a ldlen (or check the length of the array).

As for the differences in the two bits of code in terms of generated IL,
there will always be a difference because the enumeration version creates
some extra safety variables. Take the following code:

using System;

public class QuickFor {
private static void Main(string[] args) {
}

private void Foo() {
int[] foo = new int[10];
int bar = 0;
for(int i = 0; i < foo.Length; i++) {
bar += foo;
}
}

private void Foo2() {
int[] foo = new int[10];
int bar = 0;
foreach(int i in foo) {
bar += i;
}
}
}

Now, the first method Foo, creates three stack locals. Two integers and
one integer array. bar, i and foo map to these variables. The second method
Foo2 creatues five stack locals. 3 integers and two integer arrays. The two
hidden variables in Foo2 are that behind the scenese the original array foo, is
being assigned from V_0 to V_3 and V_3 is operated on while V_0 is kept
the same. This is so that you can change foo without stopping the enumerator.
They need this protection because they aren't using IEnumerable which has
worse performance than just iterating the array statically, and they aren't
going
to throw any exceptions. V_4, the other hidden variable is an integer that
stores
the offset within V_3.

Hope this helps guys.

 

[cody]

As for the differences in the two bits of code in terms of generated IL,

there will always be a difference because the enumeration version creates
some extra safety variables. Take the following code:

using System;

public class QuickFor {
private static void Main(string[] args) {
}

private void Foo() {
int[] foo = new int[10];
int bar = 0;
for(int i = 0; i < foo.Length; i++) {
bar += foo;
}
}

private void Foo2() {
int[] foo = new int[10];
int bar = 0;
foreach(int i in foo) {
bar += i;
}
}
}

Now, the first method Foo, creates three stack locals. Two integers and
one integer array. bar, i and foo map to these variables. The second method
Foo2 creatues five stack locals. 3 integers and two integer arrays. The two
hidden variables in Foo2 are that behind the scenese the original array foo, is
being assigned from V_0 to V_3 and V_3 is operated on while V_0 is kept
the same. This is so that you can change foo without stopping the enumerator.
They need this protection because they aren't using IEnumerable which has
worse performance than just iterating the array statically, and they aren't
going
to throw any exceptions.

Since the original variable is never modified, the copy could be savely
optimized away .

V_4, the other hidden variable is an integer that stores
the offset within V_3.

Hope this helps guys.

Which offset? the for loop also has to store the current offset in the
variable i.
I hope that they'll fix that in future. I expect that foreach () to have the
same performance as for()

 

[cody]

Also I wonder what the conv.i4 instruction is needed for. the lenght
property of array already returns an int so there is no need to convert
someting. I also noted that the conv instruction was apparent in the for()
version also.

decompilation of the loop returned following code:

for (int k5 = 0; k5 < (int)nums2.Length; k5++)
{
int k1 = nums2[k5];
WriteLine("test");
}

note the cast of the length property. also there is an unnessacary
assignment of k1.

 

[Justin Rogers]

You can read my full examination of these methods on my blog. for and
foreach under most circumstances have the same performance results, even
though they have different code. The semantics of foreach (storing a local
version of the array and a local copy of the array element) are required,
while you are allowed to manage these options yourself when using a for
loop.

http://weblogs.asp.net/justin_rogers/archive/2004/03/26/97230.aspx

 

[Bill McCarthy]

hi Justin,

Are those tests you did actually doing anything though ? They don't appear
to be either reading to or writing from the array. Obviously, if you are
comparing foreach with for, then due to the limitations of foreach, you
can't actually be writing to the array. So a realistic test would be reading
from the elements.

I think with foreach, you will notice various impacts as you need to cast
from each element, because the Enumerator definition is only as Object. For
value types, this impact will be more significant. (Generics of course
alleviate this)
The other thing to be aware of is whether the enumerator is a thread safe
enumerator or not. Thread safe enumerators tend to take a snapshot of the
data, and hence there is a bit of copying going on before the enumeration
starts.

You can read my full examination of these methods on my blog. for and
foreach under most circumstances have the same performance results, even
though they have different code. The semantics of foreach (storing a local
version of the array and a local copy of the array element) are required,
while you are allowed to manage these options yourself when using a for
loop.

http://weblogs.asp.net/justin_rogers/archive/2004/03/26/97230.aspx


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Also I wonder what the conv.i4 instruction is needed for. the lenght
property of array already returns an int so there is no need to convert
someting. I also noted that the conv instruction was apparent in the for()
version also.

decompilation of the loop returned following code:

for (int k5 = 0; k5 < (int)nums2.Length; k5++)
{
int k1 = nums2[k5];
WriteLine("test");
}

note the cast of the length property. also there is an unnessacary
assignment of k1.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

 

[Justin Rogers]

Are those tests you did actually doing anything though ? They don't appear

to be either reading to or writing from the array. Obviously, if you are
comparing foreach with for, then due to the limitations of foreach, you
can't actually be writing to the array. So a realistic test would be reading
from the elements.

All of the tests are using the array element to update a local variable. Hence
the bar+=foo, or in the case of foreach bar+=i;

I think with foreach, you will notice various impacts as you need to cast
from each element, because the Enumerator definition is only as Object. For
value types, this impact will be more significant. (Generics of course
alleviate this)

The point was that foreach doesn't even create an enumerator when iterating
an array. That is made quite obvious by my examination of the IL locals for
both the for instance, and the foreach instance.

The other thing to be aware of is whether the enumerator is a thread safe
enumerator or not. Thread safe enumerators tend to take a snapshot of the
data, and hence there is a bit of copying going on before the enumeration
starts.

Not to be harsh, but it looks like you probably didn't read the blog entry. I
note that there is no enumerator when using foreach. There are instead
optimizations made by the C# compiler. I talk about all of these optimizations
in the article, so I won't enumerate them again here. The main optimization,
however, is that foreach DOES NOT create an enumerator when iterating
over an array of integers.

 

[cody]

I talk about all of these optimizations

in the article, so I won't enumerate them again here.

no pun intended

foreach (Optimization opt in Article)
{
...
}

 

[Bill McCarthy]

Hi Justin,

Are those tests you did actually doing anything though ? They don't appear
to be either reading to or writing from the array. Obviously, if you are
comparing foreach with for, then due to the limitations of foreach, you
can't actually be writing to the array. So a realistic test would be reading
from the elements.

All of the tests are using the array element to update a local variable. Hence
the bar+=foo, or in the case of foreach bar+=i;

But it is still doing nothing. The local variable is not passed out of the
method, and because it is a local variable that is not used anywhere else
other than the assignment to it, an optimising JIT compiler can actually
decide to skip that code. When you do bench tests and report anomolties,
it's probalby best to avoid such code that can be optimised out, if it is
that code you are actually trying to test

The point was that foreach doesn't even create an enumerator when iterating
an array.

Right, for arrays only. For anything else that implements IList, this is
not the case. That's why I referred to thread safe enumerators, which you
probably know an array's enumerator is not.

That is made quite obvious by my examination of the IL locals for
both the for instance, and the foreach instance.

Uhm jsut a suggestion, it would have been made clearer if you actually
included the IL you were referring to

Not to be harsh, but it looks like you probably didn't read the blog entry. I
note that there is no enumerator when using foreach. There are instead
optimizations made by the C# compiler. I talk about all of these optimizations
in the article, so I won't enumerate them again here. The main optimization,
however, is that foreach DOES NOT create an enumerator when iterating
over an array of integers.

Not with you there. Seems we are perhaps talking past each other. Arrays do
not have thread safe enumeration.

 

[Justin Rogers]

Point take, I added comments to the entry and a *work-around* to root the value
bar so it can't be optimized away by the JIT, assuming the JIT would ever do
such
a thing.
Someone asserted that the JIT might optimize out the entire loop and make it
*not happen* because the resulting value isn't being used. I think this is a
highly unfounded assertion, but just in case, you'd think we might be able to
save the JIT the trouble of optimizing things out by appending the bar variable
onto the Console.WriteLine call. Once you do that, the variable bar becomes
*used* and so the JIT couldn't possibly optimize it out.

However, I know the JIT wasn't optimizing things out because I was viewing the
resulting assembler for each of the above methods and watching it run. I think
that asking the JIT to optimize all of the above code out would be a rather tall
order, but I'm assuming the metrics could be there for it. As a human compiler I
would optimize the code out since I would realize the value of bar was never
used and so the iteration was for naught.

I guess the days of using looping constructs to count time away are over. No
more: "Please insert an integer between 1 and 10000: " when you start running a
game under the GW BASIC interpreter. And I thought I was so slick when I wrote
my own custom timing function to get rid of that message for good, so no user
ever had to feel the wrath of submarines and torpedos at warp speed on their
ultra fast new 386.
<<< END Comment


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Hi Justin,

Are those tests you did actually doing anything though ? They don't appear
to be either reading to or writing from the array. Obviously, if you are
comparing foreach with for, then due to the limitations of foreach, you
can't actually be writing to the array. So a realistic test would be reading
from the elements.

All of the tests are using the array element to update a local variable. Hence
the bar+=foo, or in the case of foreach bar+=i;

But it is still doing nothing. The local variable is not passed out of the
method, and because it is a local variable that is not used anywhere else
other than the assignment to it, an optimising JIT compiler can actually
decide to skip that code. When you do bench tests and report anomolties,
it's probalby best to avoid such code that can be optimised out, if it is
that code you are actually trying to test

The point was that foreach doesn't even create an enumerator when iterating
an array.

Right, for arrays only. For anything else that implements IList, this is
not the case. That's why I referred to thread safe enumerators, which you
probably know an array's enumerator is not.

That is made quite obvious by my examination of the IL locals for
both the for instance, and the foreach instance.

Uhm jsut a suggestion, it would have been made clearer if you actually
included the IL you were referring to

Not to be harsh, but it looks like you probably didn't read the blog entry. I
note that there is no enumerator when using foreach. There are instead
optimizations made by the C# compiler. I talk about all of these optimizations
in the article, so I won't enumerate them again here. The main optimization,
however, is that foreach DOES NOT create an enumerator when iterating
over an array of integers.

Not with you there. Seems we are perhaps talking past each other. Arrays do
not have thread safe enumeration.