Is there a performance difference between a for loop and a for-each loop?

Question

What, if any, is the performance difference between the following two loops?

for (Object o: objectArrayList) {
    o.DoSomething();
}

and

for (int i=0; i<objectArrayList.size(); i++) {
    objectArrayList.get(i).DoSomething();
}

Whither

@Keparo: It is a "for each" loop not a "for-in" loop – Lee

in java its called "for each", but when it come to Objective C its called "for In" loop. – Argentina

Also see: docs.oracle.com/javase/8/docs/api/java/util/RandomAccess.html – Cullum

The extended for loop performance is discussed here: #12156487 – Ternion

Even if there would be a difference, it would be so minor that you should favor readability unless this piece of code is executed trillions of times per second. And then you would need a proper benchmark to avoid premature optimization anyways. – Manvil

Answer 1

From Item 46 in Effective Java by Joshua Bloch :

The for-each loop, introduced in release 1.5, gets rid of the clutter and the opportunity for error by hiding the iterator or index variable completely. The resulting idiom applies equally to collections and arrays:

// The preferred idiom for iterating over collections and arrays
for (Element e : elements) {
    doSomething(e);
}

When you see the colon (:), read it as “in.” Thus, the loop above reads as “for each element e in elements.” Note that there is no performance penalty for using the for-each loop, even for arrays. In fact, it may offer a slight performance advantage over an ordinary for loop in some circumstances, as it computes the limit of the array index only once. While you can do this by hand (Item 45), programmers don’t always do so.

Calumny

Worth mentioning that in a for-each loop there is no way to access an index counter (since it doesn't exist) – Dialogue

Yes, but that counter is now visible outside of the loop. Sure, it's a simple fix but so is for-each! – Novikoff

There is the performance penalty of allocating the iterator. I had some highly parallel code in an Android live wallpaper. I saw that the garbage collector was going crazy. It was because for-each loops were allocating temporary iterators in many different (short-lived) threads, cause the garbage collector a lot of work. Switching to regular index based loops fixed the problem. – Amplexicaul

@gsingh2011 But this also depends on if you're using a random access list or not. Using index based access to non-random access lists will be a lot worse than using for-each with random access lists, I guess. If you're working with the interface List and thus don't know the actual implementation type you can check if the list is an instance of (implements) RandomAccess, if you really care that much: docs.oracle.com/javase/8/docs/api/java/util/RandomAccess.html – Cullum

@gsingh2011 The Android docs (developer.android.com/training/articles/perf-tips.html#Loops) mention that you'll have a performance penalty when using foreach over an ArrayList only, not other collections. I'm curious whether that was your case. – Hereof

@Hereof No, this is different. This is purely the allocation/deallocation cost that is required when you use a foreach loop to create an Iterator object, it's not related to the iteration itself. In most code it's something you don't have to worry about. If it's in the hot path of your code, it could cause performance issues, like it did for me. – Amplexicaul

@Dialogue you always have access to the index with indexOf() no? – Superdreadnought

@Hereof +1 for mentioning the case of ArrayList. I also read that for an ArrayList the traditional for loop is 3x faster when compared to for each loop. – Sebrinasebum

As Viccari pointed out this is not true for ArrayList and it is a DS that most developers use on a day to day basis. – Sebrinasebum

Hard to believe Bloch gives such misleading advice; I hope this has been fixed, or will be fixed, in future versions. In particular, the statement "there is no performance penalty for using the for-each loop" is simply wrong, as pointed out by @Hereof and others. – Kaddish

Answer 2

All these loops do the exact same, I just want to show these before throwing in my two cents.

First, the classic way of looping through List:

for (int i=0; i < strings.size(); i++) { /* do something using strings.get(i) */ }

Second, the preferred way since it's less error prone (how many times have YOU done the "oops, mixed the variables i and j in these loops within loops" thing?).

for (String s : strings) { /* do something using s */ }

Third, the micro-optimized for loop:

int size = strings.size();
for (int i = -1; ++i < size;) { /* do something using strings.get(i) */ }

Now the actual two cents: At least when I was testing these, the third one was the fastest when counting milliseconds on how long it took for each type of loop with a simple operation in it repeated a few million times - this was using Java 5 with jre1.6u10 on Windows in case anyone is interested.

While it at least seems to be so that the third one is the fastest, you really should ask yourself if you want to take the risk of implementing this peephole optimization everywhere in your looping code since from what I've seen, actual looping isn't usually the most time consuming part of any real program (or maybe I'm just working on the wrong field, who knows). And also like I mentioned in the pretext for the Java for-each loop (some refer to it as Iterator loop and others as for-in loop) you are less likely to hit that one particular stupid bug when using it. And before debating how this even can even be faster than the other ones, remember that javac doesn't optimize bytecode at all (well, nearly at all anyway), it just compiles it.

If you're into micro-optimization though and/or your software uses lots of recursive loops and such then you may be interested in the third loop type. Just remember to benchmark your software well both before and after changing the for loops you have to this odd, micro-optimized one.

Plaza

Please note that the for loop with ++i<=size is "1-based", e.g. the get-method inside the loop will be called for values 1, 2, 3, etc. – Barbusse

A better way to write the micro-optimized loop is for(int i=0, size=strings.size();++i<=size;) {} This is preferable because it minimizes the scope of size – Sandisandidge

doesn't the third one start from i=1 on first time it goes through the loop, skipping first element. and it being a for loop is unnecessary. int n=strings.length; while(n-->0) { System.out.println(" "+n+" "+strings[n]); } – Electronic

@Dónal that loop pattern misses the first one and gives an IOOBE. This one works: for (int i = -1, size = list.size(); ++i < size;) – Centralization

"All these loops do the exact same" is incorrect. One uses random access get(int), the other uses an Iterator. Consider LinkedList where the performance of for(int i=0;i<strings.size();i++) { /* do something using strings.get(i) */ } is far worse since it's doing a get(int) n times. – Leigha

Answer 3

The for-each loop should generally be preferred. The "get" approach may be slower if the List implementation you are using does not support random access. For example, if a LinkedList is used, you would incur a traversal cost, whereas the for-each approach uses an iterator that keeps track of its position in the list. More information on the nuances of the for-each loop.

I think the article is now here: new location

The link shown here was dead.

Atterbury

Answer 4

Well, performance impact is mostly insignificant, but isn't zero. If you look at JavaDoc of RandomAccess interface:

As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)
    list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext();)
      i.next();

And for-each loop is using version with iterator, so for ArrayList for example, for-each loop isn't fastest.

Unassailable

Really each? Even one with an array? I read here #1006895 that it doesn't involve an iterator. – Meatiness

@OndraŽižka: The for-each loop uses iterators when looping over Iterables, but not arrays. For arrays a for-loop with an index variable is used. There is information about this in the JLS. – Balkanize

yeah so you would first need to create it into an array with toArray, having a cost. – Electronic

Answer 5

There appears to be a difference unfortunately.

If you look at the generated bytes code for both kinds of loops, they are different.

Here is an example from the Log4j source code.

In /log4j-api/src/main/java/org/apache/logging/log4j/MarkerManager.java we have a static inner class called Log4jMarker which defines:

    /*
     * Called from add while synchronized.
     */
    private static boolean contains(final Marker parent, final Marker... localParents) {
        //noinspection ForLoopReplaceableByForEach
        for (final Marker marker : localParents) {
            if (marker == parent) {
                return true;
            }
        }
        return false;
    }

With standard loop:

  private static boolean contains(org.apache.logging.log4j.Marker, org.apache.logging.log4j.Marker...);
    Code:
       0: iconst_0
       1: istore_2
       2: aload_1
       3: arraylength
       4: istore_3
       5: iload_2
       6: iload_3
       7: if_icmpge     29
      10: aload_1
      11: iload_2
      12: aaload
      13: astore        4
      15: aload         4
      17: aload_0
      18: if_acmpne     23
      21: iconst_1
      22: ireturn
      23: iinc          2, 1
      26: goto          5
      29: iconst_0
      30: ireturn

With for-each:

  private static boolean contains(org.apache.logging.log4j.Marker, org.apache.logging.log4j.Marker...);
    Code:
       0: aload_1
       1: astore_2
       2: aload_2
       3: arraylength
       4: istore_3
       5: iconst_0
       6: istore        4
       8: iload         4
      10: iload_3
      11: if_icmpge     34
      14: aload_2
      15: iload         4
      17: aaload
      18: astore        5
      20: aload         5
      22: aload_0
      23: if_acmpne     28
      26: iconst_1
      27: ireturn
      28: iinc          4, 1
      31: goto          8
      34: iconst_0
      35: ireturn

What is up with THAT Oracle?

I've tried this with Java 7 and 8 on Windows 7.

Befriend

For those who are trying to read the disassembly, the net result is that the code generated inside the loop is identical, but the for-each setup seems to have created an extra temporary variable containing a reference to the second argument. If the extra hidden variable is enregistered, but the parameter itself is not during code generation, then the for-each would be faster; if the parameter is enregistered in the for(;;) example, execution time would be identical. Gotta benchmark? – Trapan

Answer 6

foreach makes the intention of your code clearer and that is normally preferred over a very minor speed improvement - if any.

Whenever I see an indexed loop I have to parse it a little longer to make sure it does what I think it does E.g. Does it start from zero, does it include or exclude the end point etc.?

Most of my time seems to be spent reading code (that I wrote or someone else wrote) and clarity is almost always more important than performance. Its easy to dismiss performance these days because Hotspot does such an amazing job.

Palermo

Answer 7

The following code:

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

interface Function<T> {
    long perform(T parameter, long x);
}

class MyArray<T> {

    T[] array;
    long x;

    public MyArray(int size, Class<T> type, long x) {
        array = (T[]) Array.newInstance(type, size);
        this.x = x;
    }

    public void forEach(Function<T> function) {
        for (T element : array) {
            x = function.perform(element, x);
        }
    }
}

class Compute {
    int factor;
    final long constant;

    public Compute(int factor, long constant) {
        this.factor = factor;
        this.constant = constant;
    }

    public long compute(long parameter, long x) {
        return x * factor + parameter + constant;
    }
}

public class Main {

    public static void main(String[] args) {
        List<Long> numbers = new ArrayList<Long>(50000000);
        for (int i = 0; i < 50000000; i++) {
            numbers.add(i * i + 5L);
        }

        long x = 234553523525L;

        long time = System.currentTimeMillis();
        for (int i = 0; i < numbers.size(); i++) {
            x += x * 7 + numbers.get(i) + 3;
        }
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(x);
        x = 0;
        time = System.currentTimeMillis();
        for (long i : numbers) {
            x += x * 7 + i + 3;
        }
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(x);
        x = 0;
        numbers = null;
        MyArray<Long> myArray = new MyArray<Long>(50000000, Long.class, 234553523525L);
        for (int i = 0; i < 50000000; i++) {
            myArray.array[i] = i * i + 3L;
        }
        time = System.currentTimeMillis();
        myArray.forEach(new Function<Long>() {

            public long perform(Long parameter, long x) {
                return x * 8 + parameter + 5L;
            }
        });
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(myArray.x);
        myArray = null;
        myArray = new MyArray<Long>(50000000, Long.class, 234553523525L);
        for (int i = 0; i < 50000000; i++) {
            myArray.array[i] = i * i + 3L;
        }
        time = System.currentTimeMillis();
        myArray.forEach(new Function<Long>() {

            public long perform(Long parameter, long x) {
                return new Compute(8, 5).compute(parameter, x);
            }
        });
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(myArray.x);
    }
}

Gives following output on my system:

224
-699150247503735895
221
-699150247503735895
220
-699150247503735895
219
-699150247503735895

I'm running Ubuntu 12.10 alpha with OracleJDK 1.7 update 6.

In general HotSpot optimizes a lot of indirections and simple reduntant operations, so in general you shouldn't worry about them unless there are a lot of them in seqence or they are heavily nested.

On the other hand, indexed get on LinkedList is much slower than calling next on iterator for LinkedList so you can avoid that performance hit while retaining readability when you use iterators (explicitly or implicitly in for-each loop).

Hernando

Answer 8

Here is a brief analysis of the difference put out by the Android development team:

https://www.youtube.com/watch?v=MZOf3pOAM6A

The result is that there is a difference, and in very restrained environments with very large lists it could be a noticeable difference. In their testing, the for each loop took twice as long. However, their testing was over an arraylist of 400,000 integers. The actual difference per element in the array was 6 microseconds. I haven't tested and they didn't say, but I would expect the difference to be slightly larger using objects rather than primitives, but even still unless you are building library code where you have no idea the scale of what you will be asked to iterate over, I think the difference is not worth stressing about.

Hood

Answer 9

Seems to me like the other answers are based on the incorrect benchmarks, that doesn't take Hotspot's compilation and optimization process into an account.

Short answer

Use enhanced-loop when possible, because most of the time it's the fastest. If you cannot, pull the entire array into a local variable if possible:

int localArray = this.array;
for (int i = 0; i < localArray.length; i++) { 
    methodCall(localArray[i]); 
}

Long answer

Now, usually there is no difference, because Hotspot is very good at optimizing and getting rid of checks that java needs to do.

But sometimes some optimizations just cannot be done, usually because you have a virtual call inside a loop, that cannot be inlined. In that case, some loops can really be faster than others.

Few of the things that Java needs to do:

• reload this.array - because it could be changed (by the call or another thread)
• check whether i is in inside the bounds of the array, if not throw IndexOutOfBoundsException
• check whether an accessed object reference is null, if yes throw NullPointerException

Consider this c-style loop:

for (int i = 0; i < this.array.length; i++) { //now java knows i < this.array.length
    methodCall(this.array[i]);// no need to check
}

By evaluating the loop condition i < this.array.length, java knows that i must be inside of bounds (i is changed only after the call), so don't need to check it again in the next line. But in this case java needs to reload this.array.length.

You might be tempted to "optimize" the loop, by pulling the this.array.length value inside of the local variable:

int len = this.array.length;//len is now a local variable
for (int i = 0; i < len; i++) { //no reload needed
    methodCall(this.array[i]); //now java will do the check
}

Now java don't need to reload every single time, because a local variable can be cannot be changed by the methodCall and/or another thread. Local variables can be changed only inside the method itself, and java now can prove that variable len could not change.

But now the loop condition i < this.array.length changed to i < len, and previous optimization fails, and java need to check whether the i in inside of bounds of this.array.

A better optimization would be to pull entire array into a local variable:

ArrayType[] localArray = this.array;
for (int i = 0; i < localArray.length; i++) { 
    methodCall(localArray[i]); 
}

Now java don't need to reload the array, and the "i in bounds" check is also eliminated.

And what about the enhanced-loop? Well, usually the compiler rewrites your enhanced loop into something like the last shown loop, if not even better.

Swale

So, with the arrays of use for loop will be faster and bring better performance for each loop? – Yatzeck

@TầnQuảng I do not exactly know what do you mean. Expand your question, perhaps post some code. – Swale

short answer and long answer last optimization code "int localArray = this.array;" should not be int type. The most important thing I want to know is if the ArrayList localArray = this.array will use a dummy size memory. I dont know it is copying a new array or just a reference. – Brazenfaced

@Brazenfaced yes, the type was wrong; with ArrayList localArray = this.array, you just copy a reference, no additional memory allocation is done, except creating one object reference on the stack, so basically no overhead. – Swale

Answer 10

The only way to know for sure is to benchmark it, and even that is not as simple as it may sound. The JIT compiler can do very unexpected things to your code.

Terrain

Answer 11

Even with something like an ArrayList or Vector, where "get" is a simple array lookup, the second loop still has additional overhead that the first one doesn't. I would expect it to be a tiny bit slower than the first.

Conchiferous

The first loop has to get each element too. It creates an iterator behind the scenes to do this. They're really equivalent. – Sudd

Thinking in terms of C, an iterator can just increment a pointer, but a get would have to multiply the value of i by the width of a pointer each time. – Conchiferous

It depends on what type of list you use. I think you're right though, using get would never be faster, and sometimes slower. – Sudd

Answer 12

By the variable name objectArrayList, I assume that is an instance of java.util.ArrayList. In that case, the performance difference would be unnoticeable.

On the other hand, if it's an instance of java.util.LinkedList, the second approach will be much slower as the List#get(int) is an O(n) operation.

So the first approach is always preferred unless the index is needed by the logic in the loop.

Tour

Answer 13

It's weird that no one has mentioned the obvious - foreach allocates memory (in the form of an iterator), whereas a normal for loop does not allocate any memory. For games on Android, this is a problem, because it means that the garbage collector will run periodically. In a game you don't want the garbage collector to run... EVER. So don't use foreach loops in your draw (or render) method.

Equites

But don't forget about collections that does not create a new iterator ever time. – Swale

@JerryLundegaard Fair, but if you don't know what those are off the top of your head, which I don't, it may just be easier to just use a for loop in a game, rather than decompiling your program to see which calls new and which doesn't (or relying on docs... who knows how accurate they are?). If you're already using object pools and other techniques to avoid calling new... it just makes sense to use for loops and avoid the issue. Of course a memory profiler is the final arbiter of GC issues. – Equites

Answer 14

It's always better to use the iterator instead of indexing. This is because iterator is most likely optimzied for the List implementation while indexed (calling get) might not be. For example LinkedList is a List but indexing through its elements will be slower than iterating using the iterator.

Leigha

I think there is no such thing as "always" in performance optimizations .) – Ternion

I think you'll need to define better here. If we're talking about performance (which is the point of the question), then it's just wrong to say always here. Iterator-based loops are slower than indexed loops for RandomAccess lists. Note that this includes ArrayList, which is one of the most used data structures in Java. Most of the time, the performance difference matters less than the readability of the loop, but the penalty is here if it's in your hot path, so when asked the question about performance, this answer is really misleading. – Mussulman

Answer 15

1. for(Object o: objectArrayList){
    o.DoSomthing();
}
and

2. for(int i=0; i<objectArrayList.size(); i++){
    objectArrayList.get(i).DoSomthing();
}

Both does the same but for easy and safe programming use for-each, there are possibilities for error prone in 2nd way of using.

Jd

Answer 16

Accepted answer answers the question, apart from the exceptional case of ArrayList...

Since most developers rely on ArrayList(atleast I believe so)

So I am obligated to add the correct answer here.

Straight from the developer documentation:-

The enhanced for loop (also sometimes known as "for-each" loop) can be used for collections that implement the Iterable interface and for arrays. With collections, an iterator is allocated to make interface calls to hasNext() and next(). With an ArrayList, a hand-written counted loop is about 3x faster (with or without JIT), but for other collections the enhanced for loop syntax will be exactly equivalent to explicit iterator usage.

There are several alternatives for iterating through an array:

static class Foo {
    int mSplat;
}

Foo[] mArray = ...

public void zero() {
    int sum = 0;
    for (int i = 0; i < mArray.length; ++i) {
        sum += mArray[i].mSplat;
    }
}

public void one() {
    int sum = 0;
    Foo[] localArray = mArray;
    int len = localArray.length;

    for (int i = 0; i < len; ++i) {
        sum += localArray[i].mSplat;
    }
}

public void two() {
    int sum = 0;
    for (Foo a : mArray) {
        sum += a.mSplat;
    }
}

zero() is slowest, because the JIT can't yet optimize away the cost of getting the array length once for every iteration through the loop.

one() is faster. It pulls everything out into local variables, avoiding the lookups. Only the array length offers a performance benefit.

two() is fastest for devices without a JIT, and indistinguishable from one() for devices with a JIT. It uses the enhanced for loop syntax introduced in version 1.5 of the Java programming language.

So, you should use the enhanced for loop by default, but consider a hand-written counted loop for performance-critical ArrayList iteration.

Sebrinasebum

The documentation you're referring to is actually a performance guide for android deveopers (link), which only applies to jvm that runs on android, and seems out of date anyway. – Swale