Performance and Insight: For versus Foreach over a strongly typed array... Some things you might not know.
To give some background there was a post on one of the MS newsgroups about why a nested foreach statement looping over two arrays was slower than the equivalent code in a for loop. While everyone liked to point out, rather too quickly I might add, that an enumerator was happening in the back-end, nobody really bothered looking at the IL to make sure. At some point the user replied that there was no enumerator, and since no enumerator, why the performance difference. Well, I figured I'd answer the question as best I knew how. Here is what I came up with along with some additional insight.
What is in a for:
The most important thing to note is what exactly goes into a for loop. Generally, you have some control variable that you are incrementing each iteration, to process something like an array or other collection. You can get more complex. But that is the basics. So I took this and decided I'd iterate over an integer array containing 10 elements and add those to a target value. Here is the code:
private void Foo() {
int[] foo = new int[10];
int bar = 0;
for(int i = 0; i < foo.Length; i++) {
bar += foo[i];
}
}
The IL generated by this particular method is pretty short. However, the locals are what is important. This method has 3 locals, 2 integers, and 1 integer array. This is as you would expect and is clearly visible in the code. Your two integers are bar and i, while your integer array is foo. Easy enough right? Well, there might be a bit more to it than that. At some point in time I heard there was an optimization when looping over arrays that some bounds checking code might be removed by the JIT if you used the length of the array (foo.Length) in the for loop, versus pre-caching this value (int length = foo.Length, in the locals). Just to check I've compiled out the following two pieces of code. The results are that pre-caching runs about 5.5 seconds over 100 million iterations, and .Length runs about 4.9 seconds. That is a pretty decent perf increase. Note there are cases where the .Length version actually takes 5.8 seconds. These appear to be anomalies on my machine, but they do happen. I've never seen such an anomaly come out of the pre-cached version.
private static void ForLoopOverArrayNoLength(int iterations) {
int[] foo = new int[10];
int bar = 0;
int length = foo.Length;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
for(int i = 0; i < length; i++) {
bar += foo[i];
}
}
end = DateTime.Now;
Console.WriteLine("ForLoopOverArrayNoLength: {0}", end - start);
}
private static void ForLoopOverArray(int iterations) {
int[] foo = new int[10];
int bar = 0;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
for(int i = 0; i < foo.Length; i++) {
bar += foo[i];
}
}
end = DateTime.Now;
Console.WriteLine("ForLoopOverArray: {0}", end - start);
}
Looks like my information was at least partially right. There does appear to be a decent enhancement by using the .Length method of an array within the context of the for loop? But what else can you do with a for loop that might not be cool... Well, you can change the variable pointed to by foo to a new array at any time. Haha, this is sneaky and very important so remember this. Want to see this in action, without it actually hurting anything, just run the following code:
private void ForLoopOverArrayWithArrayMod() {
int[] foo = new int[10];
int bar = 0;
for(int i = 0; i < foo.Length; i++) {
bar += foo[i];
foo = new int[10];
}
}
The foreach statement, better than you might think:
The foreach statement is really for collections, but it is so simple and easy to use that you often find it used for array access as well. There are times where it is probably faster or better to use than a for loop, perhaps if you are using the array element multiple times and indexing each time without caching it in a local. That is always a riot, but I see it more often than not. You might think that the foreach would be using the enumerator (yet another variable to GC right?), but it really isn't, and I think this is where it's power comes from. So what does a foreach over an array look like and what does it do:
private void Foo2() {
int[] foo = new int[10];
int bar = 0;
foreach(int i in foo) {
bar += i;
}
}
Above is the foreach loop equivalent to the very first code sample. The first code sample had 3 locals, while this one contains 5 locals. The two new locals are kind of hidden, since they aren't apparent in the code. You get 1 extra integer local and 1 extra integer array local. The integer array local is used to store a reference to the array used (foo) when you started the foreach statement. Excellent, that means I can change foo now, without worrying that the enumerator is going to be operating over the newly allocated array. You can do the same thing with a for loop, but you'd have to create a new array, assign it foo, and then forget the variable exists. Since you can't forget the variable exists you can never ensure, without code inspection, that someone in the loop body doesn't change the array out on you.
The second new integer in this case is really i, but i has now changed meanings. In the for loop we actually had to keep the array index as we moved over the array. The foreach loop creates a hidden variable and stores this value for us. So now i is the element in the array, not the index into the array. That accounts for all of the extra variables. Just turns out foreach is protecting us. Very cool if you ask me.
So how about the performance? Got some really strange numbers here, but I'll post them anyway, since I think the JIT is doing some really cool prediction to optimize the foreach loop. Here is the code I'm running just to test the foreach. It runs the same number of iterations as the for code used previously.
private static void ForeachLoopOverArray(int iterations) {
int[] foo = new int[10];
int bar = 0;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
foreach(int i in foo) {
bar += i;
}
}
end = DateTime.Now;
Console.WriteLine("ForeachLoopOverArray: {0}", end - start);
}
Not much different. However, depending on how ForeachLoopOverArray is actually called, the timing results for the method change. If I call ForeachLoopOverArray multiple times within a loop, then the timing is about 6 seconds. Well that sucks. An entire second here really matters. By simply calling the method outside of a loop, then I get times around 4.9 seconds, similiar to what I was getting with the for statement. Definitely looks like the JIT is doing some optimizations based on how they expect the method to be called. If they expect the method to be called in a loop, then they don't appear to optimize it as heavily as if it were to only be called once. Once the tuning is done, it doesn't appear to be re-done. In other words, calling each test at the beginning to *pre-JIT* them using the tuning, and then calling them in a loop later, seems to keep the performance. The final test program is added at the bottom of the entry. Note that timeMax is parsed from the command line. If you want to see the heuristics of the application change, then turn the int.Parse statement and make it a literal value of 10 instead. Just this change is enough to revert the methods back to the unoptimized versions. I'd love to hear different people's results. If you have timings that tend to trump what I've said, then publish em and let's take a gander.
using System;
public class QuickFor {
private static void Main(string[] args) {
int timeMax = 10; //int.Parse(args[0]);
ForeachLoopOverArray(100000000);
ForLoopOverArrayNoLength(100000000);
ForLoopOverArray(100000000);
for(int times = 0; times < timeMax; times++) {
ForeachLoopOverArray(100000000);
}
for(int times = 0; times < timeMax; times++) {
ForLoopOverArrayNoLength(100000000);
}
for(int times = 0; times < timeMax; times++) {
ForLoopOverArray(100000000);
}
}
private static void ForLoopOverArrayNoLength(int iterations) {
int[] foo = new int[10];
int bar = 0;
int length = foo.Length;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
for(int i = 0; i < length; i++) {
bar += foo[i];
}
}
end = DateTime.Now;
Console.WriteLine("ForLoopOverArrayNoLength: {0}", end - start);
}
private static void ForLoopOverArray(int iterations) {
int[] foo = new int[10];
int bar = 0;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
for(int i = 0; i < foo.Length; i++) {
bar += foo[i];
}
}
end = DateTime.Now;
Console.WriteLine("ForLoopOverArray: {0}", end - start);
}
private static void ForeachLoopOverArray(int iterations) {
int[] foo = new int[10];
int bar = 0;
DateTime start, end;
start = DateTime.Now;
for(int iteration = 0; iteration < iterations; iteration++) {
foreach(int i in foo) {
bar += i;
}
}
end = DateTime.Now;
Console.WriteLine("ForeachLoopOverArray: {0}", end - start);
}
}