Performance of traditional for loop vs Iterator/foreach in Java

Question

Is there any performance testing results available in comparing traditional for loop vs Iterator while traversing a ArrayList,HashMap and other collections?

Or simply why should I use Iterator over for loop or vice versa?

Answer 1

Assuming this is what you meant:

// traditional for loop
for (int i = 0; i < collection.size(); i++) {
  T obj = collection.get(i);
  // snip
}

// using iterator
Iterator<T> iter = collection.iterator();
while (iter.hasNext()) {
  T obj = iter.next();
  // snip
}

// using iterator internally (confirm it yourself using javap -c)
for (T obj : collection) {
   // snip
}

Iterator is faster for collections with no random access (e.g. TreeSet, HashMap, LinkedList). For arrays and ArrayLists, performance differences should be negligible.

Edit: I believe that micro-benchmarking is root of pretty much evil, just like early optimization. But then again, I think it's good to have a feeling for the implications of such quite trivial things. Hence I've run a small test:

• iterate over a LinkedList and an ArrayList respecively
• with 100,000 "random" strings
• summing up their length (just something to avoid that compiler optimizes away the whole loop)
• using all 3 loop styles (iterator, for each, for with counter)

Results are similar for all but "for with counter" with LinkedList. All the other five took less than 20 milliseconds to iterate over the whole list. Using list.get(i) on a LinkedList 100,000 times took more than 2 minutes (!) to complete (60,000 times slower). Wow! :) Hence it's best to use an iterator (explicitly or implicitly using for each), especially if you don't know what type and size of list your dealing with.

Answer 2

The first reason to use an iterator is obvious correctness. If you use a manual index, there may be very innocuous off-by-one errors that you can only see if you look very closely: did you start at 1 or at 0? Did you finish at length - 1? Did you use < or <=? If you use an iterator, it is much easier to see that it is really iterating the whole array. "Say what you do, do what you say."

The second reason is uniform access to different data structures. An array can be accessed efficiently through an index, but a linked list is best traversed by remembering the last element accessed (otherwise you get a "Shlemiel the painter"). A hashmap is even more complicated. By providing a uniform interface from these and other data structures (e.g., you can also do tree traversals), you get obvious correctness again. The traversing logic has to be implemented only once, and the code using it can concisely "say what it does, and do what it says."

Answer 3

Performance is similar in most cases.

However, whenever a code receives a List, and loops on it, there is well-known case:
the Iterator is way better for all List implementations that do not implement RandomAccess (example: LinkedList).

The reason is that for these lists, accessing an element by index is not a constant time operation.

So you can also consider the Iterator as more robust (to implementation details).

---

As always, performance should not be hide readability issues.
The java5 foreach loop is a big hit on that aspect :-)

Answer 4

Yes, it does make a difference on collections which are not random access based like LinkedList. A linked list internally is implemented by nodes pointing to the next(starting at a head node).

The get(i) method in a linked list starts from the head node and navigates through the links all the way to the i'th node. When you iterate on the linked list using a traditional for loop, you start again from the head node each time, thus the overall traversal becomes quadratic time.

for( int i = 0; i< list.size(); i++ ) {
    list.get(i); //this starts everytime from the head node instead of previous node
}

While the for each loop iterates over the iterator obtained from the linked list and calls its next() method. The iterator maintains the states of the last access and thus does not start all the way from head everytime.

for( Object item: list ) {
    //item element is obtained from the iterator's next method.
}

Answer 5

One of the best reasons to use an iterator over the i++ syntax is that not all data structures will support random access let alone have it perform well. You should also be programming to the list or collection interface so that if you later decided that another data structure would be more efficient you'd be able to swap it out without massive surgery. In that case (the case of coding to an interface) you won't necessarily know the implementation details and it's probably wiser to defer that to the data structure itself.

Answer 6

One of the reasons I've learned to stick with the for each is that it simplifies nested loops, especially over 2+ dimensional loops. All the i's, j's, and k's that you may end up manipulating can get confusing very quickly.

Answer 7

Use JAD or JD-GUI against your generated code, and you will see that there is no real difference. The advantage of the new iterator form is that it looks cleaner in your codebase.

Edit: I see from the other answers that you actually meant the difference between using get(i) versus an iterator. I took the original question to mean the difference between the old and new ways of using the iterator.

Using get(i) and maintaining your own counter, especially for the List classes is not a good idea, for the reasons mentioned in the accepted answer.

Answer 8

I don't believe that

for (T obj : collection) {

calculates .size() each time thru the loop and is therefore faster than

for (int i = 0; i < collection.size(); i++) {

Answer 9

+1 to what sfussenegger said. FYI, whether you use an explicit iterator or an implicit one (i.e. for each) won't make a performance difference because they compile to the same byte code.