aspose file tools*
The moose likes Performance and the fly likes is using ArrayList.iterator() is faster than looping ArrayList in for loop? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "is using ArrayList.iterator() is faster than looping ArrayList in for loop?" Watch "is using ArrayList.iterator() is faster than looping ArrayList in for loop?" New topic
Author

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

hasan khan
Ranch Hand

Joined: Aug 04, 2003
Posts: 222

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


SCJP, SCWCD
Jeroen T Wenting
Ranch Hand

Joined: Apr 21, 2006
Posts: 1847
potentially, depending on the internal implementation of the iterator.


42
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12682
    
    5
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
Ranch Hand

Joined: Jun 26, 2002
Posts: 852
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.


http://www.jamonapi.com/ - a fast, free open source performance tuning api.
JavaRanch Performance FAQ
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

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
Greenhorn

Joined: Jan 30, 2007
Posts: 6
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
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12682
    
    5
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
Ranch Hand

Joined: Apr 19, 2002
Posts: 209
    
    1
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
Greenhorn

Joined: Nov 02, 2006
Posts: 22
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

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.


"I'm not back." - Bill Harding, Twister
Sushil Sharma
Greenhorn

Joined: Nov 02, 2006
Posts: 22
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
Ranch Hand

Joined: Jun 26, 2002
Posts: 852
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)


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

Joined: Jun 26, 2002
Posts: 852
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
Ranch Hand

Joined: Jun 26, 2002
Posts: 852
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
Greenhorn

Joined: Feb 21, 2009
Posts: 14
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
Greenhorn

Joined: Mar 05, 2009
Posts: 7
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
Greenhorn

Joined: Feb 21, 2009
Posts: 14
I'd actually like to see your code so I could run the same tests.
Norman Larson
Greenhorn

Joined: Mar 05, 2009
Posts: 7
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
Greenhorn

Joined: Mar 05, 2009
Posts: 7
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)".


[Thumbnail for iterator_graph1.png]

Norman Larson
Greenhorn

Joined: Mar 05, 2009
Posts: 7
Dangit, forgot to attach the program.
Matt Elliott
Greenhorn

Joined: Feb 21, 2009
Posts: 14
Everyone seems to be doing large lists, does the size of the list matter?
Billy Tsai
Ranch Hand

Joined: May 23, 2003
Posts: 1297
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?


BEA 8.1 Certified Administrator, IBM Certified Solution Developer For XML 1.1 and Related Technologies, SCJP, SCWCD, SCBCD, SCDJWS, SCJD, SCEA,
Oracle Certified Master Java EE 5 Enterprise Architect
J Westland
Ranch Hand

Joined: Apr 06, 2009
Posts: 40
@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...


Woohoo passed SCJP 1.6, that's the theory exam passed now for the practice ;)
Tim Holloway
Saloon Keeper

Joined: Jun 25, 2001
Posts: 15661
    
  15

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.


Customer surveys are for companies who didn't pay proper attention to begin with.
Billy Tsai
Ranch Hand

Joined: May 23, 2003
Posts: 1297
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: is using ArrayList.iterator() is faster than looping ArrayList in for loop?
 
Similar Threads
LinkedList - Kathy Sierra
two ways of looping into a list
Iteration speed of Collections
List iteration
Arraylist Vs LinkedHashMap