Reverse loop versus Forward loop in Performance – Java

Forward Looping

Forward looping is loop from starting element and continues to the end of the elements. 0..1..2..3..End. Most of the time, may be i can said all the time we are using this type of looping method to loop through an array, List or collection.

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

Reverse Looping

Reverse looping is loop from end of the element and continues to the starting elements. End..9..8..0. Most of the time, may be i can said all the time we are not using this type of looping method.

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

Performance Test

Here i create two tiny programs to use forward loop and reverse loop to traverse 15 millions of data, and display the elapse time in output.

1. Forward Looping

import java.util.Arrays;
import java.util.Date;
import java.util.List;
 
public class LoopTestForward {
  public static void main(String[] argv) {
 
	  String sArray[] = createArray();
 
	  //convert array to list
	  List lList = Arrays.asList(sArray);
	  int iListSize = lList.size();
 
          //Forward Loop Testing 
	  System.out.println("\n--------- Forward Loop --------\n");
	  long lForwardStartTime = new Date().getTime();
	  System.out.println("Start: " + lForwardStartTime);
 
	  //for loop
	  for (int i=0; i< iListSize; i++){
		  String stemp = (String)lList.get(i);
	  }
 
	  long lForwardEndTime = new Date().getTime();
	  System.out.println("End: " + lForwardEndTime);
 
	  long lForwardDifference = lForwardEndTime - lForwardStartTime;
	  System.out.println("Forward Looping - Elapsed time in milliseconds: " + lForwardDifference);
 
	  System.out.println("\n-------END-------");
 
 
  }
 
  static String [] createArray(){
 
	  String sArray[] = new String [15000000];
 
	  for(int i=0; i<15000000; i++)
		  sArray[i] = "Array " + i;
 
	  return sArray;
  }
}

2. Reverse Looping

import java.util.Arrays;
import java.util.Date;
import java.util.List;
 
public class LoopTestReverse {
  public static void main(String[] argv) {
 
	  String sArray[] = createArray();
 
	  //convert array to list
	  List lList = Arrays.asList(sArray);
	  int iListSize = lList.size();
 
	  //Reverse Loop Testing 
	  System.out.println("\n--------- Reverse Loop --------\n");
	  long lReverseStartTime = new Date().getTime();
	  System.out.println("Start: " + lReverseStartTime);
 
	  //for loop
	  for (int i=iListSize-1; i > 0; i--){
		  String stemp = (String)lList.get(i);
	  }
 
	  long lReverseEndTime = new Date().getTime();
	  System.out.println("End: " + lReverseEndTime);
 
	  long lReverseDifference = lReverseEndTime - lReverseStartTime;
	  System.out.println("For - Elapsed time in milliseconds: " + lReverseDifference);
 
	  System.out.println("\n-------END-------");
 
  }
 
  static String [] createArray(){
 
	  String sArray[] = new String [15000000];
 
	  for(int i=0; i<15000000; i++)
		  sArray[i] = "Array " + i;
 
	  return sArray;
  }
}
D:\test>java -Xms1024m -Xmx1024m LoopTestFoward
D:\test>java -Xms1024m -Xmx1024m LoopTestReverse

Performance Test Result (in milliseconds)

Conclusion

The result show there’s not much different between forward and reverse looping in 1 million of data. However when data grow huge, the performance of reverse looping is slightly faster than forward looping around 15%.

May be you will question about who so stupid to load 1 million of data into a single List or Collection. Please imagine a multi-thread system environment, where 100k people concurrent access your “forward loop x 10″, it already over 1 million. Ya i know sometime the different is negligible, but i do believe believe “Reverse loop” is a good habit in programming , it can increase the performance. It’s sound weird …but performance show.

Tags :

About the Author

mkyong
Founder of Mkyong.com and HostingCompass.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

  • 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

    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

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

  • http://þÿ 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

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

  • 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.

    • http://www.sentinelweb.co.uk/products Rob

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

      • http://www.sentinelweb.co.uk/products 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

    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

    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

  • Flix

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

    • mkyong

      thanks for tips~

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