Enumeration isn’t cheap
So code optimization is sometimes like the unholy alliance of art and commerce… a case in point being the choice of Enumerators vs raw indexers for collections (for those of us unlucky enough to still be working in CLR1.1 anyway). Enumeration constructs are vastly more elegant and well encapsulated than raw indexing. However, that elegance comes at a non-trivial cost. If you have code that is doing a lot of enumeration at a low level, your profiler may well be advising you to look at using an indexer.
The sample code below produces the following results on my machine:
Enumerator: 2875.0184 Indexing: 234.3765
In other words the cost is over 10x more for the Enumerator.
private void button1_Click(object sender, System.EventArgs e)
{
ArrayList list = new ArrayList();
for (int i = 0; i < 10000000; i++)
{
list.Add(new object());
}
DateTime t1 = DateTime.Now;
foreach (object o in list)
{
int x = o.GetHashCode();
}
DateTime t2 = DateTime.Now;
DateTime t3 = DateTime.Now;
int length = list.Count;
for (int i = 0; i < length; i++)
{
int x = list[i].GetHashCode();
}
DateTime t4 = DateTime.Now;
double dt1 = ((TimeSpan)t2.Subtract(t1)).TotalMilliseconds;
double dt2 = ((TimeSpan)t4.Subtract(t3)).TotalMilliseconds;
MessageBox.Show(string.Format(“Enumerator: {0} Indexing: {1}”, dt1, dt2));
}
April 10th, 2006 at 2:34 pm
I would check this again, with the order of your tests reversed. I believe that Object.GetHashCode() is more expensive the first time it is called.
Certainly, in comparing enumerators with indexing, you will find differences, but the magnitude of the differences you are finding seems out of whack.
April 10th, 2006 at 2:40 pm
Good point. Reversing them the ratio falls to about 7x worse for the enumerator.
April 10th, 2006 at 3:33 pm
When doing these kinds of things, I also try to ensure that the code I am testing in the inner loop actually _does_ something, otherwise it can be optimised away.
x = 0;
int t0 = Environment.TickCount;
for (int i = 0; i
April 10th, 2006 at 3:35 pm
Umm, I was trying to show that you should accumulate all of the hashcodes your grab, i.e. x += o.GetHashCode()
April 10th, 2006 at 4:17 pm
Yes. I’m certainly not advancing this is as the canonical testing suite… Another thing it doesn’t demonstrate is that the cost doesn’t just exist for large collections. Iterations over small collections that are called frequently can actually be worse, since you incurr the cost of creating the Enumerator, and then later GC’ing it.
April 29th, 2006 at 6:34 pm
Did either of you try this with CLR 2.0? I did, and the Enumerator version varied between 1.5-2x worse than the index based version. Nothing as bad as 5-10x worse though. Looks like Microsoft has been working on this.
April 30th, 2006 at 1:21 pm
There are some interesting imporvements in 2.0, made possible through the introduction of generic types. Specifcally, the boxing/unboxing costs associated with value types in a collection, or even just the cost of the downcast from Object, can now be avoided. There is quite a nice article on it here: http://msdn.microsoft.com/msdnmag/issues/04/05/C20/
May 10th, 2006 at 3:22 pm
Another thing worth noting here is that in more typical usage of an ArrayList’s indexer, a cast is required. When the above sample is modified in the following fashion, results converge significantly to:
Enumerator: 328.1376 Indexing: 125.0048
private void button1_Click(object sender, System.EventArgs e)
{
ArrayList list = new ArrayList();
for (int i = 0; i
May 10th, 2006 at 3:24 pm
Hmm…looks like my sample was clipped. I was trying to emphasize the following amendment to the for (int i…loop:
int length = list.Count;
for (int i = 0; i
May 10th, 2006 at 3:26 pm
for (int i…
{
int x = ((SomeClass)list[i]).Val;
}