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