Performance: Iterating through a List in Java

Question

Is it slower to iterate through a list in Java like this:

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

as opposed to:

for (Object o: list) {
    ... o
}

Answer 1

I assume you ask out of pure curiosity and won't cite Knuth (somebody probably will).

I believe that once your code gets compiled, it doesn't make a difference. It does make a difference before (example 2 is a lot more readable and concise), so go for number 2 and do not care about the rest.

Just my 2 cents

EDIT

Note your code in snippet number 1 calculates list.size() every time the loop runs, that could make it even slower than number 2

YET ANOTHER EDIT

Something I had to double check, Joshua Bloch recommends using for each loops (see item 46 of Effective Java). I believe that ends all kinds of discussions. Thanks Josh! :)

Answer 2

There shouldn't be any noticeable differences in performance for normal lists.

For linked lists, the iterator will be substantially faster, especially for large lists.

Answer 3

Created a microbenchmark for the question and was surprised to see for-each runing 2x-3x faster than an indexed loop. The only explanation I have is that for-each version might not require range checks which are made by ArrayList.get(int index).

For very small lists (10 elements) the result was about the same. For 100 elements for-each is 1.5x faster, for 10000-100000 elements it is faster 2x-3x times.

The tests are run on a random dataset and checksums are being verified at the end, so JIT chearing is very unlikely to take place in these.

Answer 4

According to benchmark tests in While loop, For loop and Iterator Performance Test – Java and the JavaRanch question "is using ArrayList.iterator() is faster than looping ArrayList in for loop?" the iterator is actually a bit slower.

I'd still favor readability unless I'd benchmarked my entire application and found that loop to be my bottleneck, though.

Answer 5

No. It is faster (or should be faster) when the list also implements: RandomAccess (as ArrayList does and LinkedList doesn't).

However, you should always use the latter :

 for( Object o: list ) {
 }

and only switch to the former if your have substantial evidence that you're having a performance issue using it (for instance, you profile your application and as result you see as a point for improvement this section of code).

By not doing so, you risk not being able to switch your implementation in a later refactoring if your application requires it (because you would be tied to the for( int i = 0 ; i < list.size(); i++ ) idiom).

Answer 6

THERE CAN BE A DIFFERENCE.

If a List implementation also implements java.util.RandomAccess (like ArrayList does), then it is just about faster to use its get() method over an interator.

If it does not implement java.util.RandomAccess (for example, LinkedList does not), then it is substantially faster to use an iterator.

However, this only matter if you are using lists containing thousands of (possibly scattered) objects or that are constantly traversed (as if performing copious amounts of math on List objects representing numerical vectors.)

Answer 7

Checking the size every iteration does add i operations, but it's not a big impact on performance.

By that, I mean there is a minor difference between

int lsize = myList.size();
for(int i=0; i < lsize; i++)
{
   Object o = myList.get(i);
}

Versus:

for(int i=0; i < myList.size(); i++)
{
   Object o = myList.get(i);
}

But it essentially doesn't matter. Use the second one from your question for readability, among other reasons.

Answer 8

It is recognized that the distinction between random and sequential * access is often fuzzy. For example, some List implementations * provide asymptotically linear access times if they get huge, but constant * access times in practice. Such a List implementation * should generally implement this interface. As a rule of thumb, a * List implementation should implement this interface if, * for typical instances of the class, this loop: *

 *     for (int i=0, n=list.size(); i < n; i++)
 *         list.get(i);
 * 

* runs faster than this loop: *

 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * 

*

Answer 9

I didn't look myself into the code of get() of all List implementations so maybe what I will write is some FUD. What I have learned is that using the get(i) in for loop will result in an iteration over the whole list over and over again each loop run. Using an Iterator (like enhanced for loop does) will just move the iterator the the next list element without iterating the whole list again.

My conclusion is that using iterators or the enhanced for loop should be more performant since using get() will result in complexity O(n^2) instead of O(n).