Does the c# compiler optimizes Count properties?

Question

List<int> list = ...

for(int i = 0; i < list.Count; ++i)
{
           ...
}

So does the compiler know the list.Count does not have to be called each iteration?

Answer 1

Are you sure about that?

List<int> list = new List<int> { 0 };

for (int i = 0; i < list.Count; ++i)
{
    if (i < 100)
    {
        list.Add(i + 1);
    }
}

If the compiler cached the Count property above, the contents of list would be 0 and 1. If it did not, the contents would be the integers from 0 to 100.

Now, that might seem like a contrived example to you; but what about this one?

List<int> list = new List<int>();

int i = 0;
while (list.Count <= 100)
{
    list.Add(i++);
}

It may seem as if these two code snippets are completely different, but that's only because of the way we tend to think about for loops versus while loops. In either case, the value of a variable is checked on every iteration. And in either case, that value very well could change.

Typically it's not safe to assume the compiler optimizes something when the behavior between "optimized" and "non-optimized" versions of the same code is actually different.

Answer 2

The C# compiler does not do any optimizations like this. The JIT compiler, however, optimizes this for arrays, I believe (which are not resizable), but not for lists.

A List's count property can change within the loop structure, so it would be an incorrect optimization.

Answer 3

No, it doesn't. Because condition is calculated on each step. It can be more complex than just comparsion with count, and any boolean expression is allowed:

 for(int i = 0; new Random().NextDouble() < .5d; i++)
     Console.WriteLine(i);

http://msdn.microsoft.com/en-us/library/aa664753(VS.71).aspx

Answer 4

It depends on the particular implementation of Count; I've never noticed any performance issues with using the Count property on a List so I assume it's ok.

In this case you can save yourself some typing with a foreach.

List<int> list = new List<int>(){0};
foreach (int item in list)
{ 
    // ...
} 

Answer 5

For all the other commenters who say that the 'Count' property could change in a loop body: JIT optimizations let you take advantage of the actual code that's running, not the worst-case of what might happen. In general, the Count could change. But it doesn't in all code.

So in the poster's example (which might not have any Count-changing), is it unreasonable for the JIT to detect that the code in the loop doesn't change whatever internal variable List uses to hold its length? If it detects that list.Count is constant, wouldn't it lift that variable access out of the loop body?

I don't know if the JIT does this or not. But I am not so quick to brush this problem off as trivially "never."

Answer 6

If you take a look at the IL generated for Dan Tao's example you'll see a line like this at the condition of the loop:

callvirt instance int32 [mscorlib]System.Collections.Generic.List`1<int32>::get_Count()

This is undeniable proof that Count (i.e. get_Count()) is called for every iteration of the loop.

Answer 7

It's worth noting, as nobody else has mentioned it, that there is no knowing from looking at a loop like this what the "Count" property will actually do, or what side effects it may have.

Consider the following cases:

• A third party implementation of a property called "Count" could execute any code it wished to. e.g. return a Random number for all we know. With List we can be a bit more confident about how it will operate, but how is the JIT to tell these implementations apart?

• Any method call within the loop could potentially alter the return value of Count (not just a straight "Add" directly on the collection, but a user method that is called in the loop might also party on the collection)

• Any other thread that happens to be executing concurrently could also change the Count value.

The JIT just can't "know" that Count is constant.

However, the JIT compiler can make the code run much more efficiently by inlining the implementation of the Count property (as long as it is a trivial implementation). In your example it may well be inlined down to a simple test of a variable value, avoiding the overhead of a function call on each iteration, and thus making the final code nice and fast. (Note: I don't know if the JIT will do this, just that it could. I don't really care - see the last sentence of my answer to find out why)

But even with inlining, the value may still be changed between iterations of the loop, so it would still need to be read from RAM for each comparison. If you were to copy Count into a local variable and the JIT could determine by looking at the code in the loop that the local variable will remain constant for the loop's lifetime, then it may be able to further optimise it (e.g. by holding the constant value in a register rather than having to read it from RAM on each iteration). So if you (as a programmer) know that Count will be constant for the lifetime of the loop, you may be able to help the JIT by caching Count in a local variable. This gives the JIT the best chance of optimising the loop. (But there are no guarantees that the JIT will actually apply this optimisation, so it may make no difference to the execution times to manually "optimise" this way. You also risk things going wrong if your assumption (that Count is constant) is incorrect. Or your code may break if another programmer edits the contents of the loop so that Count is no longer constant, and he doesn't spot your cleverness)

So the moral of the story is: The JIT can make a pretty good stab at optimising this case by inlining. Even if it doesn't do this now, it may do it with the next C# version. You might not gain any advantage by manually "optmising" the code, and you risk changing its behaviour and thus breaking it, or at least making future maintenance of your code more risky, or possibly losing out on future JIT enhancements. So the best approach is to just write it the way you have, and optimise it when your profiler tells you that the loop is your performance bottleneck.

Hence, IMHO it's interesting to consider/understand cases like this, but ultimately you don't actually need to know. A little bit of knowledge can be a dangerous thing. Just let the JIT do its thing, and then profile the result to see if it needs improving.