for:each loops versus standard loops

[lhkbob]

I was wondering what has better performance when using ArrayList's:
1. A for:each loop, ie:

...make an ArrayList<T> arT...
for (T : arT) {
    ...handle T
}

2. Iterators, ie:

...make an ArrayList<T> art...
Iterator<T> it=arT.iterator();
while(it.hasNext()) {
    ...handle it.next()
}

3. Indexed acces (mind you this is for ArrayLists, not LinkedLists)

for (int i=0;i<arT.size()-1;i++) {
     ...handle arT.get(i)
}

[fletchergames]

The for each loop creates an iterator, so 1 and 2 should be the same.

Option 3 will be the fastest, though the loop index should stop at arT.size(), not arT.size() - 1.  Or you could change the < to <=, though taking out the - 1 would be the normal thing to do.

[oNyx]

for(int i=a.size()-1;i>=0;--i)

Is the quickest.

Games published by our own members! Check 'em out!

[Jeff]

For:each loops are purely syntactic sugar. They are translated to the appropriate code by the compiler, so
there is no functional difference between a foreach loop and its equivalent explicit construct.

eg.

if
int[] a;

then

1   2   3

for (b : a){        ... something    }

Is exactly the same as

1   2   3   4

for(int i=0;i<a.length;i++){      b = a[i];      ... something }

[Riven]

for primitive-arrays this is true, however:

for ArrayLists it's faster to use the 'normal-for', using the indices directly. The 'enhanced-for' allocates an Iterator and the overhead of the method-calls make it quite a bit slower (10-25% IIRC).

[lhkbob]

Thanks, you pretty much agreed with my thinking, but it's always nice to be sure that you're not crazy.
And thanks for the logic error, fletchergames, I was pretty tired when I posted.

[JAW]

for(int i=a.size()-1;i>=0;--i)

Is the quickest.

Is end to begin iteration faster than begin to end? Or why using size-1 as start and stepping i--?

[ryanm]

I think the thinking is that testing a variable against zero is faster than testing against the array length.

[oNyx]

Yea, it's a little bit quicker for that reason. It doesn't really make much of a difference, but it doesn't hurt either. It's only 3 keystrokes more. 3 extra keystrokes for a super tiny speed gain if the loop does very little (and basically none if the loop does something remotely complex). It's an acceptable trade imo.

It's one of the few micro optimizations, which are sorta alright in run of the mill code.

[erikd]

It's only 3 keystrokes more.

If you write it like this, it's even a few keystrokes shorter 
for(int i=a.size();--i>=0;)

Games published by our own members! Check 'em out!

[fletchergames]

for(int i=a.size()-1;i>=0;--i)

Is the quickest.

That probably means that the size method takes some time to execute (which should only be the case when the size method hasn't been inlined - unless there's some kind of assertion there).  Since subtraction is slightly slower than addition, the following might be even faster:

1   2

int sizeOfA = a.size(); for(int i = 0; i < sizeOfA; i++)

However, it might not be faster in all cases.  Addition is only slightly faster than subtraction, so it shouldn't make much of a difference.  If the extra variable causes some kind of cache thrashing (which is unlikely), it could actually be slower.

[oNyx]

Needs to be...

for(int i=a.size()-1;i-->=0;)

tho

Well, I rather use the clearer version with one extra keystroke.

[Abuse]

Isn't backward iteration over arrays bad for memory cache hits?
Though I've never seen it benchmarked, but i've certainly seen it discussed many times on forums.

Ignoring the above, the backward iteration would also be faster because comparison against zero is a single bytecode instruction, whereas comparison against a local variable, member variable or static variable requires 2 to 3 bytecodes.

[erikd]

Needs to be...

for(int i=a.size()-1;i-->=0;)

tho

Nah, I think you'll run into an ArrayIndexOutOfBoundsException (-1) with this one ;-)

Well, I rather use the clearer version with one extra keystroke.

Oh I agree.
Out of habit I usually even just write
for (int i = 0; i < a.size(); i++)
unless it's some tight inner loop where it matters.

That probably means that the size method takes some time to execute (which should only be the case when the size method hasn't been inlined

I don't think the size() method will be inlined, unless HotSpot will go through the code in the for loop and find out that the List isn't resized, re-instanciated, nulled and whatnot. I guess that at least the Client VM doesn't go that far in optimizing things like that.
And, as said above, another difference is the comparison against zero.

Isn't backward iteration over arrays bad for memory cache hits?
Though I've never seen it benchmarked, but i've certainly seen it discussed many times on forums.

That's interesting, never heard about that.
[ *starts googling* ]

[oNyx]

>Nah, I think you'll run into an ArrayIndexOutOfBoundsException (-1) with this one ;-)

Ooops :f

Must have done something stupid while beanshelling around.

[oNyx]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99

import java.util.ArrayList; public class AWalk{    int LIST_SIZE=4096;    int ITERATIONS=5000;    int REPEAT=20;    int AVG=REPEAT/2;    ArrayList a=new ArrayList(LIST_SIZE);    long []times=new long[4];    long []avg=new long[4];    public static void main(String[]args){       new AWalk();    }    public AWalk(){       for(int i=0;i<LIST_SIZE;i++)          a.add(new Integer(i));       for(int i=0;i<times.length;i++)          times[i]=Long.MAX_VALUE;       long start;       long stop;       long time;       for(int i=0;i<REPEAT;i++){          if(i==AVG)             for(int k=0;k<times.length;k++)                avg[k]=times[k];          start=System.nanoTime();          forward1();          stop=System.nanoTime();          time=stop-start;          avg[0]=(avg[0]*AVG+(time))/(AVG+1);          System.out.println("forward1 "+time/1000000000.0+"s");          if(time<times[0])             times[0]=time;          start=System.nanoTime();          forward2();          stop=System.nanoTime();          time=stop-start;          avg[1]=(avg[1]*AVG+(time))/(AVG+1);          System.out.println("forward2 "+time/1000000000.0+"s");          if(time<times[1])             times[1]=time;          start=System.nanoTime();          reverse1();          stop=System.nanoTime();          time=stop-start;          avg[2]=(avg[2]*AVG+(time))/(AVG+1);          System.out.println("reverse1 "+time/1000000000.0+"s");          if(time<times[2])             times[2]=time;          start=System.nanoTime();          reverse2();          stop=System.nanoTime();          time=stop-start;          avg[3]=(avg[3]*AVG+(time))/(AVG+1);          System.out.println("reverse2 "+time/1000000000.0+"s");          if(time<times[3])             times[3]=time;       }       String []labels={          "[forward1] for(int i=0;i<a.size();i++)",          "[forward2] int size=a.size();for(int i=0;i<size;i++)",          "[reverse1] for(int i=a.size()-1;i>=0;--i)",          "[reverse2] for(int i=a.size();--i>=0;)"       };       for(int i=0;i<times.length;i++){          System.out.println(labels[i]);          System.out.println("best:"+times[i]/1000000000.0+"s");          System.out.println("avg :"+avg[i]/1000000000.0+"s");       }    }    public void forward1(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=0;i<a.size();i++)             sum+=((Integer)a.get(i)).intValue();    }    public void forward2(){       int sum=0;       int size=a.size();       for(int x=0;x<ITERATIONS;x++)          for(int i=0;i<size;i++)             sum+=((Integer)a.get(i)).intValue();    }    public void reverse1(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=a.size()-1;i>=0;--i)             sum+=((Integer)a.get(i)).intValue();    }    public void reverse2(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=a.size();--i>=0;)             sum+=((Integer)a.get(i)).intValue();    } }

Ah hum...

forward2 is surprisingly slower then forward1. reverse1 is the best and reverse2 is about the same, but a little bit slower most of the time.

Oh and I forgot... the main reason to go backwards over ArrayLists is that it allows you to remove elements as you go.

edit: now that no background shizzle is running anymore. reverse2 appears to be slightly faster.

[erikd]

interesting, although I'm not sure what to conclude here. 
I think I'll stick with forward1 for clarity until my profiler tells me that fame, money and babes await me with reverse1   

[oNyx]

I use reverse1 out of habit with ArrayLists and forward1 with Bag. Removing stuff would be quite the pain if you travel the other way around anyways.

Well, I also use forward1 for ArrayLists occasionally... if I cant be arsed.

[Abuse]

Did you try changing around the order of the tests, so the reverse iterations are done first?

I bet it has an effect on the results.

[erikd]

If it has an effect, I bet reverse iterations are still a tiny bit faster. That's my own experience anyway.

However, the difference is usually so small that it will soon fall below noise level in the big picture, except maybe in some corner cases and even then don't expect much.

[broumbroum]

I 'd strongly recommend for List or Map instances to Iterate on them if you intend to bring up more as one single Thread on it. Then for:each loop is obviously the only way  to make it on running while you mustn't forget about synchronizing all that stuff. Javadoc manner provides a synchronized view of every sort of Array from the Collections static class. See:

1   2   3   4   5

Map<Integer, Object> smap = Collections.synchronizedMap(new HasMap<Integer, Object>()); synchronized(smap) {      for(Iterator<Integer> i = smap.keySet().iterator(); i.hasNext())              doSomeActionOnTheValue(smap.get(i.next())); }

This will run as fast as if you had one Object[] array to initialize and to get activity running on it. The obvious advantage with Maps or List or Set, globally Collections, is to have a scaleable amount of values to work on.

[cylab]

@broumbroum
I think you missed the point, that this is a performance discussion... 

This will run as fast as if you had one Object[] array to initialize and to get activity running on it.

either I don't get it due to language barrier or this statement is a plain lie

[broumbroum]

I assume you don't even have ever tried it, but it is true that this is the fastest way to get out of for and foreach loops with big amount of objects. 

[Riven]

bullshit plain lie

Collections are slower to iterate - especially in a for-each (simply because doing it yourself removes the overhead of the Iterator)

[cylab]

I assume you don't even have ever tried it, but it is true that this is the fastest way to get out of for and foreach loops with big amount of objects. 

So did you?

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31

[forward1] for(int i=0;i<a.size();i++) best:0.401326985s avg :0.424093174s [forward2] int size=a.size();for(int i=0;i<size;i++) best:0.37795893s avg :0.401431877s [reverse1] for(int i=a.size()-1;i>=0;--i) best:0.369816555s avg :0.389192799s [reverse2] for(int i=a.size();--i>=0;) best:0.361338383s avg :0.390844695s [iterate]  for(Iterator i=a.iterator();i.hasNext();) best:1.039801428s avg :1.116375577s [foreach]  for(Integer s: a) best:1.087047935s avg :1.138143202s [synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call best:1.050037086s avg :1.143322395s [synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration) best:1.088886716s avg :1.14673606s

Testcase:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172   173   174

public class IterationTester {    int LIST_SIZE=4096;    int ITERATIONS=5000;    int REPEAT=20;    int AVG=REPEAT/2;    ArrayList<Integer> a=new ArrayList(LIST_SIZE);    long []times=new long[8];    long []avg=new long[8];    public static void main(String[]args){       new IterationTester();    }    public IterationTester(){       for(int i=0;i<LIST_SIZE;i++)          a.add(new Integer(i));       for(int i=0;i<times.length;i++)          times[i]=Long.MAX_VALUE;       long start;       long stop;       long time;       for(int i=0;i<REPEAT;i++){          if(i==AVG)             for(int k=0;k<times.length;k++)                avg[k]=times[k];          start=System.nanoTime();          forward1();          stop=System.nanoTime();          time=stop-start;          avg[0]=(avg[0]*AVG+(time))/(AVG+1);          System.out.println("forward1 "+time/1000000000.0+"s");          if(time<times[0])             times[0]=time;          start=System.nanoTime();          forward2();          stop=System.nanoTime();          time=stop-start;          avg[1]=(avg[1]*AVG+(time))/(AVG+1);          System.out.println("forward2 "+time/1000000000.0+"s");          if(time<times[1])             times[1]=time;          start=System.nanoTime();          reverse1();          stop=System.nanoTime();          time=stop-start;          avg[2]=(avg[2]*AVG+(time))/(AVG+1);          System.out.println("reverse1 "+time/1000000000.0+"s");          if(time<times[2])             times[2]=time;          start=System.nanoTime();          reverse2();          stop=System.nanoTime();          time=stop-start;          avg[3]=(avg[3]*AVG+(time))/(AVG+1);          System.out.println("reverse2 "+time/1000000000.0+"s");          if(time<times[3])             times[3]=time;          start=System.nanoTime();          iterate();          stop=System.nanoTime();          time=stop-start;          avg[4]=(avg[4]*AVG+(time))/(AVG+1);          System.out.println("iterate "+time/1000000000.0+"s");          if(time<times[4])             times[4]=time;          start=System.nanoTime();          foreach();          stop=System.nanoTime();          time=stop-start;          avg[5]=(avg[5]*AVG+(time))/(AVG+1);          System.out.println("foreach "+time/1000000000.0+"s");          if(time<times[5])             times[5]=time;          start=System.nanoTime();          synchro1();          stop=System.nanoTime();          time=stop-start;          avg[6]=(avg[6]*AVG+(time))/(AVG+1);          System.out.println("synchro1 "+time/1000000000.0+"s");          if(time<times[6])             times[6]=time;          start=System.nanoTime();          syncro2();          stop=System.nanoTime();          time=stop-start;          avg[7]=(avg[7]*AVG+(time))/(AVG+1);          System.out.println("synchro2 "+time/1000000000.0+"s");          if(time<times[7])             times[7]=time;       }       String []labels={          "[forward1] for(int i=0;i<a.size();i++)",          "[forward2] int size=a.size();for(int i=0;i<size;i++)",          "[reverse1] for(int i=a.size()-1;i>=0;--i)",          "[reverse2] for(int i=a.size();--i>=0;)",          "[iterate]  for(Iterator i=a.iterator();i.hasNext();)",          "[foreach]  for(Integer s: a)",          "[synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call",          "[synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration)"       };       for(int i=0;i<times.length;i++){          System.out.println(labels[i]);          System.out.println("best:"+times[i]/1000000000.0+"s");          System.out.println("avg :"+avg[i]/1000000000.0+"s");          System.out.println();       }    }    public void forward1(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=0;i<a.size();i++)             sum+=((Integer)a.get(i)).intValue();    }    public void forward2(){       int sum=0;       int size=a.size();       for(int x=0;x<ITERATIONS;x++)          for(int i=0;i<size;i++)             sum+=((Integer)a.get(i)).intValue();    }    public void reverse1(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=a.size()-1;i>=0;--i)             sum+=((Integer)a.get(i)).intValue();    }    public void reverse2(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(int i=a.size();--i>=0;)             sum+=((Integer)a.get(i)).intValue();    }    public void iterate(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(Iterator i=a.iterator();i.hasNext();)             sum+=((Integer)i.next()).intValue();    }    public void foreach(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)          for(Integer s: a)             sum+=s.intValue();    }    public void synchro1(){       int sum=0;       for(int x=0;x<ITERATIONS;x++)       {          List<Integer> sa = Collections.synchronizedList(a);          synchronized(sa) {                 for(Iterator<Integer> i = sa.iterator(); i.hasNext();)                    sum+=((Integer)i.next()).intValue();          }       }    }    public void syncro2(){       int sum=0;       List<Integer> sa = Collections.synchronizedList(a);       for(int x=0;x<ITERATIONS;x++)       {          synchronized(sa) {             for(Iterator<Integer> i = sa.iterator(); i.hasNext();)                sum+=((Integer)i.next()).intValue();          }       }    } }

It's quite brazen to accuse someone not doing his homework right, if you didn't yourself

[broumbroum]

thank you for this test, I did my own for my own apps.

[cylab]

care to post it here and back up your statements?

[bienator]

my results:
java 6 client

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31

[forward1] for(int i=0;i<a.size();i++) best:0.236861869s avg :0.237710407s [forward2] int size=a.size();for(int i=0;i<size;i++) best:0.243388188s avg :0.245275719s [reverse1] for(int i=a.size()-1;i>=0;--i) best:0.234105232s avg :0.236468176s [reverse2] for(int i=a.size();--i>=0;) best:0.234173636s avg :0.23560745s [iterate]  for(Iterator i=a.iterator();i.hasNext();) best:1.001008995s avg :1.002553588s [foreach]  for(Integer s: a) best:1.001137343s avg :1.002832611s [synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call best:1.047498371s avg :1.050345237s [synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration) best:1.026651229s avg :1.034549709s

java 7b12 client

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31

[forward1] for(int i=0;i<a.size();i++) best:0.098598338s avg :0.099309703s [forward2] int size=a.size();for(int i=0;i<size;i++) best:0.086764429s avg :0.087365481s [reverse1] for(int i=a.size()-1;i>=0;--i) best:0.086961825s avg :0.087888956s [reverse2] for(int i=a.size();--i>=0;) best:0.087148515s avg :0.087648407s [iterate]  for(Iterator i=a.iterator();i.hasNext();) best:0.902982435s avg :0.9046512s [foreach]  for(Integer s: a) best:0.901919269s avg :0.904204496s [synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call best:0.88929315s avg :0.898148557s [synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration) best:0.887476421s avg :0.901809679s

java 6 server

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31

[forward1] for(int i=0;i<a.size();i++) best:0.047897427s avg :0.04833437s [forward2] int size=a.size();for(int i=0;i<size;i++) best:0.047876021s avg :0.048443501s [reverse1] for(int i=a.size()-1;i>=0;--i) best:0.050514161s avg :0.051226223s [reverse2] for(int i=a.size();--i>=0;) best:0.050541038s avg :0.051425828s [iterate]  for(Iterator i=a.iterator();i.hasNext();) best:0.170091701s avg :0.171224648s [foreach]  for(Integer s: a) best:0.17041104s avg :0.171149453s [synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call best:0.170544356s avg :0.171396083s [synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration) best:0.169996068s avg :0.17115992s

java 7b12 server (tiered compiler)

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31

[forward1] for(int i=0;i<a.size();i++) best:0.046119653s avg :0.046703256s [forward2] int size=a.size();for(int i=0;i<size;i++) best:0.046233412s avg :0.046704791s [reverse1] for(int i=a.size()-1;i>=0;--i) best:0.048204308s avg :0.048780098s [reverse2] for(int i=a.size();--i>=0;) best:0.048143243s avg :0.048854144s [iterate]  for(Iterator i=a.iterator();i.hasNext();) best:0.078269895s avg :0.07890705s [foreach]  for(Integer s: a) best:0.078561754s avg :0.079460743s [synchro1] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // one synchronizedList() call best:0.074725515s avg :0.076259373s [synchro2] for(Iterator<Integer> i = sa.iterator(); i.hasNext();) // multiple synchronizedList() calls (one per test iteration) best:0.079357871s avg :0.080087159s

CPU: Core2Duo;  64bit winXP; 32bit VMs

I did the test primary because I was curious how the tiered compiler performs compared to the old server VM.

Because i always use the server VM for my 3D stuff, i will use the plain old for loop (for(int i=0;i<a.size();i++) )in future too. But the really interesting part of this benchmark:
-the 7 client VM solves the for loop 2x faster then the 6
-the new tiered VM is even a little bit faster then the old server VM

[Mr_Light]

  thats looking pritty sharp