Nested loop limit?

[Bengt Richter]

On Sun, 11 Jul 2004 13:21:37 -0400, Dan Christensen <jdc at uwo.ca> wrote:

>Peter Hansen <peter at engcorp.com> writes:
>
>> Dan Christensen wrote:
>>
>>> Well, in a computation in quantum gravity, I have the C code shown
>>> below.  It has exactly 20 nested for loops!  There are of course
>>> other ways to write it, but given the number of iterations, speed
>>> is the bottom line.
>>
>> (Thanks for the _real_ real-world example. :-)
>...
>> its general appearance suggests to
>> me that it could also be written, perhaps with equivalent or
>> conceivably even better performance, and at least more generality,
>> with some kind of table-driven approach.  I'll certainly bow
>> to your better judgment if you've considered that possibility.
>
>Yes, I've considered it, and in fact I'll be forced to use a
>table-driven approach to handle more general situations, where the
>geometry is read in from a file.  I haven't done timing comparisons,
>but I would be very surprised if it was faster.  There would be some
>beneficial cache effects from the shorter code, but more lookups and
>index shuffling which I would expect to slow things down.  But maybe
>I'm not familiar with some tricks that would make this technique
>faster. 
>
>As for maintainability of my method, using the macros means that
>writing the code is very similar to filling in the table in the first
>place!  :-)
>
>I've actually toyed with the idea of having the program generate the
>code (maybe in Python) on the fly, compile it (e.g. with psyco), and
>then run it.  But with Python's limit of 20 nested loops, that won't
>fly. 
>
>Dan
How many total executions of the innermost loop are you expecting?

At 2 states per nested loop, ISTM you'd have 2**20 unless some logic prunes it (not bad).
But at say 10 states per nested loop, ISTM 10**20 would imply a long wait (>3000 years
if you could do a billion loops/second ;-), unless you have a way of parallelizing
over a LARGE farm and CONSIDERABLE pruning happens.

Perhaps a clue to your real problem might yield some ideas for alternatives
to massive nested looping, where just the repeated control overhead of the innermost
loops by itself could add up to a long wait.

Regards,
Bengt Richter