Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / August 2007

Tip: Looking for answers? Try searching our database.

For-loop optimization question

Thread view: 
Nino - 31 Jul 2007 17:33 GMT
Hello everyone,

This may seem like a pretty simple question, but one that I'm curious
about. I have 2 nested for-loops in my code, and want to know which is
the best (fastest) way to organize them:

OPTION 1:
for (int x=0; x < (somewhere between 0-40); x++) {
    for (int y=0; y < (somewhere between 400-1000); y++) {
         <if the x array matches the y array, call some functions and
do some more logic>
         <else keep going through loop>
    }
}

With option 1, it makes the most sense for me to use with the logic
that needs to be run when an array match is found.

OPTION 2:
for (int x=0; x < (somewhere between 400-1000); x++) {
    for (int y=0; y < (somewhere between 1-40); y++) {
         <if the x array matches the y array, call some functions and
do some more logic>
         <else keep going through loop>
    }
}

I believe option 2 will be faster (right?), but there might be a
little more logic that goes into the work when finding a match.

The ultimate question is... How much difference does it really make
(with this example or in general) in the way nested for-loops are
organized and handled in Java?

Let me know if there is anything I'm leaving out that might help, and
thanks in advance!

Nino Skilj
Patricia Shanahan - 31 Jul 2007 17:51 GMT
> Hello everyone,
>
[quoted text clipped - 34 lines]
>
> Nino Skilj

First of all, code for simplicity and maintainability unless both the
following conditions are met:

1. The program is running slowly enough that it is worth spending risk
and programmer time to make it faster. The cost is not just the
immediate cost, but the long term cost of e.g. errors in future changes
due to reduced clarity.

2. The loop in question is a significant contributor to the slowness of
the program.

If both those conditions are true, and if there is a significant
performance difference between the alternatives, you should be able to
measure it.

If you do need to optimize it, decide what problem you are trying to
solve. If the problem is cache misses, consider loop tiling. If the
problem is mispredicted branches, put the longer loop on the inside.

Patricia
Twisted - 31 Jul 2007 18:51 GMT
> If you do need to optimize it, decide what problem you are trying to
> solve. If the problem is cache misses, consider loop tiling. If the
> problem is mispredicted branches, put the longer loop on the inside.

What is "loop tiling"? I'm afraid it's not self-explanatory...
Patricia Shanahan - 31 Jul 2007 18:57 GMT
>> If you do need to optimize it, decide what problem you are trying to
>> solve. If the problem is cache misses, consider loop tiling. If the
>> problem is mispredicted branches, put the longer loop on the inside.
>
> What is "loop tiling"? I'm afraid it's not self-explanatory...

No, but it is a good search term. In particular, see the first hit on
the Google search, the Wikipedia page,
http://en.wikipedia.org/wiki/Loop_tiling.

Patricia
bugbear - 01 Aug 2007 10:08 GMT
>>> If you do need to optimize it, decide what problem you are trying to
>>> solve. If the problem is cache misses, consider loop tiling. If the
[quoted text clipped - 5 lines]
> the Google search, the Wikipedia page,
> http://en.wikipedia.org/wiki/Loop_tiling.

Indeedy.

http://groups.google.com/group/sci.image.processing/browse_thread/thread/778a2ba
5f20747ea/396efc1f39647722?lnk=st&q=rotate+bugbear+tile&rnum=2#396efc1f39647722


   BugBear
Roedy Green - 31 Jul 2007 20:56 GMT
>The ultimate question is... How much difference does it really make
>(with this example or in general) in the way nested for-loops are
>organized and handled in Java?

When in doubt, measure. See http://mindprod.com/jgloss/benchmark.html

The innermost loop body will be executed the same number of times
either way.  

Either in your head or with variables try counting how many times the
outer loop executes and how many the inner executes. Sum that for and
approximation to your overhead.

What is more important in such loopings is LOCALITY.  Don't hop all
over ram.  Try to process linearly. This keeps caches happy and VRAM
swapping down.
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.