Nested loop limit?

[Dan Christensen]

Re: Nested loop limit?

bokr@oz.net (Bengt Richter) writes:
[color=blue]
> How many total executions of the innermost loop are you expecting?[/color]

In our longest runs, I think we had this many: 77 922 135 056 261.
This was distributed over a large cluster of machines, as you guessed,
and each job was coded with nested for loops. :-)
[color=blue]
> Perhaps a clue to your real problem might yield some ideas for alternatives
> to massive nested looping[/color]

We can get the answers with statistical methods in minutes, but we
needed to know that the statistical methods were accurate in this case
before extrapolating to other cases.

Dan

[Fernando Perez]

Re: Nested loop limit?

Dan Christensen wrote:
[color=blue]
> 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. Unfortunately, this is only the simplest test
> case of a larger problem...[/color]

You might want to have a look at:

http://amath.colorado.edu/pub/wavelets/papers/pnas.ps.gz

The approach outlined here is a fairly generic framework to tackle
high-dimensionality problems, there's another preprint with more examples
coming down the pipeline.

With d=20, since your complexity for truly nested stuff goes like N^d you are
hosed for almost any value of N. Combining the ideas from the paper above
with:

http://amath.colorado.edu/pub/wavelets/papers/car.ps.gz

it is possible to write separated forms of many interesting kernels in
mathematical physics, providing algorithms which scale linearly with d (albeit
with big constants in front).

I'd like to know in a bit more detail what the context of your calculation is,
and whether the 20 comes from looping over dimesionalities of some
string-derived model or something else. We're very interested in finding
contexts where these dimesionality-reduction approaches may be used. While my
background is not in quantum gravity, if you keep the discussion generic enough
I should be able to follow (keep it bounded by general relativity, the standard
model and introductory stringy stuff and I should be fine).

Feel free to contact me directly at fperez AT colorado DOT edu if you don't feel
like talking about quantum gravity on c.l.py :)

Regards,


f

[Terry Reedy]

Re: Nested loop limit?


"Bengt Richter" <bokr@oz.net> wrote in message
news:ccrucm$qbv $0@216.39.172.1 22...[color=blue]
> 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[/color]
prunes it (not bad).

And there are at least two simple ways to extend the limit: a) have the
innermost loop call a function with its own set of nestings; b) flatten the
nesting with explicit cross-products, as in replacing

for a in [1,2]:
for b in [1,2]: # with

for a,b in [(1,1), (1,2), (2,1), (2,2)]:

Terry J. Reedy

[Paul Rubin]

Re: Nested loop limit?

Dan Christensen <jdc@uwo.ca> writes:[color=blue]
> 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.[/color]

Since I doubt you care very much about portability to lots of different
installations, maybe you could just recompile your copy of Python to use
a higher limit.

[Peter Hansen]

Re: Nested loop limit?

Dan Christensen wrote:
[color=blue]
> 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.[/color]

Maybe Pyrex does not have such a limit, or at least has a higher
one. Then you could generate the Pyrex code on the fly, and
maybe still get C performance.

[Peter Hansen]

Re: Nested loop limit?

Fernando Perez wrote:
[color=blue]
> Feel free to contact me directly at fperez AT colorado DOT edu if you don't feel
> like talking about quantum gravity on c.l.py :)[/color]

Just a note: quantum gravity discussions are _clearly_ on-topic in
c.l.py.

This is obviously so, for one thing because if you look at other
discussions which are not considered off-topic, and compare the
degree of association with Python, you will see that quantum gravity
is relatively (approximately) 100% Python-related.

Secondly, though it's not widely known, the technology behind
the still-missing time machine is based on combining phase-change
metaphysics (cf. the "transmogrifier ", for example, of Calvin-Hobbes
Inc.) with quantum gravity to form an electro-gravitic
four-dimensional propulsive system which the PSU first rel

[Michele Simionato]

Re: Nested loop limit?

Dan Christensen <jdc@uwo.ca> wrote in message news:<873c3ycvd q.fsf@uwo.ca>.. .[color=blue]
> 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[/color]

You should consider writing your code in Lisp if have in mind that kind
of tricks (not that I claim that would be the right way to go, more
likely not).

BTW, just out of curiosity, what kind of computation are you trying to
perform? Is it in the context of loop quantum gravity, or Regge calculus,
or just general relativity?

You would be surprised by the backgrounds of people reading c.l.p. ...


Michele Simionato

[Dan Christensen]

Re: Nested loop limit?

Peter Hansen <peter@engcorp. com> writes:
[color=blue]
> Secondly, though it's not widely known, the technology behind
> the still-missing time machine is based on combining phase-change
> metaphysics (cf. the "transmogrifier ", for example, of Calvin-Hobbes
> Inc.) with quantum gravity to form an electro-gravitic
> four-dimensional propulsive system which the PSU first rel[/color]

Thankfully, I was able to zap Peter with my own transmogrifier before
he completely gave away my secret technique for achieving time travel.

See you later (or sooner),

Dan

[Dan Christensen]

Re: Nested loop limit?

michele.simiona to@gmail.com (Michele Simionato) writes:
[color=blue]
> BTW, just out of curiosity, what kind of computation are you trying to
> perform? Is it in the context of loop quantum gravity, or Regge calculus,
> or just general relativity?[/color]

Spin foam models of quantum gravity, which are thought to be the path
integral version of loop quantum gravity.

(Sorry to the rest of list for going off topic. People who want to
pursue the non-python aspects of my question further should feel free
to e-mail me directly.)

Dan

[Paul Rubin]

Re: Nested loop limit?

Dan Christensen <jdc@uwo.ca> writes:[color=blue]
> 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.[/color]

If you're going to generate code and compile it, you might as well
generate C code.

[Greg Ewing]

Re: Nested loop limit?

Peter Hansen wrote:[color=blue]
>
> Maybe Pyrex does not have such a limit, or at least has a higher
> one. Then you could generate the Pyrex code on the fly, and
> maybe still get C performance.[/color]

Pyrex does not impose any limit on the depth of nesting of
any control structure (as long as your C compiler can handle
the generated code).

--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand

http://www.cosc.canterbury.ac.nz/~greg