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?

Marko Topolnik · Accepted Answer · 2018-07-31T16:28:00.750

9

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.

edited Jul 31 '18 at 16:28

answered Aug 28 '12 at 09:11

Marko Topolnik

195,646
29
319
436

Can you please clarify how will a LinkedList(if used) result in O(n^2)? – Uzair Aug 28 '12 at 09:17
1

The assumption is that you are going to iterate over the list elements in that loop body, and that involves `list.get(i)`, which is O(i) for a linked list. You will evaluate that *n* times, resulting in O(n^2) overall complexity. – Marko Topolnik Aug 28 '12 at 09:20
This answer is wrong. LinkedList.size call costs O(1) since it is a class member. Not calculated everytime it is called. Take a look at source code of LinkedList class. – kerberos84 Jul 31 '18 at 16:19
@kerberos84 That was a side point of the answer, anyway. The fundamental source of O(n2) complexity is indexed access. See the edited answer. – Marko Topolnik Jul 31 '18 at 16:28
@MarkoTopolnik no, list.size() was your reasoning for the o(n^2) and containing wrong information about that api call. So now it doesn't contain that wrong information anymore for further readers of this answer. – kerberos84 Aug 01 '18 at 13:07
@kerberos84 Nope, it wasn't, but I saw how it could be misinterpreted so I clarified in the recent edit. See the sentence: `Depending on circumstance, the calculation of list size may take O(n), so yet another source of O(n2) complexity, but size is more likely to be cached.` Note the phrase **yet another** because I tacitly assumed that the indexed iteration itself is O(n2). Also note "but size is more likely to be cached", which makes it clear that it is a side point. – Marko Topolnik Aug 01 '18 at 13:20
@MarkoTopolnik yes it was confusing and containing wrong information about java api. So now it is better, i think you will at least agree on that – kerberos84 Aug 01 '18 at 14:36
It is better now, absolutely. My own standards have risen in the last 6 years, too. But it is still untrue it contained _wrong_ information, it was just poorly written. The topic of the sentence above was intended to be not `LinkedList`, but a general `List` implementation. That intent was very poorly communicated. – Marko Topolnik Aug 01 '18 at 14:51

score 5 · Answer 2 · edited May 23 '17 at 11:51

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

Amit Deshpande · Answer 3 · 2012-08-28T09:20:00.387

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.

score 0 · Answer 4 · answered Aug 28 '12 at 09:09

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

score 0 · Answer 5 · answered Aug 28 '12 at 09:11

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.

Enhanced for loop performance

5 Answers5

Linked