By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,854 Members | 876 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,854 IT Pros & Developers. It's quick & easy.

Nested loop limit?

P: n/a
I am writing a program to do some reliability calculations that
require several nested for-loops. However, I believe that as the
models become more complex, the number of required for-loops will
increase. Does Python have a limit on the number of nested for-loops?
Thanks.
Jul 18 '05 #1
Share this Question
Share on Google+
25 Replies


P: n/a
chad wrote:
I am writing a program to do some reliability calculations that
require several nested for-loops. However, I believe that as the
models become more complex, the number of required for-loops will
increase. Does Python have a limit on the number of nested for-loops?

for n in range(100): .... exec '\n'.join([(' ' * i) + 'for i%s in range(2):' % i for i in
range(n)])
+ '\n' + ' ' * n + 'pass\n'
....
Traceback (most recent call last):
File "<stdin>", line 2, in ?
SystemError: too many statically nested blocks print n

21

Yes. :-)

-Peter
Jul 18 '05 #2

P: n/a
>>>>> "Chad" == chad <ch*********@hp.com> writes:

Chad> I am writing a program to do some reliability calculations
Chad> that require several nested for-loops. However, I believe
Chad> that as the models become more complex, the number of
Chad> required for-loops will increase. Does Python have a limit
Chad> on the number of nested for-loops? Thanks.

No idea (probably not), but if you even need to think of such a thing,
you might want to reconsider the design. 50 or so nested for loops
wouldn't even fit on the screen due to indentation.

Typically excessive nesting can be avoided by introduding a function.

--
Ville Vainio http://tinyurl.com/2prnb
Jul 18 '05 #3

P: n/a
Peter already answered your "specific" question, but
I thought I'd make a suggestion. If you find yourself
with LOTS of nested loops, you probably need to take
a closer look at your class/data structure. Often I
find that if I find that I'm looping a lot, I probably
haven't optimized my data storage or object structures
well. Using list comprehensions can effectively eliminate
many loops, but your data must be structured in lists of
numbers (or objects) for them to work well. Functions
that act on lists of objects can also eliminate many
nested loops. Lists of objects that themselves hold lists
of objects can allow you to create complex hierarchies that
don't require lots of nested lists.

Just some thoughts that might be of benefit.

Regards,
Larry Bates
Syscon, Inc.
"chad" <ch*********@hp.com> wrote in message
news:fd**************************@posting.google.c om...
I am writing a program to do some reliability calculations that
require several nested for-loops. However, I believe that as the
models become more complex, the number of required for-loops will
increase. Does Python have a limit on the number of nested for-loops?
Thanks.

Jul 18 '05 #4

P: n/a
Why does CPython have a limit of 21 nested blocks?

I'm never going to write code this deeply nested by hand, but I could
imagine writing a program that does. It's also sort of a weird limit.

Peter Hansen <pe***@engcorp.com> writes:
>>> for n in range(100): ... exec '\n'.join([(' ' * i) + 'for i%s in range(2):' % i for i in
range(n)])
+ '\n' + ' ' * n + 'pass\n'
...
Traceback (most recent call last):
File "<stdin>", line 2, in ?
SystemError: too many statically nested blocks >>> print n

21

Yes. :-)

-Peter


--
Jul 18 '05 #5

P: n/a
Nelson Minar wrote:
Why does CPython have a limit of 21 nested blocks?

I'm never going to write code this deeply nested by hand, but I could
imagine writing a program that does. It's also sort of a weird limit.
Is the fact that the limit is actually 20 less weird? (The 21 was
where "n" was after it raised an exception, not the last legal
amount of indentation.)

And I think the answer is probably something like "CPython,
being written in C, tends to have certain hard-coded limits
much like C programs always do, rather than being nice and
flexible like programs written with more sophisticated languages
like, say, Python." :-)
Peter Hansen <pe***@engcorp.com> writes:
>>> for n in range(100):

... exec '\n'.join([(' ' * i) + 'for i%s in range(2):' % i for i in
range(n)])
+ '\n' + ' ' * n + 'pass\n'
...
Traceback (most recent call last):
File "<stdin>", line 2, in ?
SystemError: too many statically nested blocks
>>> print n

21

Yes. :-)

-Peter


Jul 18 '05 #6

P: n/a
Peter Hansen <pe***@engcorp.com> writes:
Nelson Minar wrote:
Why does CPython have a limit of 21 nested blocks?
I'm never going to write code this deeply nested by hand, but I
could
imagine writing a program that does. It's also sort of a weird limit.


Is the fact that the limit is actually 20 less weird? (The 21 was
where "n" was after it raised an exception, not the last legal
amount of indentation.)

And I think the answer is probably something like "CPython,
being written in C, tends to have certain hard-coded limits
much like C programs always do, rather than being nice and
flexible like programs written with more sophisticated languages
like, say, Python." :-)


Spot on. This has to do with the 'blockstack', very much an internal
detail to Python's implementation. We'd like to get rid of it (*not*
because we want to let people write code with more than 20 nested for
loops :-) but it's not especially easy (finally: blocks are the
biggest problem).

Cheers,
mwh

--
I really hope there's a catastrophic bug in some future e-mail
program where if you try and send an attachment it cancels your
ISP account, deletes your harddrive, and pisses in your coffee
-- Adam Rixey
Jul 18 '05 #7

P: n/a
Peter Hansen <pe***@engcorp.com> wrote in message news:<FP********************@powergate.ca>...
chad wrote:
I am writing a program to do some reliability calculations that
require several nested for-loops. However, I believe that as the
models become more complex, the number of required for-loops will
increase. Does Python have a limit on the number of nested for-loops?

>>> for n in range(100): ... exec '\n'.join([(' ' * i) + 'for i%s in range(2):' % i for i in
range(n)])
+ '\n' + ' ' * n + 'pass\n'
...
Traceback (most recent call last):
File "<stdin>", line 2, in ?
SystemError: too many statically nested blocks >>> print n 21


However, the code:
for i in xrange(1000):

.... try:
.... exec '[0 %s]' % ' '.join(['for k%d in [0]' % j for j in
xrange(i)])
.... except:
.... print i
.... break

doesn't break until i=227. So if you need more than 20 nested loops,
try replacing them with list comprehensions.
Jul 18 '05 #8

P: n/a
Dan Bishop wrote:
Peter Hansen <pe***@engcorp.com> wrote:
chad wrote:
Does Python have a limit on the number of nested for-loops?
[Yes. 20]


However, the code:

[snip] doesn't break until i=227. So if you need more than 20 nested loops,
try replacing them with list comprehensions.


Actually, I think what both our code samples show is that if
one needs such a large number of statically nested *anything*,
the design is probably broken and should be replaced, if nothing
else, with something that builds the code on the fly...

If you consider that statically nested for loops must in some
way represent different dimensions, is it really possible that
a problem can have more than 20 dimensions (or even nearly that
many!) which must all be looped over simultaneously? I would
try to step way back from my problem and reconsider what I'm
doing if I were ever on my way to that situation...

But I'd be interested in any ("real world", as usual) example
where it is true....

-Peter
Jul 18 '05 #9

P: n/a
Peter Hansen <pe***@engcorp.com> writes:
If you consider that statically nested for loops must in some
way represent different dimensions, is it really possible that
a problem can have more than 20 dimensions (or even nearly that
many!) which must all be looped over simultaneously? .... But I'd be interested in any ("real world", as usual) example
where it is true....


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...

I'm converting much of this project to python, but will probably
keep this part in C and wrap it with SWIG.

Dan

(I'm simultaneously embarrassed and proud of this code... :-)

#define l1(a) for(Label[a] = 0; Label[a] <= cutoff; Label[a]++)

#define l2(a,b,c,d) \
for(Label[a] = low3(Label[b],Label[c],Label[d]); \
Label[a] <= cutoff && Label[a] <= high3(Label[b],Label[c],Label[d]); \
Label[a]+=2)

sumF = 0.0;
sumFG = 0.0;

l1(0)
l1(1)
l1(4)
l2(10,4,0,1)
l1(2)
l1(5)
l2(11,5,0,2)
l1(7)
l2(13,7,1,2)
l2(16,4,5,7)
l1(3)
l1(6)
l2(12,6,0,3)
l1(8)
l2(14,8,1,3)
l2(17,4,6,8)
l1(9)
l2(15,9,2,3)
l2(18,5,6,9)
l2(19,7,8,9)
{
saveF = F();
sumF += saveF;
sumFG += saveF*obsv();
}
Jul 18 '05 #10

P: n/a
Peter Hansen <pe***@engcorp.com> writes:
>>> for n in range(100):

... exec '\n'.join([(' ' * i) + 'for i%s in range(2):' % i for i in
range(n)])
+ '\n' + ' ' * n + 'pass\n'


To tie two threads together, I shudder to think of how unreadable
python code could be if there was a ternary operator. :-)

Dan
Jul 18 '05 #11

P: n/a
Dan Christensen wrote:
Peter Hansen <pe***@engcorp.com> writes:
If you consider that statically nested for loops must in some
way represent different dimensions, is it really possible that
a problem can have more than 20 dimensions (or even nearly that
many!) which must all be looped over simultaneously?
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. :-)
#define l1(a) for(Label[a] = 0; Label[a] <= cutoff; Label[a]++)
#define l2(a,b,c,d) \

[snip code sample]

I won't claim to have tried, or even to be able, to understand the
purpose of the code ;-), but 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.
(And I wonder if you would have written it as statically nested
loops if you didn't have macros to fall back on. One might
say that you're sort of cheating there, since the loop structure
is mostly absent by virtue of having used C.)

Anyway, trust an engineer to think the world can be simple,
and trust a physicist to show that sometimes it's not. ;-)

(Bonvenon al "Pitonujo". Kaj bv. saluti Lindi de mi. :-)

-Peter
Jul 18 '05 #12

P: n/a
>>>>> "Dan" == Dan Christensen <jd*@uwo.ca> writes:

Dan> I'm converting much of this project to python, but will
Dan> probably keep this part in C and wrap it with SWIG.

While agreeing with Peter about the table driven approach (possibly
with some recursion thrown in, the number of recursion levels is not
so limited), your code seems like a textbook example of code where C
performance is going to murder Python performance, so keeping it in C
might indeed make sense if it's run often...

--
Ville Vainio http://tinyurl.com/2prnb
Jul 18 '05 #13

P: n/a
Peter Hansen <pe***@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
Jul 18 '05 #14

P: n/a
On Sun, 11 Jul 2004 13:21:37 -0400, Dan Christensen <jd*@uwo.ca> wrote:
Peter Hansen <pe***@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
Jul 18 '05 #15

P: n/a
bo**@oz.net (Bengt Richter) writes:
How many total executions of the innermost loop are you expecting?
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. :-)
Perhaps a clue to your real problem might yield some ideas for alternatives
to massive nested looping


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
Jul 18 '05 #16

P: n/a
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. Unfortunately, this is only the simplest test
case of a larger problem...


You might want to have a look at:

http://amath.colorado.edu/pub/wavele...ers/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
Jul 18 '05 #17

P: n/a

"Bengt Richter" <bo**@oz.net> wrote in message
news:cc**********@216.39.172.122...
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).

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

Jul 18 '05 #18

P: n/a
Dan Christensen <jd*@uwo.ca> writes:
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.


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.
Jul 18 '05 #19

P: n/a
Dan Christensen wrote:
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.


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.
Jul 18 '05 #20

P: n/a
Fernando Perez wrote:
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 :)


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
Jul 18 '05 #21

P: n/a
Dan Christensen <jd*@uwo.ca> wrote in message news:<87************@uwo.ca>...
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


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
Jul 18 '05 #22

P: n/a
Peter Hansen <pe***@engcorp.com> writes:
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


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
Jul 18 '05 #23

P: n/a
mi***************@gmail.com (Michele Simionato) writes:
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?


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
Jul 18 '05 #24

P: n/a
Dan Christensen <jd*@uwo.ca> writes:
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.


If you're going to generate code and compile it, you might as well
generate C code.
Jul 18 '05 #25

P: n/a
Peter Hansen wrote:

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.


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

Jul 18 '05 #26

This discussion thread is closed

Replies have been disabled for this discussion.