Which is more efficient a for-each loop or an iterator

Question

Which is the most efficient way to traverse a collection   List lt Integer gt   a   new ArrayList lt Integer gt     for  Integer integer   a      integer toString        or  List lt Integer gt   a   new ArrayList lt Integer gt     for  Iterator iterator   a iterator    iterator hasNext          Integer integer    Integer  iterator next       integer toString        Please note  that this is not an exact duplicate of this  this  this  or this  although one of the answers to the last question comes close  The reason that this is not a dupe  is that most of these are comparing loops where you call get i  inside the loop  rather than using the iterator   As suggested on Meta I will be posting my answer to this question

User · Answer

The foreach underhood is creating the iterator  calling hasNext   and calling next   to get the value  The issue with the performance comes only if you are using something that implements the RandomomAccess    for  Iterator lt CustomObj gt  iter   customList iterator    iter hasNext        CustomObj custObj   iter next                Performance issues with the iterator-based loop is because it is     allocating an object even if the list is empty  Iterator lt CustomObj gt  iter   customList iterator      iter hasNext   during every iteration of the loop there is an invokeInterface virtual call  go through all the classes  then do method table lookup before the jump   the implementation of the iterator has to do at least 2 fields lookup in order to make hasNext   call figure the value   1 get current count and  2 get total count inside the body loop  there is another invokeInterface virtual call iter next so  go through all the classes and do method table lookup before the jump  and as well has to do fields lookup   1 get the index and  2 get the reference to the array to do the offset into it  in every iteration     A potential optimiziation is to switch to an index iteration with the cached size lookup   for int x   0  size   customList size    x  lt  size  x       CustomObj custObj   customList get x             Here we have    one invokeInterface virtual method call customList size   on the initial creation of the for loop to get the size  the get method call customList get x  during the body for loop  which is a field lookup to the array and then can do the offset into the array   We reduced a ton of method calls  field lookups  This you don t want to do with LinkedList or with something that is not a RandomAccess collection obj  otherwise the customList get x  is gonna turn into something that has to traverse the LinkedList on every iteration    This is perfect when you know that is any RandomAccess based list collection

User · Answer

To expand on Paul s own answer  he has demonstrated that the bytecode is the same on that particular compiler  presumably Sun s javac   but different compilers are not guaranteed to generate the same bytecode  right  To see what the actual difference is between the two  let s go straight to the source and check the Java Language Specification  specifically 14 14 2   The enhanced for statement       The enhanced for statement is equivalent to a basic for statement of the form    for  I  i   Expression iterator     i hasNext            VariableModifiers opt  Type Identifier    i next            Statement      In other words  it is required by the JLS that the two are equivalent  In theory that could mean marginal differences in bytecode  but in reality the enhanced for loop is required to    Invoke the  iterator   method Use  hasNext   Make the local variable available via  next     So  in other words  for all practical purposes the bytecode will be identical  or nearly-identical  It s hard to envisage any compiler implementation which would result in any significant difference between the two

User · Answer

The difference isn t in performance  but in capability   When using a reference directly you have more power over explicitly using a type of iterator  e g  List iterator   vs  List listIterator    although in most cases they return the same implementation    You also have the ability to reference the Iterator in your loop   This allows you to do things like remove items from your collection without getting a ConcurrentModificationException   e g   This is ok   Set lt Object gt  set   new HashSet lt Object gt        add some items to the set  Iterator lt Object gt  setIterator   set iterator    while setIterator hasNext          Object o   setIterator next         if o meets some condition             setIterator remove                 This is not  as it will throw a concurrent modification exception   Set lt Object gt  set   new HashSet lt Object gt        add some items to the set  for Object o   set        if o meets some condition             set remove o

User · Answer

Iterator is an interface in the Java Collections framework that provides methods to traverse or iterate over a collection    Both iterator and for loop acts similar when your motive is to just traverse over a collection to read its elements    for-each is just one way to iterate over the Collection    For example   List lt String gt  messages  new ArrayList lt  gt        using for-each loop for String msg  messages       System out println msg        using iterator  Iterator lt String gt  it   messages iterator    while it hasNext         String msg   it next        System out println msg       And for-each loop can be used only on objects implementing the iterator interface   Now back to the case of for loop and iterator   The difference comes when you try to modify a collection  In this case  iterator is more efficient because of its fail-fast property  ie  it checks for any modification in the structure of underlying collection before iterating over the next element  If there are any modifications found  it will throw the ConcurrentModificationException     Note  This functionality of iterator is only applicable in case of collection classes in java util package  It is not applicable for concurrent collections as they are fail-safe by nature

User · Answer

If you are just wandering over the collection to read all of the values  then there is no difference between using an iterator or the new for loop syntax  as the new syntax just uses the iterator underwater   If however  you mean by loop the old  c-style  loop   for int i 0  i lt list size    i         Object o   list get i       Then the new for loop  or iterator  can be a lot more efficient  depending on the underlying data structure  The reason for this is that for some data structures  get i  is an O n  operation  which makes the loop an O n2  operation  A traditional linked list is an example of such a data structure  All iterators have as a fundamental requirement that next   should be an O 1  operation  making the loop O n    To verify that the iterator is used underwater by the new for loop syntax  compare the generated bytecodes from the following two Java snippets  First the for loop   List lt Integer gt   a   new ArrayList lt Integer gt     for  Integer integer   a      integer toString         Byte code  ALOAD 1  INVOKEINTERFACE java util List iterator  Ljava util Iterator   ASTORE 3  GOTO L2 L3  ALOAD 3  INVOKEINTERFACE java util Iterator next  Ljava lang Object   CHECKCAST java lang Integer  ASTORE 2   ALOAD 2  INVOKEVIRTUAL java lang Integer toString  Ljava lang String   POP L2  ALOAD 3  INVOKEINTERFACE java util Iterator hasNext  Z  IFNE L3   And second  the iterator   List lt Integer gt   a   new ArrayList lt Integer gt     for  Iterator iterator   a iterator    iterator hasNext         Integer integer    Integer  iterator next      integer toString         Bytecode   ALOAD 1  INVOKEINTERFACE java util List iterator  Ljava util Iterator   ASTORE 2  GOTO L7 L8  ALOAD 2  INVOKEINTERFACE java util Iterator next  Ljava lang Object   CHECKCAST java lang Integer  ASTORE 3  ALOAD 3  INVOKEVIRTUAL java lang Integer toString  Ljava lang String   POP L7  ALOAD 2  INVOKEINTERFACE java util Iterator hasNext  Z  IFNE L8   As you can see  the generated byte code is effectively identical  so there is no performance penalty to using either form  Therefore  you should choose the form of loop that is most aesthetically appealing to you  for most people that will be the for-each loop  as that has less boilerplate code

User · Answer

foreach uses iterators under the hood anyway  It really is just syntactic sugar   Consider the following program   import java util List  import java util ArrayList   public class Whatever       private final List lt Integer gt  list   new ArrayList lt  gt         public void main             for Integer i   list                        Let s compile it with javac Whatever java  And read the disassembled bytecode of main    using javap -c Whatever   public void main      Code       0  aload 0      1  getfield       4                     Field list Ljava util List       4  invokeinterface  5   1               InterfaceMethod java util List iterator   Ljava util Iterator       9  astore 1     10  aload 1     11  invokeinterface  6   1               InterfaceMethod java util Iterator hasNext   Z     16  ifeq          32     19  aload 1     20  invokeinterface  7   1               InterfaceMethod java util Iterator next   Ljava lang Object      25  checkcast      8                     class java lang Integer     28  astore 2     29  goto          10     32  return   We can see that foreach compiles down to a program which    Creates iterator using List iterator   If Iterator hasNext    invokes Iterator next   and continues loop     As for  why doesn t this useless loop get optimized out of the compiled code  we can see that it doesn t do anything with the list item   well  it s possible for you to code your iterable such that  iterator   has side-effects  or so that  hasNext   has side-effects or meaningful consequences   You could easily imagine that an iterable representing a scrollable query from a database might do something dramatic on  hasNext    like contacting the database  or closing a cursor because you ve reached the end of the result set    So  even though we can prove that nothing happens in the loop body    it is more expensive  intractable   to prove that nothing meaningful consequential happens when we iterate  The compiler has to leave this empty loop body in the program   The best we could hope for would be a compiler warning  It s interesting that javac -Xlint all Whatever java does not warn us about this empty loop body  IntelliJ IDEA does though  Admittedly I have configured IntelliJ to use Eclipse Compiler  but that may not be the reason why

User · Answer

We should avoid using traditional for loop while working with Collections  The simple reason what I will give is that the complexity of for loop is of the order O sqr n   and complexity of Iterator or even the enhanced for loop is just O n   So it gives a performence difference   Just take a list of some 1000 items and print it using both ways  and also print the time difference for the execution  You can sees the difference

[java] Which is more efficient, a for-each loop, or an iterator?

Examples related to java

Examples related to collections

Examples related to foreach