reg. GCLS recursive test.

Hi, I wrote a blog entry yesterday about using rpython for the great computer language shootout recursive program, and got a RunTime error when I input on the commandline 11 (1 to 10 goes fine). Just did an svn update of pypy to version 51115 and still get the error, here is the program: blog entry: http://amundblog.blogspot.com/2008/01/rpython-gclb-benchmark-recursive.html source file: recursive.py # The Computer Language Shootout # http://shootout.alioth.debian.org/ # based on bearophile's psyco program # slightly modified by Isaac Gouy def Ack(x, y): if x == 0: return y+1 if y == 0: return Ack(x-1, 1) return Ack(x-1, Ack(x, y-1)) def Fib(n): if n < 2: return 1 return Fib(n-2) + Fib(n-1) def FibFP(n): if n < 2.0: return 1.0 return FibFP(n-2.0) + FibFP(n-1.0) def Tak(x, y, z): if y < x: return Tak( Tak(x-1,y,z), Tak(y-1,z,x), Tak(z-1,x,y) ) return z def TakFP(x, y, z): if y < x: return TakFP( TakFP(x-1.0,y,z), TakFP(y-1.0,z,x), TakFP(z-1.0,x,y) ) return z from sys import argv, setrecursionlimit setrecursionlimit(20000) def main(argv): n = int(argv[1]) - 1 print "Ack(3,%d):" % (n+1), Ack(3, n+1) print "Fib(" + str(28.0+n) + "," + str(FibFP(28.0+n)) print "Tak(%d,%d,%d): %d" % (3*n, 2*n, n, Tak(3*n, 2*n, n)) print "Fib(3):", Fib(3) print "Tak(3.0,2.0,1.0):", TakFP(3.0, 2.0, 1.0) return 0 from pypy.translator.interactive import Translation t = Translation(main, standalone=True, gc='ref') t.source(backend='c') path = t.compile() print path Best regards, Amund

Hello, Amund Tveit wrote:
Hi, I wrote a blog entry yesterday about using rpython for the great computer language shootout recursive program, and got a RunTime error when I input on the commandline 11 (1 to 10 goes fine). Just did an svn update of pypy to version 51115 and still get the error, here is the program:
blog entry: http://amundblog.blogspot.com/2008/01/rpython-gclb-benchmark-recursive.html
source file: recursive.py # The Computer Language Shootout # http://shootout.alioth.debian.org/ # based on bearophile's psyco program # slightly modified by Isaac Gouy
def Ack(x, y): if x == 0: return y+1 if y == 0: return Ack(x-1, 1) return Ack(x-1, Ack(x, y-1)) ...
from sys import argv, setrecursionlimit setrecursionlimit(20000)
def main(argv): n = int(argv[1]) - 1 print "Ack(3,%d):" % (n+1), Ack(3, n+1) print "Fib(" + str(28.0+n) + "," + str(FibFP(28.0+n)) print "Tak(%d,%d,%d): %d" % (3*n, 2*n, n, Tak(3*n, 2*n, n)) print "Fib(3):", Fib(3) print "Tak(3.0,2.0,1.0):", TakFP(3.0, 2.0, 1.0) return 0
from pypy.translator.interactive import Translation t = Translation(main, standalone=True, gc='ref') t.source(backend='c') path = t.compile() print path
This has nothing to do with pypy, and I get the same error with a normal python interpreter: the Ackermann function is gigantically recursive, and 20000 is probably not enough for Ack(3, 11). -- Amaury Forgeot d'Arc

Hi Amund, Amund Tveit wrote:
Hi, I wrote a blog entry yesterday about using rpython for the great computer language shootout recursive program, and got a RunTime error when I input on the commandline 11 (1 to 10 goes fine). Just did an svn update of pypy to version 51115 and still get the error, here is the program:
The runtime error is a stack overflow. RPython is checking for stack overflows when a recursive call is occuring (which is probably also the reason why the RPython version is slower). It is a bit conservative in doing that, which is why C still works for 11, but not the RPython version. To simulate an infinite stack you could additionally pass in the option stackless=True and gc="generation" instead of ="ref" to the Translation class. This will make the program slightly slower, but should allow you very large arguments (argument sizes that probably make the normal C version segfault). Cheers, Carl Friedirch

thanks, will try that. (used stackless python a while back for simulation - http://amundtveit.info/publications/2003/zereal.pdf ) Amund 2008/1/29, Carl Friedrich Bolz <cfbolz@gmx.de>:
Hi Amund,
Amund Tveit wrote:
Hi, I wrote a blog entry yesterday about using rpython for the great computer language shootout recursive program, and got a RunTime error when I input on the commandline 11 (1 to 10 goes fine). Just did an svn update of pypy to version 51115 and still get the error, here is the program:
The runtime error is a stack overflow. RPython is checking for stack overflows when a recursive call is occuring (which is probably also the reason why the RPython version is slower). It is a bit conservative in doing that, which is why C still works for 11, but not the RPython version.
To simulate an infinite stack you could additionally pass in the option stackless=True and gc="generation" instead of ="ref" to the Translation class. This will make the program slightly slower, but should allow you very large arguments (argument sizes that probably make the normal C version segfault).
Cheers,
Carl Friedirch
-- Amund Tveit http://amundtveit.info/ - +47 416 26 572
participants (4)
-
Amaury Forgeot d'Arc
-
Amund Tveit
-
Amund Tveit
-
Carl Friedrich Bolz