Enhanced for loop performance

Question

I had an argument with my friend regarding this. Consider the below snippet,

for(i=0; i<someList.size(); i++) {
    //some logic
    }

Here someList.size() will be executed for every iteration, so it is recommended to migrate this size calculation to outside(before) the loop.

Now what happens when I use an extended for loop like this,

for(SpecialBean bean: someBean.getSpecialList()) {
//some logic
}

Is it necessary to move someBean.getSpecialList() to outside the loop? How many times will someBean.getSpecialList() execute if I were to retain the 2nd snippet as it is?

Answer 1

Repeated calls to list.size() won't result in any performance penalty. The JIT compiler will most probably inline it and even if it doesn't, it will still be quite inexpensive because it just involves reading the value of a field.

A much more serious problem with your first example is that the loop body will have to involve list.get(i) and for a LinkedList, acessing the i th element has O(i) cost with a quite significant constant factor due to pointer chasing, which translates to data-dependent loads on the CPU level. The CPU's prefetcher can't optimize this access pattern.

This means that the overall computational complexity will be O(n²) when applied to a LinkedList.

Your second example compiles to iteration via Iterator and will evaluate someBean.getSpecialList().iterator() only once. The cost of iterator.next() is constant in all cases.

Answer 2

From Item 46 in Effective Java by Joshua Bloch :

The for-each loop, introduced in release 1.5, gets rid of the clutter and the opportunity for error by hiding the iterator or index variable completely. The resulting idiom applies equally to collections and arrays:

// The preferred idiom for iterating over collections and arrays for (Element e : elements) { doSomething(e); } When you see the colon (:), read it as “in.” Thus, the loop above reads as “for each element e in elements.” Note that there is no performance penalty for using the for-each loop, even for arrays. In fact, it may offer a slight performance advantage over an ordinary for loop in some circumstances, as it computes the limit of the array index only once. While you can do this by hand (Item 45), programmers don’t always do so.

See also is-there-a-performance-difference-between-a-for-loop-and-a-for-each-loop