Main Tutorials

Java – Reverse loop versus Forward loop in Performance

Node
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

References

  1. JMH – Java Forward loop vs Reverse loop

About Author

author image
Founder of Mkyong.com, love Java and open source stuff. Follow him on Twitter. If you like my tutorials, consider make a donation to these charities.

Comments

Subscribe
Notify of
20 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Jumla
10 years ago

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.

Ace
10 years ago

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…

Urlan
11 years ago

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

fail
11 years ago

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++)

Vincenzo Tetzlaff
11 years ago

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!

Alok
13 years ago

This is totally wrong
If you correct the mistake pointed out by Flix, the forward loop is faster then reverse.

Chandra sekhar. M
13 years ago

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.

Rob
12 years ago

this test shows faster reverse time than forward time:
first loop time:1452666
second loop time:2095571

Rob
12 years ago
Reply to  Rob

OK but when the loop size is increased, the fwd loop wins:

first loop time:5183470
second loop time:2949142

thats interesting. thx.

Jaan
14 years ago

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?

juanmf
14 years ago

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

Nicola Pellicanò
8 years ago
Reply to  juanmf

And he is also introducing differences in the access order which can give completely different results because of caching! this article is garbage

Net Dawg
1 year ago
Reply to  mkyong

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.

Flix
15 years ago

sorry, the right reverse loop is
for (int i=listSize-1;i>=0;i–)

Flix
15 years ago

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– )