Uzair
Uzair

Reputation: 135

Enhanced for loop performance

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?

Upvotes: 6

Views: 3912

Answers (5)

Marko Topolnik
Marko Topolnik

Reputation: 200138

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(n2) 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.

Upvotes: 9

Amit Deshpande
Amit Deshpande

Reputation: 19185

for each variation will be same as below

for (Iterator i = c.iterator(); i.hasNext(); ) {
doSomething((Element) i.next()); 
}

From Item 46: Prefer for-each loops to traditional for loops of Effective java

for-each loop provides compelling advantages over the tradi- tional for loop in clarity and bug prevention, with no performance penalty. You should use it wherever you can.

So My first guess was wrong there is no penalty using function inside for each loop.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533432

As the extended loop uses an Iterator taken from the Iterable, it wouldn't be possible or sensible to execute someBean.getSpecialList() more than once. Moving it outside the loop will not change the performance of the loop, but you could do it if it improves readability.

Note: if you iterate by index it can be faster for random access collections e.g. ArrayList as it doesn't create an Iterator, but slower for indexed collections which don't support random access.

Upvotes: 0

aviad
aviad

Reputation: 8278

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

Upvotes: 5

codebox
codebox

Reputation: 20254

An alternative to the first snippet would be:

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

With regard to the for..each loop, the call to getSpecialList() will only be made once (you could verify this by adding some debugging/logging inside the method).

Upvotes: 0

Related Questions