is using ArrayList.iterator() is faster than looping ArrayList in for loop?

[hasan khan]

is using Iterating ArrayList is faster than getting each element of ArrayList inside for loop.

[Jeroen T Wenting]

potentially, depending on the internal implementation of the iterator.

[William Brogden]

I will never understand why people ask questions like this when a few minutes writing a test case program would give you an answer.

[steve souza]

I will never understand why people ask questions like this when a few minutes writing a test case program would give you an answer.

Beyond that the difference is usually so minimal that it makes no impact on a production application. Design well, monitor, tune where needed and then repeat.

[Mr. C Lamont Gilbert]

Originally posted by William Brogden:
I will never understand why people ask questions like this when a few minutes writing a test case program would give you an answer.

Because this is not an implementation question, its a question of principle.

The answer is, the iterator is the correct way.

If you use an iterator, and there is invented a faster way of iterating, then Sun can implement that and speed up your program without you having to change anything.

If you wrote the iteration yourself, then you will have to modify your own code to take advantage of this advance.

So it does not matter which tests faster, the only correct way is to use the 'iterator.'

[Ashwath Rangan]

I am sorry but i differ from the opinion that using .iterator() is the correct usage.
ArrayList actually implements a marker interface RandomAccess which means that it is possible to fetch any element in the list.
U ll find this in the java docs

http://java.sun.com/j2se/1.4.2/docs/api/java/util/RandomAccess.html

[William Brogden]

Because this is not an implementation question, its a question of principle.

Wow - political correctness in programming.

The OP asked about speed - since .iterator() involves creating a new object, if you don't need the special properties of iterators but do need speed, why use one?

Bill

[Justin Chu]

Someone has mentioned about the disassociation of performing iteration from the actual implementation.

Suppose someday later, your code is modified to use a LinkedList, then your .get(i) approach will have worse performance than using an Iterator.

Iterator design abstracts the act of iterating, and all implementations of List will have the optimal implementation for that data structure.
[ February 04, 2007: Message edited by: Chu Tan ]

[Sushil Sharma]

I did a basic test to benchmark iterator and for loop. The iterator over a sample size of 10,000 runs takes 40 ms; where as for loop takes 2 ms.

Code

import java.util.*;
 
public class Arrtest
{
    public static void main(String[] args)
    {
        ArrayList<String> alist = new ArrayList<String>();
        long start, end;
        
        for (int i = 0; i < 1000000; i++) {
            alist.add(String.valueOf(i));
        }
        
        ListIterator<String> it = alist.listIterator();    
        
        start = System.currentTimeMillis();
        while (it.hasNext()) {
            String s = it.next();
        }
        end = System.currentTimeMillis();
        
        System.out.println("Iterator start: " + start + ", end: " + end + ", delta: "
            + (end - start));
        start = System.currentTimeMillis();
        int ixx = 0;
        for (int i = 0; i < 100000; i++) {
            String s = alist.get(i);
        }
        
        System.out.println(ixx);
        end = System.currentTimeMillis();
        System.out.println("for loop start: " + start + ", end: " + end + ", delta: "
            + (end - start));
        
    }
}    

[Jim Yingst]

Well, one issue here is that your iterator code is going through the entire loop, and the for loop code is only going through a tenth of the loop. Another issue is that the loops are still too small and short to be reliably measured - HotSpot optimizations can take a few seconds before their effects are apparant. Try repeating each loop ten times (or a hundred) and measuring the total time for all the loops.

[Sushil Sharma]

I modified loop to do a 10 x 1000000. The results are:

for loop: 125 ms
iterator: 359 ms

Platform: Windows XP, Xeon 3.2GHz, 2GB RAM, Java 1.5

[steve souza]

I suspect your results may vary based on many factors including the jvm used, collections used, hot spot and more. Still the results are interesting.

I modified your program a bit. I used jamon for the timings, and ran the tests 500 times. Each of the 5 test cases I performed was run 500 times and each test case iterated/looped through all 1 million rows of data. I added a couple other cases 1) a for loop decrementing the counter (people often ask about this), 2) A regular iterator, 2) and the new "For each" idiom.

Here are the abbreviated results. Note that the for loops were about twice as fast. Although in this test suite decrement was slightly faster than increment for loop this varied and doesn't seem to be a factor (notice that the min and max for these are the same). For each is in between iterators and the for loops for performance.


The units for avg/total/min/max are in ms.

JAMon Label=listIterator, Units=ms.: (Hits=500.0, Avg=66.06, Total=33030.0, Min=47.0, Max=94.0)
JAMon Label=iterator, Units=ms.: (Hits=500.0, Avg=66.368, Total=33184.0, Min=47.0, Max=110.0)
JAMon Label=forEach, Units=ms.: (Hits=500.0, Avg=57.876, Total=28938.0, Min=46.0, Max=79.0)
JAMon Label=forLoopIncr, Units=ms.: (Hits=500.0, Avg=27.024, Total=13512.0, Min=15.0, Max=47.0)
JAMon Label=forLoopDecr, Units=ms.: (Hits=500.0, Avg=26.888, Total=13444.0, Min=15.0, Max=47.0)

    
 
 
package com.tester;
 
import java.util.*;
import com.jamonapi.*;
 
public class ArrayListTester {
 
   private static final int NUM_LIST_VALUES=1000000;
   private static final int TEST_EXECTUIONS=500;
 
   private static void iterator(String label, Iterator<String> iter) {
 
      Monitor mon=MonitorFactory.start(label);
         while (iter.hasNext()) {
            String s=iter.next();
        }
 
        System.out.println(mon.stop());
   }
 
   private static void forEach(String label, Collection<String> c) {
    Monitor mon=MonitorFactory.start(label);
    for (String str : c) {
        String s=str;
    }
    
        System.out.println(mon.stop());
   }
   
   
   private static void forLoopIncr(String label, List<String> c){
Monitor mon=MonitorFactory.start(label);
 
        int size=c.size();
        for (int i = 0; i < size; i++) {
            String s = c.get(i);
 
        }
 
        System.out.println(mon.stop());
 
   }
   
 
   private static void forLoopDecr(String label, List<String> c){
   
Monitor mon=MonitorFactory.start(label);
 
        int size=c.size()-1;
        for (int i = size; i >= 0; i--) {
            String s = c.get(i);
 
        }
 
        System.out.println(mon.stop());
 
   }
 
 
    public static void main(String[] args)
    {
        ArrayList<String> alist = new ArrayList<String>();
  
        for (int i = 0; i < NUM_LIST_VALUES; i++) {
            alist.add(String.valueOf(i));
        }
        
 
        for (int i=0;i<TEST_EXECTUIONS;i++) {
          iterator("listIterator", alist.listIterator());
          iterator("iterator", alist.iterator());
          forEach("forEach", alist);
          forLoopIncr("forLoopIncr", alist);
          forLoopDecr("forLoopDecr", alist);
        }
        
        
        
    }
}
 

[ February 07, 2007: Message edited by: steve souza ]

[steve souza]

Suppose someday later, your code is modified to use a LinkedList, then your .get(i) approach will have worse performance than using an Iterator.

Iterator design abstracts the act of iterating, and all implementations of List will have the optimal implementation for that data structure.

As this post mentions changing your List from an ArrayList to a LinkedList had a big impact on performance. I had to bring down the number of elements in the list from 1,000,000 to 50,000 and even still the for loop approach took over 6 seconds, and the iterator took less than a millisecond! This indicates that in general it is best to use the ForEach approach or an iterator.

JAMon Label=listIterator, Units=ms.: (Hits=1.0, Avg=0.0, Total=0.0, Min=0.0, Max=0.0)
JAMon Label=iterator, Units=ms.: (Hits=1.0, Avg=0.0, Total=0.0, Min=0.0, Max=0.0)
JAMon Label=forEach, Units=ms.: (Hits=1.0, Avg=0.0, Total=0.0, Min=0.0, Max=0.0)
JAMon Label=forLoopIncr, Units=ms.: (Hits=1.0, Avg=6015.0, Total=6015.0, Min=6015.0, Max=6015.0)
JAMon Label=forLoopDecr, Units=ms.: (Hits=1.0, Avg=6047.0, Total=6047.0, Min=6047.0, Max=6047.0)

To run the test I changed this:
ArrayList<String> alist = new ArrayList<String>();

to this:
LinkedList<String> alist = new LinkedList<String>();

[steve souza]

I reran the previous test 10 times to get more realistic numbers, and eliminated the decrement loop as it doesn't seem to effect performance and I didn't want to wait for it.

JAMon Label=listIterator, Units=ms.: (Hits=10.0, Avg=7.9, Total=79.0, Min=0.0, Max=16.0)
JAMon Label=iterator, Units=ms.: (Hits=10.0, Avg=3.1, Total=31.0, Min=0.0, Max=16.0)
JAMon Label=forEach, Units=ms.: (Hits=10.0, Avg=1.6, Total=16.0, Min=0.0, Max=16.0)
JAMon Label=forLoopIncr, Units=ms.: (Hits=10.0, Avg=6029.7, Total=60297.0, Min=5968.0, Max=6172.0)


Then I performed the test on the listiterator, iterator, and foreach 1000 times each and performance of all 3 approaches look the same!. The lesson here is that beware of benchmarks!

JAMon Label=listIterator, Units=ms.: (Hits=1000.0, Avg=3.318, Total=3318.0, Min=0.0, Max=16.0)
JAMon Label=iterator, Units=ms.: (Hits=1000.0, Avg=3.124, Total=3124.0, Min=0.0, Max=16.0)
JAMon Label=forEach, Units=ms.: (Hits=1000.0, Avg=3.28, Total=3280.0, Min=0.0, Max=16.0)

[Matt Elliott]

Sorry about reviving a dead thread, but I feel this adds to the discussion.

I found in the actual running of production code that the iterator locks the data structure, and other threads are blocked from accessing it.
This did infact create a slow down.

[Norman Larson]

I found this thread because I was trying to answer the same question as you. After looking around for awhile at similar threads and running some tests, I've come to the conclusion that the fastest way to iterate through a collection is to use an ArrayList, convert it to an array (using .toArray()) and then iterate through that backwards using a normal loop. (I iterate backwards so I only have to call arr.length once, e.g. (for int i=arr.length-1;i>=0;i--)). I guess technically the array by itself is faster, but ArrayLists are much more convenient, and the toArray() function adds negligible time.

Below I'm listing the best results I found and some data from my test. In my test, I iterated over 300,000 elements in a colection. and I profiled as well (using NetBeans) so that I could actually understand WHY different operations were taking different amounts of time. So the run times I report would actually be much smaller if I weren't using the profiler, but since we only care about relative time, it doesn't really matter. My JVM, by the way, was the basic Sun Java 6 JVM for Ubuntu.

From fastest to slowest:

1) ArrayList, converted to an array via .toArray(), then looping backwards with a normal for-loop

The .toArray() added very minimal extra time (41 ms total), and looping through the array added about the same amount (total, that is).

2) ArrayList, looping backwards with a normal for-loop

ArrayList has a function called RangeCheck within get(i) that adds a fair amount of time. You don't really need to do that, since you've already established with the for-loop that your indexes are within the right range, so it's just wasted effort.

Total: 338 ms.

3) LinkedList, for-each loop

AbstractList$Itr invokes something called checkForComodification, which adds some time.

Total: 551 ms.

4) ArrayList, for-each loop

AbstractList$Itr actually just calls the ArrayList's get(int i) function, so it can't POSSIBLY be faster than a standard for-loop through the ArrayList. Plus it invokes that checkForComodification.

Total: 1053 ms.

On #3 and #4, I should mention that I also tried iterators as well as for-each loops, but there wasn't much difference (because they call the same methods). You may think you can be clever and save time by using a try/catch on NoSuchElementException to avoid the hasNext() check each time, but it didn't seem to help much. Actually, the hasNext() function is much less expensive than the next() function, whereas the initialization of the exception itself actually adds a significant amount of time, so at best you'd probably break even.

So I guess the moral of the story is: wrappers add time. If you want speed, go for the most basic objects in the programming language (like arrays). However, more importantly, get a profiler (NetBeans is great, and it's free). You don't want to ugly up your code by converting ArrayLists into arrays and iterating backwards all over the place if you don't have to. That would probably just slow down your development process and make it harder to maintain your code. Just do these kinds of fixes where absolutely necessary, because a for-each loop is much cleaner.

Anyway, I invite people to verify my results. I wish there were more threads like this around, because I think these kinds of discussions are fascinating!

[Matt Elliott]

I'd actually like to see your code so I could run the same tests.

[Norman Larson]

OK, I've attached a quick program I wrote to test the speed of various Java lists and different ways of iterating through them. To run the test, I first create a simple short list of Strings and multiply its size by various pre-defined sizes ("relativeSizes"). Then I cast the list to whatever data structure I want, iterate through each string, and just call .hashCode() on each one. I repeat this experiment 100 times for each data structure and average the results. By the way, you can set the variables to be whatever you want and run the tests yourself.

The punchline is that I was wrong about how well ArrayList.toArray()+forloop works with very large lists - eventually the performance starts to degrade as, presumably, Java is taking more and more time to do the Arrays.copyOf() operation and allocate new space to the newly constructed Array. So with very large lists, the ArrayList with a standard for-loop seems to be the way to go. The ArrayList.toArray()+forloop is still great with medium-sized lists, though, and of course the Array by itself is always the fastest. (With the exception of the very small lists, though - the measurements there are all over the place, but I figure that's because milliseconds are too coarse a measure to really mean anything in those cases.)

Overall, though, I think my results just confirm what others on this thread have shown. Here are the full results:

relativeSize=100
testing loop on the array alone
Took 0.11 ms on average
testing .toArray() and basic for-loop on the array
Took 0.05 ms on average
testing ArrayList with basic for-loop
Took 0.1 ms on average
testing LinkedList with for-each
Took 0.15 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 0.11 ms on average
testing ArrayList with for-each
Took 0.17 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 0.1 ms on average


----------------


relativeSize=500
testing loop on the array alone
Took 0.04 ms on average
testing .toArray() and basic for-loop on the array
Took 0.04 ms on average
testing ArrayList with basic for-loop
Took 0.04 ms on average
testing LinkedList with for-each
Took 0.06 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 0.05 ms on average
testing ArrayList with for-each
Took 0.19 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 0.11 ms on average


----------------


relativeSize=1000
testing loop on the array alone
Took 0.07 ms on average
testing .toArray() and basic for-loop on the array
Took 0.08 ms on average
testing ArrayList with basic for-loop
Took 0.09 ms on average
testing LinkedList with for-each
Took 0.13 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 0.11 ms on average
testing ArrayList with for-each
Took 0.38 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 0.18 ms on average


----------------


relativeSize=5000
testing loop on the array alone
Took 0.3 ms on average
testing .toArray() and basic for-loop on the array
Took 0.33 ms on average
testing ArrayList with basic for-loop
Took 0.49 ms on average
testing LinkedList with for-each
Took 0.64 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 0.5 ms on average
testing ArrayList with for-each
Took 1.75 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 0.78 ms on average


----------------


relativeSize=10000
testing loop on the array alone
Took 0.49 ms on average
testing .toArray() and basic for-loop on the array
Took 0.71 ms on average
testing ArrayList with basic for-loop
Took 0.85 ms on average
testing LinkedList with for-each
Took 1.38 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 1.06 ms on average
testing ArrayList with for-each
Took 3.63 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 1.56 ms on average


----------------


relativeSize=50000
testing loop on the array alone
Took 2.63 ms on average
testing .toArray() and basic for-loop on the array
Took 17.62 ms on average
testing ArrayList with basic for-loop
Took 4.18 ms on average
testing LinkedList with for-each
Took 6.97 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 5.03 ms on average
testing ArrayList with for-each
Took 17.42 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 7.53 ms on average


----------------


relativeSize=100000
testing loop on the array alone
Took 5.63 ms on average
testing .toArray() and basic for-loop on the array
Took 17.31 ms on average
testing ArrayList with basic for-loop
Took 8.76 ms on average
testing LinkedList with for-each
Took 13.55 ms on average
testing LinkedList with 'clever' iterator where we don't call hasNext()
Took 10.14 ms on average
testing ArrayList with for-each
Took 35.47 ms on average
testing ArrayList with 'clever' iterator where we don't call hasNext()
Took 15.04 ms on average

[Norman Larson]

By the way, attached is a chart of the above test results for your viewing pleasure. I cut out the 100-length list set (because the results were too wonky, like I explained above) and took the time in milliseconds per 100 entries in the list as the Y value.

[edit] that last item should be "ArrayList ('clever' itr)", not "LinkedList ('clever' itr)".

[Norman Larson]

Dangit, forgot to attach the program.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
/**
 *
 * Test how fast different list iterators are by iterating through different collections of strings and just calling hashCode on each one
 * (hashCode() does not cache)
 */
public class IteratorTest {
    public static void main(String[] args) {
        int[] relativeSizes = new int[]{100,500,1000, 5000, 10000, 50000, 100000};
        int numTimesToTestEachLoop = 100;
        for (int relativeSize : relativeSizes) {
            System.out.println("relativeSize=" + relativeSize);
            Timer timer = new Timer();
            ArrayList<String> oldArrayList = new ArrayList<String>(Arrays.asList(new String[]{"foo", "bar", "baz", "larry", "moe", "curly"}));
            ArrayList<String> arrayList = new ArrayList<String>();

            // make the arr huge; copy it several times
            for (int i = 0; i < relativeSize; i++) {
                arrayList.addAll(oldArrayList);
            }
            System.out.println("testing loop on the array alone");
            double totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                Object[] arr = arrayList.toArray();
                timer.start();
                for (int i = arr.length - 1; i >= 0; i--) {
                    ((String) arr[i]).hashCode();
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing .toArray() and basic for-loop on the array");
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                Object[] arr = arrayList.toArray();
                for (int i = arr.length - 1; i >= 0; i--) {
                    ((String) arr[i]).hashCode();
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing ArrayList with basic for-loop");
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                for (int i = arrayList.size() - 1; i >= 0; i--) {
                    arrayList.get(i).hashCode();
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing LinkedList with for-each");
            LinkedList<String> linkedList = new LinkedList<String>(arrayList);
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                for (String str : linkedList) {
                    str.hashCode();
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing LinkedList with 'clever' iterator where we don't call hasNext()");
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                Iterator<String> itr = linkedList.iterator();
                for (;;) {
                    try {
                        itr.next().hashCode();
                    } catch (NoSuchElementException e) {
                        break;
                    }
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing ArrayList with for-each");
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                for (String str : arrayList) {
                    str.hashCode();
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");
            System.out.println("testing ArrayList with 'clever' iterator where we don't call hasNext()");
            totalTime = 0.0;
            for (int j = 0; j < numTimesToTestEachLoop; j++) {
                timer.start();
                Iterator<String> itr = arrayList.iterator();
                for (;;) {
                    try {
                        itr.next().hashCode();
                    } catch (NoSuchElementException e) {
                        break;
                    }
                }
                totalTime += timer.stop();
            }
            System.out.println("Took " + (totalTime / numTimesToTestEachLoop) + " ms on average");

            System.out.println("\n\n----------------\n\n");
            // let the system garbage collect for awhile
            System.gc();
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
            }
        }
    }
    /**
     * simple start-stop timer
     */
    private static class Timer {
        private long savedTime;
        public void start() {
            savedTime = System.currentTimeMillis();
        }
        public long stop() {
            try {
                return System.currentTimeMillis() - savedTime;
            } catch (NullPointerException e) { // start wasn't called
                throw new IllegalStateException("call start() first", e);
            }
        }
    }
}  

[Matt Elliott]

Everyone seems to be doing large lists, does the size of the list matter?

[Billy Tsai]

I know this is partially irrelevant but I will still post my question in this thread for informatvie purpose.

In a multi-threaded scenario where concurrent access occurs, can the Iterator.remove() method still be used even if the Iterator object is declared as a local variable and is derived from calling the iterator() method on a java.util.List that is also created as a local variable within the same method?

[J Westland]

@billy: Even if you can, would this really be a good idea?

As the remove() behaviour is unspecified if the collection changes while you are iterating over it...

[Tim Holloway]

J Westland wrote:@billy: Even if you can, would this really be a good idea?

As the remove() behaviour is unspecified if the collection changes while you are iterating over it...

Actually, I don't think that's true, at least in all cases. I seem to recall some Javadocs that very explicitly allowed using remove() on an iterator cursor. Since remove() simply removes the object from that particular collection, the object itself is unaffected, although it may then become eligible for garbage collection if there are no other references to it. Executing remove() on any other object in the iterator, however, is something that can be perilous in the extreme. In any case, I only recommend removing objects from an iterator if the iterator explicitly supports doing so. Some iterators are static snapshots of the collection at the time they were formed, but some are dynamic views and can become seriously confused if objects are reshuffled, added, or removed while iterating.

As far as coding, I recommend the "foreach" notation for iteration rather than explicit code. It's usually less typing, the abstraction gives more flexibility (especially going to/from arrays to ArrayLists), and the optimizers are more likely to be tuned for this approach as new JVMs come out.

Only if there's a serious performance problem would I code otherwise and then only after actually benchmarking different approaches and measuring them in my own specific environment. However even before that I'd look at the bigger picture. Micro-optimization usually gives only incremental improvements - a lot of extra work for minimal return, but a more appropriate algorithm can often boost speed by several orders of magnitude.

[Billy Tsai]

In my question the Iterator and the Collection that the Iterator is derived from are both declared within a same method(method level scope) as local variables so I am assuming it is safe(thread safe) to execute the Iterator's remove() method as both objects are placed on the stack instead of the heap in the JVM, each thread has its own stack and also there is no other usage of that Collection object in the same method. Just want to confirm my assumption is correct.