Using collection size in for loop comparison

Question

Is there a compiler optimization for the size() methods of Collections in Java?

Consider the following code:

for(int i=0;i<list.size();i++)
      ...some operation.....

There is a call to the size() methods for every i. Won't it be better to find out the size and reuse it? (Method calls have overheads).

final int len = list.size()
for(int i=0;i<len;i++)
      ...some operation.....

However, when I timed both these code pieces there was no significant time difference, even for i as high as 10000000. Am I missing something here?

Update1: I understand that the size is not computed again unless the collection changes. But there has to be some overhead associated with a method call. Is it the case that the compiler always inlines these (See Esko's answer)?

Update 2: My curiosity has been fueled further. From the answers given, I see that good JIT compilers will often inline this function call. But they will still have to determine whether the collection was modified or not. I am not accepting an answer in the hope that someone will give me pointers regarding how this is handled by compilers.

Answer 1

Okay, here is an excerpt from the JDK sources (src.zip in the JDK folder):

public int size() {
    return size;
}

This is from ArrayList, but I think other collections have similar implementations. Now if we imagine that the compiler inlines the size() call (which would make perfect sense), your loop turns into this:

for(int i=0;i<list.size;i++)
// ...

(Well, let's forget that the size is private.) How does compiler checks if the collection was modified? The answer that it doesn't and doesn't need to do so because the size is already available in the field, so all it has to do is to access the size field on each iteration, but accessing an int variable is a very fast operation. Note that it probably calculates its address once, so it doesn't even have to dereference list on each iteration.

What happens when the collection is modified, say, by the add() method?

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

As you can see, it just increases the size field. So the compiler doesn't actually need to do anything to ensure it has access to the latest size. The only exception would be that if you modify the collection from another thread you need to synchronize, otherwise the loop thread may see its local cached value of size which may or may not be updated.

Answer 2

The value returned by collection's .size() method is usually cached and recalculated only when the actual collection is modified (new elements are added or old ones removed).

Instead of comparing for loop control scoping, try using the for each loop since that actually uses Iterator which in some collection implementations is a lot faster than iterating by using index.

Answer 3

Calling the size() method of a collection is just returning an integer value that is already kept track of. There isnt much of a time difference because size() isnt actually counting the number of items but instead the number of items are kept track of when you add or remove them.

Answer 4

The java language specification explains, that the expression is evaluated on each iteration step. With you example, list.size() is called 10.000.000 times.

This doesn't matter in your case, because list implementations (usually) have a private attribute that stores the actual list size. But it may cause trouble, if the evaluation really takes time. In those cases it's advisable to store the result of the expression to a local variable.