Saturday, May 17, 2008

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


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
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.