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.

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

Leave a Reply

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