I was wondering what has better performance when using ArrayList’s:
…make an ArrayList arT…
for (T : arT) {
…handle T
}
…make an ArrayList art…
Iterator it=arT.iterator();
while(it.hasNext()) {
…handle it.next()
}
for (int i=0;i<arT.size()-1;i++) {
…handle arT.get(i)
}
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.
for(int i=a.size()-1;i>=0;–i)
Is the quickest.
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
for (b : a){
... something
}
Is exactly the same as
for(int i=0;i<a.length;i++){
b = a[i];
... something
}
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).
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.
Is end to begin iteration faster than begin to end? Or why using size-1 as start and stepping i–?
I think the thinking is that testing a variable against zero is faster than testing against the array length.
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.
If you write it like this, it’s even a few keystrokes shorter ;D
for(int i=a.size();–i>=0;)
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:
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.
Needs to be…
for(int i=a.size()-1;i–>=0;)
tho 
Well, I rather use the clearer version with one extra keystroke.
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.
Nah, I think you’ll run into an ArrayIndexOutOfBoundsException (-1) with this one
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.
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.
That’s interesting, never heard about that.
[ starts googling ]
Nah, I think you’ll run into an ArrayIndexOutOfBoundsException (-1) with this one
Ooops :f
Must have done something stupid while beanshelling around.
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.
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 ;D
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.
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.
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.