Java – Reverse loop versus Forward loop in Performance
Node
This article is using the
This article is using the
endTime - startTime
method to measure the performance of a loop, it ignores the JVM warm up optimization, the result may not consistent or accurately.
A better way is using the OpenJDK JMH framework to do the benchmark testing, because it will take care of the JVM warm up concerns automatically, see this example – JMH – Forward loop vs Reverse loop
A Java performance test for Forward loop vs Reverse loop for a List, which one is faster?
Forward loop
for (int i = 0; i < aList.size(); i++) {
String s = aList.get(i);
}
Reverse loop
for (int i = aList.size() - 1; i >= 0; i--) {
String s = aList.get(i);
}
1. Forward loop versus Reverse loop
LoopForwardReverseTest.java
package com.mkyong.benchmark.bk;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
public class LoopForwardReverseTest {
private static List<String> DATA_FOR_TESTING = Arrays.asList(createArray());
public static void main(String[] argv) {
LoopForwardReverseTest obj = new LoopForwardReverseTest();
obj.forwardLoop();
obj.reverseLoop();
}
public void forwardLoop() {
System.out.println("\n--------- Forward Loop -------\n");
long startTime = new Date().getTime();
for (int i = 0; i < DATA_FOR_TESTING.size(); i++) {
String s = DATA_FOR_TESTING.get(i);
//System.out.println(s);
}
long endTime = new Date().getTime();
long difference = endTime - startTime;
System.out.println("Forward Loop - Elapsed time in milliseconds: " + difference);
}
public void reverseLoop() {
System.out.println("\n--------- Reverse Loop -------\n");
long startTime = new Date().getTime();
for (int i = DATA_FOR_TESTING.size() - 1; i >= 0; i--) {
String s = DATA_FOR_TESTING.get(i);
//System.out.println(s);
}
long endTime = new Date().getTime();
long difference = endTime - startTime;
System.out.println("Reverse Loop - Elapsed time in milliseconds: " + difference);
}
private static String[] createArray() {
int N = 10_000_000;
String sArray[] = new String[N];
for (int i = 0; i < N; i++) {
sArray[i] = "Array " + i;
}
return sArray;
}
}
Result
--------- Forward Loop -------
Forward Loop - Elapsed time in milliseconds: 64
--------- Reverse Loop -------
Reverse Loop - Elapsed time in milliseconds: 49
This is a completely invalid comparison – not only do you leave out the first element with the reverse loop, but you completely base your results on a single test – which can be extremely unreliable data. I’d suggest that you attempt running this test at least 100 times and average the data (after fixing the unbalanced reverse code), and it’ll be easy to see that this is a invalid experiment.
Yes, thanks for your suggestion, a better way should be used JMH to perform the test, review the following example :
https://mkyong.com/java/jmh-java-forward-loop-vs-reverse-loop/
Your reverse loop has a bug. It never loops through the first element:
for (int i=iListSize-1; i > 0; i–){
String stemp = (String)lList.get(i);
}
must be
for (int i=iListSize-1; i >= 0; i–){
String stemp = (String)lList.get(i);
}
Regards…
Thanks for correcting me, article is updated.
How many times did you execute the same experiment? I mean, how many times did you run 1 million, how many times did you run 5 millions, and so forth?
It seems you executed only 1 time each set. If you did that, please, take a look at:
http://en.wikipedia.org/wiki/Confidence_interval
So, for each set you need to run 35 times and then calculate the confidence interval.
Why should you do that? Because there are variables than can influence your result, like other processes running on your processor, etc.
And please, show on your graphics the name regardind to x-axis. People should see your graphic and understand what you’re showing on it without read the explanation. =)
Best regards,
Urlan
Sorry, my test ignored the JVM warm up, a better way should be used JMH to perform the test :
https://mkyong.com/java/jmh-java-forward-loop-vs-reverse-loop/
obviously you’re calling lList.size()…
foward) … every iteration
backward) … only once
try something like:
for (int i=0, max=lList.size(); i<max; i++)
Wow, incredible blog structure! How long have you ever been running a blog for? you made blogging look easy. The total glance of your site is great, let alone the content!
This is totally wrong
If you correct the mistake pointed out by Flix, the forward loop is faster then reverse.
public class Example1 {
public static void main(String[] args) {
long time = System.nanoTime();
for(int i = 100000; i > 0; i–) {}
long time1 = System.nanoTime();
System.out.println(“first loop time:”+(time1-time));
time = System.nanoTime();
for(int i = 1; i < 100001; i++) {}
time1 = System.nanoTime();
System.out.println("second loop time:"+(time1-time));
}
}
Run this. you understand forward loop is better than reverse loop.
this test shows faster reverse time than forward time:
first loop time:1452666
second loop time:2095571
OK but when the loop size is increased, the fwd loop wins:
first loop time:5183470
second loop time:2949142
thats interesting. thx.
It looks like modern JVMs should optimize out the for loops completely because the result of the computation is not used anywhere. This could be fixed e. g. by computing the sum of the hashes of all the elements and displaying it to the user, like this:
int sum = 0;
for (int i=iListSize-1; i > 0; i–) {
sum += lList.get(i).hashCode();
}
System.out.println(sum);
In this example, hashCode() would probably take most of the time. However, if the elements in list referenced only a few String objects (e.g. if the line
sArray[i] = “Array ” + i;
were replaced with
sArray[i] = i%10000 == 0 ? “Array ” + i : sArray[i-1];
) then hashCode() would take less time because the hash value is stored in the String object.
BTW, what Java version did you use?
you are not comparing the difference between loops well.. this 15% should be more… maybe becouse the statement:
String stemp = (String)lList.get(i);
takes more time than i– and i>=0;
then the time the string inicialization consumes inflates both loops times.
see Amdahl’s law
http://es.wikipedia.org/wiki/Amdahl
And he is also introducing differences in the access order which can give completely different results because of caching! this article is garbage
Agreed, sorry, I wrote a garbage article. However, I have created a new article by using JMH to do the testing , see this :
https://mkyong.com/java/jmh-java-forward-loop-vs-reverse-loop/
LOL…yet it is the first google result when I searched for “java reverse for loop”. Keep up the good work, you have helped us all more than you probably know.
sorry, the right reverse loop is
for (int i=listSize-1;i>=0;i–)
thanks for tips~
It seems to me that you’re missing the first element in your reverse loop, the right reverse loop is
For ( int i=listSize; i>=0; i– )