Search

Saturday, May 17, 2008

You need to be careful about how you use count in for-loops

Negotiating

Lets consider the following code

 MyCollection myCol = new MyCollection();
myCol.AddRange(new int[] { 1, 2, 3, 4, 5, });
for (int i = 0; i < myCol.Count; ++i)
{
Console.WriteLine("{0}", i);
}


 


What most people forgets to consider is the condition check that happens for the for loop (in Red). In this case it is actually a call to a method get_Count. The compiler doesn't optimize this away (even when inlined)!! Since the condition is evaluated after each iteration, there's actually a method call happening each time. For most .NET code it is low-cost because ultimately it's just a small method with count being returned from an instance variable (if inlined the method call overhead also goes away). Something like this is typically written for count.

public int Count
{
get
{
return this.count;
}
}

Someone wrote something very similar in C, where in the for-loop he used strlen. Which means that the following code actually is O(n2) because each time you are re-calculating the length...

for(int i = 0; i < strlen(str); ++i) {...}

Why the compiler cannot optimize it is another question. For one it's a method call and it is difficult to predict whether there's going to be any side-effect. So optimizing the call away can have other disastrous effect.


So store the count and re-use it if you know that the count is not going to change...

1 comment:

Anonymous said...

Consider the code you posted won't compile:

myCol.AddRange(new int[] { 1, 2, 3, 4, 5, });

The comma after the five will give you a compile error.