• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

for loop optimization

 
mangpal singh
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Case 1 :
for(int i=0;i<50000;i++){
System.out.print("l");
}

Case 2:
for(int i=50000;i>0;i--){
System.out.print("m");
}

Which of the two is faster ? If one of the two is faster, how much value does it add to have this optimization ?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can measure elapsed time using the System.currentTimeMillis() method. Be sure to run the tests several times to see if the time varies substantially.
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From an assembler point of view, case 2 seems easier to track, by looking at the zero flag. Does it make it faster ? Don't know. Probably not. We're not in the 80's anymore anyway
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That would be nice to send the results of Jim's suggestion
 
mangpal singh
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As per Jim's suggestion, here is the time required for each case after running it 4 times consecutively. Surprisingly, case 2 takes more time except once.

Case 1 Case 2
844 1078
1469 1578
1438 1422
922 1141
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it's not *that* surprising - it's typical code, so the JVM probably got optimized for it.

Moving to our Performance forum...
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that the two loops use a different range of values for i: the first is 0...49999, while the second is 50000...1. In most cases, you'd have to change the test in the second one to be > -1 or >= 0, anyway -- so now you have to go off and time it again...
 
Bjorn Svensson
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by mangpal singh:
As per Jim's suggestion, here is the time required for each case after running it 4 times consecutively. Surprisingly, case 2 takes more time except once.

Case 1 Case 2
844 1078
1469 1578
1438 1422
922 1141


Also remember, the possibility that if you have non-fixed font you will
have a lot of extra lines in case 2 compared to case 1.
Avoid doing console I/O when doing low level performace tests
like this.
 
Shaan Shar
Ranch Hand
Posts: 1249
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is proved old mathametical algorithm that decreasing a number is faster then Increasing a number and the another fatcor is
about zero flag. which is easier then to compare every time you increase the number and then compare it to maximum value....



 
mangpal singh
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ernest,
The number of iterations performed by both the loops is same whether u go from 0 - 49999 or 50000 - 1.

Bjorn,
When we tried executing the loops without System.out.print() statements, the time taken is displayed as 0 in both cases.
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13071
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That myth about using the decrement instead of increment in a loop got started way back with Java 1.02 - I can't believe it is still circulating.

PLEASE! write your code for clarity and maintainability and ignore these bizarre "optimizations".

Bill (the old timer)
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Bj�rn Julander:

Also remember, the possibility that if you have non-fixed font you will
have a lot of extra lines in case 2 compared to case 1.


Almost exactly the same lines are printed in both cases, but in a different order.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by mangpal singh:

The number of iterations performed by both the loops is same whether u go from 0 - 49999 or 50000 - 1.


Indeed, I didn't imply otherwise. But the usefulness of the loop index differs: if you're going to use it as an array index, or an argument to List.get(), for example, then in the second case you'd need to either change the loop test or subtract 1 from the index before using it. What I'm saying is that in any real program, this may add additional overhead, and as long as you're microbenchmarking, you need to consider this.

Also, you need to read up on how HotSpot works before doing any kind of benchmark like this. If you put the loops in a separate method and invoke them multiple times, you'll see the performance improve. Just running something like this once in a test application gives an inaccurate impression of how it will act in a real program.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ernest Friedman-Hill:


Almost exactly the same lines are printed in both cases, but in a different order.


Case 1 prints "l"s, case 2 "m"s. With a non-fixed font, the "m"s are likely to produce more line breaks...
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ilja Preuss:


Case 1 prints "l"s, case 2 "m"s. With a non-fixed font, the "m"s are likely to produce more line breaks...


My memory failed me during the discussion. I could've sworn the code was printing the loop index values themselves, one per line. Sorry, gang.
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Trying to measure performance of the loop itself, when the loop contains console output is totally doomed. The console output will take hugely longer than the loop itself.
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can at least
to avoid the time for real output on the one hand, and prevent the super-optimization of removing the needles for-loop all together.

50.000 iterations are of course nothing.

And for microbenchmarks, you should reverse the code, and run both loops in reversed order too.
[ April 27, 2006: Message edited by: Stefan Wagner ]
 
Isuru Sampath
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ankur Sharma:
This is proved old mathametical algorithm that decreasing a number is faster then Increasing a number and the another fatcor is
about zero flag. which is easier then to compare every time you increase the number and then compare it to maximum value....


I don't think that there is any truth in it, at least for Java.

Test Code:




Results:

First Set:


If possible, please run the test yourself and see. Maybe you could post the results here...
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes thank you Isuru. System.out is a blocking call or at least not thread friendly. Im not sure what was meant to be tested in the original post. The speed of the loop operation or the speed of repeated calls to System.out?

If one or the other were faster, it would be retarded by the call to System.out. Isuru's example removes this issue.
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try Isurus code with java -server ForTest:
 
Isuru Sampath
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think Stefan's results suggest that the operation results were cached.
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guess the hotspot-compiler recognizes that the result of Math.sqrt (_dNum); is never used and the whole loop might be skipped.

I guess if you avoid this skipping by doing something more inside the loop, the difference between forward and backward iteration becomes negligible.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic