Performance of traditional for loop vs Iterator/foreach in Java

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.

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

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

Performance of traditional for loop vs Iterator/foreach in Java

Related

Recent Posts