• Post Reply Bookmark Topic Watch Topic
  • New Topic

For loop optimization  RSS feed

 
Jay Damon
Ranch Hand
Posts: 282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When coding for loops, I often code something similar to the following example:

to create a local variable containing the size of the array.

Recently, I had a discussion with another developer regarding which of the following loops would be more efficient:

OR

My guess would be the second example. However, it occurs to me that the Java compiler may optimize both such that there is no real difference.

I would appreciate any comment or insight. Thanks.
 
Chris Montgomery
Ranch Hand
Posts: 141
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a simple and easy way to find out.
try this and let us know what you get



then try this



I use this especially with database calls.
 
Grant Gainey
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wall-clock timings are notoriously bad ways to make decisions about micro-optiimzations - too many variables involved. It's easier to just look at the bytecode (using javap -c). For example - the following class:decompiles to the following bytecode:As you can see, the only difference between the two approaches is that outide() spends an extra bytecode instruction setting object to null. Once they're inside the loop (10-28 in outside(), 8-26 in inside()), the approaches generate identical bytecode.

Note that optimizing at this level is really, really, REALLY pointless. HotSpot does strange and wonderful things to your code, so you have no idea which is "better" at runtime. Worse (and even more likely), one bad algorithm involving I/O will suck up more time than that squeezed out of painstakingly optimizing a bazillion for-loops.

Optimize your design, and write your loops in a way that makes them most readable...

Grant
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I prefer to declare "Object o = array[i]" or iterator.next or whatever inside the loop because it makes it very clear to future generations of maintaners that the object is not to be used outside the loop. It requires no initialization, it has no implied or assured state after to loop. Write to make your intentions clear to humans first, worry about shaving a couple CPU cycles off a loop only if you can prove it's a problem.

A silly optimization story to illustrate: In mainframe days we stored dates as numbers like 20051022. Somebody made all the dates signed fields, because moving data into an unsigned field used one more machine instruction to always make sure the result was positive. We were billed by CPU time and this saved a penny every few million times through the code. It cost much more to explain to every new programmer: no, we don't really have negative dates, not to mention finding the bug when somebody accidentally created a negative date.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jay Damon:
When coding for loops, I often code something similar to the following example:

to create a local variable containing the size of the array.


Have you ever noticed a difference? My guess would be that it doesn't make one. In fact, it could even be slower, because length isn't declared final - it could change its value inside the loop, which the array length cannot.

Moving to our Performance forum...
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that

Object object = array[index];

does NOT create a new object. It only creates a new reference to an already existing object. As pointed out above, there is little difference between the bytecode generated for the two options presented here.

I also agree with Ilja that creating a new variable to store the array length is a questionable "optimization". In my opinion, it makes the code much more difficult to read, which is as much of a concern, if not more, than performance.

Layne
 
Grant Gainey
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Layne Lund:
Note that
I also agree with Ilja that creating a new variable to store the array length is a questionable "optimization". In my opinion, it makes the code much more difficult to read, which is as much of a concern, if not more, than performance.
Layne

Strongly agree - but I'll also note that I have been, once again, surprised at the results from decompiling the two approaches. The "local length variable" approach results in moving a getfield and arraylength out of the loop. This might actually result in a noticeable performance impact.

If the loop had millions of iterations.

And HotSpot didn't do something arcane when optimizing (which I find likely).

And strongly agree about the readability impact and importance thereof.

In a far past life, I recall similar kinds of optimization discoveries being completely invalidated by the next rev of the machine's underlying microcode, resulting in large swathes of code now being (marginally) slower and harder to read. I stopped caring about such issues around then.

Grant
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it's extremely rare that this would really make any noticeable difference in performance. (Especially if we truncate the times with integer division, as Chris has done - eek!) I'm referring both to the question of declaring the variable inside of outside the loop, and to the issue of using another variable for the length. For the first issue, I think it's much more important to focus on the benefits of declaring variables within the smallest scope that's appropriate - it reduces the chance of a bug because you've accidentally re-used a variable name somewhere else. And it's more communicative - declaring the variable nearest where it's actually used. It's that much easier for a reader to see what's going on if you do this as much as possible. Even if we're only talking about two lines worth of distance - it's tiny but I guarantee it's much more significant than any alleged performance effects under discussion here.

You'll be pleased to know that Tiger's enhanced for loop has this sort of trivial optimization built in already. This:

compiles to this:

As we see, the loop avoids to horrible overhead of getfield and arraylength, and thus we may all sleep soundly.
[ October 22, 2005: Message edited by: Jim Yingst ]
 
Grant Gainey
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You'll get no argument from me regarding the actual impact of any of these. Too often I've found that the strongest proponents of these pico-optimisations are the most likely to write code that parses large XML documents multiple times, or recovers static data from distant servers with multiple requests per session. Opening one file unnecessarily will likely wipe out any gain to be had from this level of analysis.

That being said, I do find the discussions useful. I'm always surprised at how many experienced Java programmers don't know about javap. For things like this, you don't have to hypothesize about what a given construct generates - you can know. In that context, this kind of thread can serve a useful purpose.

Even if the coding tricks involved generally don't...

Grant
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well - I know of javap, but when I have to read the output, I need to run the loop giltzillions of times, to get the time back

Of course, the scope-tainting problem could be solved like this:

- you just have to tell new programmers, that blocks without controlstatement are perfectly legal - another couple of minutes you never get back
 
Jay Damon
Ranch Hand
Posts: 282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to everyone who responded! I appreciate the insights and feedback.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I recall similar kinds of optimization discoveries being completely invalidated by the next rev of the machine's underlying microcode, resulting in large swathes of code now being (marginally) slower and harder to read.


Mike Cowlishaw begged users of the REXX language to make no effort to optimize based on their knowledge (or guesses) about how the interpreter worked for exactly this reason. It was nice to have permission from him to not worry about those lowest level implementation details.
 
Grant Gainey
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Heh - Mr. Cowlishaw said that because he just happened to work for the same Really Big Company I mentioned earlier, and knew for a fact that there were people in it doing this kind of thing. In REXX.

SHARE conferences must have driven him nuts...

Grant
 
JuanP barbancho
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

try to use byte or short instead of int.

I think that is more quick.

Thanks
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by JuanP barbancho:
try to use byte or short instead of int.

I think that is more quick.

Why do you think so?
Did you test it?
 
JuanP barbancho
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I test it in some loop and short and byte as fastest than int.

Please, could you test it ?
Thanks
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well - I measured the opposite; small differences for java in client-mode (+10% time for byte), and big differences for server-mode (+3000%), but this will decrease drastically, if real work is done in the loop (I just added a value, to prevent to aggressive optimization).
 
steve souza
Ranch Hand
Posts: 862
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A nice thread. Grant and I think alike.

My overall feeling of these microtuning questions is that they keep the performance discussion in the realm of things that don't make much difference. Performance questions should always be asked in the context of overall application performance. Microtuning questions usually make virtually no difference in overall application performance.

I encourage all of you to put your performance thoughts in the following FAQ.
http://faq.javaranch.com/view?EnterprisePerformance

Grants quotes, and my extracted rules follow.

Rule: Developers that emphasize micro-tuning also tend to write inefficient overall code.



You'll get no argument from me regarding the actual impact of any of these. Too often I've found that the strongest proponents of these pico-optimisations are the most likely to write code that parses large XML documents multiple times, or recovers static data from distant servers with multiple requests per session. Opening one file unnecessarily will likely wipe out any gain to be had from this level of analysis.


Rule: Hotspot may eliminate any possible benefits of micro-tuning.
Rule: Emphasize maintainability and readability over performance and then tune where appropriate.

Note that optimizing at this level is really, really, REALLY pointless. HotSpot does strange and wonderful things to your code, so you have no idea which is "better" at runtime. Worse (and even more likely), one bad algorithm involving I/O will suck up more time than that squeezed out of painstakingly optimizing a bazillion for-loops.

Optimize your design, and write your loops in a way that makes them most readable...

[ October 29, 2005: Message edited by: steve souza ]
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!