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 the Author

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

Comments

avatar
11 Comment threads
8 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
14 Comment authors
mkyongNicola PellicanòJumlaAceUrlan Recent comment authors
newest oldest most voted
Jumla
Guest
Jumla

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
Guest
Ace

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
Guest
Urlan

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… Read more »

fail
Guest
fail

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
Guest
Vincenzo Tetzlaff

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
Guest
Alok

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

Chandra sekhar. M
Guest
Chandra sekhar. M

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
Guest
Rob

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

Rob
Guest
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
Guest
Jaan

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… Read more »

juanmf
Guest
juanmf

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ò
Guest
Nicola Pellicanò

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

Flix
Guest
Flix

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

Flix
Guest
Flix

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