Long loop causes maximum recursion depth to be exceeded

[Aaron Goodman]

I am running some Wright-Fisher evolutionary simulations with each generation as a jug task.  I initially implemented this as a recursive function, but ran into issues with the python stack limit since tail-call optimization is not implemented. I rewrote it as a loop, which ran fine, however when I am trying to get the results out of jug it fails unless I preload the entire simulation.

I've attached a minimal example to reproduce the bug.

[Luis Pedro Coelho]

Thanks!

This is a tricky one to fix as it really does hit the central hash
computation code.

Even just triggering the hash computation of a single Task in your deep
stack works around the issue:


from jug import TaskGenerator

@TaskGenerator
def f(i):
return i + 1

def loop(count):
x = 0
result = []
for i in range(count):
x = f(x)
result.append(x)
return result

foo = loop(501)

# Trigger hash computation:
foo[300].hash()
if foo[500].can_load():
print(foo[500].value())

But I'm not 100% sure how to

--

Luis Pedro Coelho | EMBL | http://luispedro.org
My blog: http://metarabbit.wordpress.com

> --
> You received this message because you are subscribed to the Google Groups
> "jug-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to jug-users+...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
> Email had 1 attachment:
> + jugfile.py
> 1k (text/x-python)

[Aaron Goodman]

It seems like this would be a good use for tail-call optimization, and Guido suggested this as the pythonic work around.

I haven't totally grokked what is going on in the hash_update and __jug_hash__ functions, but it seems like something like this might work.

http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html

Or perhaps you could do a DFS using an explicit stack rather than the call stack on the object to find all jug dependencies, and then compute the hashes from the bottom up?  I'm not exactly sure how the back and forth works between hash_update and __jug_hash__ to see if this could easily be moved into one function.

[Luis Pedro Coelho]

> I haven't totally grokked what is going on in the hash_update and
> __jug_hash__ functions, but it seems like something like this might work.

hash_update adds Python objects to a hash object. Basically, hashes are
computed like:

h = create_hash()
hash_update(h, ...)
hash_update(h, ...)
hash_update(h, ...)
hash_update(h, ...)
finalize(h)

__jug_hash__() builds the hash for a Task (or any other object which
defines it).

> http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html
>
> Or perhaps you could do a DFS using an explicit stack rather than the
> call
> stack on the object to find all jug dependencies, and then compute the
> hashes from the bottom up? I'm not exactly sure how the back and forth
> works between hash_update and __jug_hash__ to see if this could easily be
> moved into one function.

In general, it'd be quite hard. hash_update can be done better,
flattening the stack a bit. This makes it harder to trigger the issue
(by a factor of 1 or 2).

But the whole thing is very intertwined and the fact that the user can
add __jug_hash__ to any object (which I am sure is a rarely used
feature, but is there, and I have used it) makes the whole thing a bit
tricky.

Task.__jug_hash__ also only computes the hash the first time it is
called, which is important for speed.

*

The simplest solution is likely to just call

`sys.setrecursionlimit(100000)`

or use explicit hash triggers.

Cheers,
Luis

> > > email to jug-users+...@googlegroups.com <javascript:>.

[Aaron Goodman]

Thanks for the suggestion. I'll just trigger the hash calculation in the jugfile to avoid the recursion.