[gambit-list] Re: simple unoptimized gsc nontail recursion

Bill Richter richter at math.northwestern.edu
Mon Dec 5 01:51:20 EST 2005


   So the tip is this: try to use tail-calls for deep recursions (say
   more than 1000 deep).  Shallow recursions can be done either with
   tail-calls or non-tail-calls.  There is a graceful degradation, so
   if you happen to do a non-tail-call recursion that is 10000 deep it
   will not be a big mistake.  Gambit was designed to allow
   arbitrarily deep non-tail-call recursions (up to the size of your
   heap) which I think is the right thing to do (certainly better than
   the core dump that C gives).  If you want to limit the depth of
   recursion for testing your code, you can add the -:hNNNN runtime
   option when you start gsi.

Marc, I finally realized you gave me a tip, and tried to debug my
program accordingly.  So I set a maximum heap size of 100MB:

export GAMBCOPT=d-,h100000

 % gsi Curtis-algorithm &
 % fg
*** ERROR IN ##make-vector -- Heap overflow

 %  gsc Curtis-algorithm
 %  gcc -O2 -L. -I. Curtis-algorithm.c Curtis-algorithm_.c -lgambc
 %  ./a.out &
*** ERROR IN Poly->Tree -- Heap overflow

Can I get the debugger to tell me what's happening when it crashes
here? Note I get 2 different answers, and the compiled answer makes
more sense to me: I'm trying to build a huge tree.  It's a dumb
question, because if I thought about my code, I might figure something
out.  Also, I have no idea how to relate the recursion depth to the
heap size, but 100MB is 5% of the available memory (2 GB).


BTW both gsi & gcc crash at the same place:

 % tail -40 Min_t-Max_t-BZ ; ps aux | grep [.]out
   ((23 11 12 4 5 3 3 3) (25 17 3 6 6 5 3))
   ((25 3 5 9 3 5 7 7) (35 12 4 5 3 3 3))
   ((27 3 5 7 3 5 7 7) (29 5 9 3 5 7 7))
   ((27 7 12 4 5 3 3 3) (28 13 2 3 5 7 7))
   ((31 5 5 3 6 6 5 3) (33 9 3 6 6 5 3))
   ((33 21 1 2 4 1 1 1) (34 22 2 4 1 1 1))
   ((41 13 1 2 4 1 1 1) (49 1 2 4 3 3 3))
   ((47 1 1 2 4 3 3 3) (48 2 2 4 3 3 3))
   ((49 5 1 2 4 1 1 1) (50 6 2 4 1 1 1))
   ((53 1 1 2 4 1 1 1) (54 2 2 4 1 1 1)))

(Z 8 72
   (5 10 8 9 11 7 7 7)
   (10 20 5 7 3 5 7 7)
   (17 9 3 5 9 7 7 7))

(B 9 72
   ((1 1 2 4 7 7 11 15 15) (4 5 3 4 7 11 15 15))
   ((1 2 4 3 5 7 11 15 15) (2 3 6 5 7 11 15 15))
   ((2 4 5 5 7 11 15 7 7) (4 8 5 7 11 15 7 7))
   ((3 4 4 5 7 11 15 7 7) (4 5 10 9 15 7 7 7))
   ((3 5 1 2 4 7 11 15 15) (4 6 2 4 7 11 15 15))
   ((3 6 4 5 9 15 7 7 7) (4 7 8 9 15 7 7 7))
   ((5 9 11 8 12 9 3 3 3) (6 11 12 5 9 7 7 7))
   ((7 9 9 3 5 9 7 7 7) (9 17 3 5 9 7 7 7))
   ((9 13 11 12 4 5 3 3 3) (16 8 5 5 9 7 7 7))
   ((11 6 8 3 5 9 7 7 7) (12 8 7 14 4 5 7 7))
   ((12 3 5 10 11 3 5 7 7) (18 8 3 5 9 7 7 7))
   ((15 4 6 3 5 9 7 7 7) (16 5 10 11 3 5 7 7))
   ((15 25 13 1 2 4 1 1 1) (16 28 2 4 5 3 3 3))
   ((17 11 6 5 2 3 5 7 7) (18 14 9 3 6 6 5 3))
   ((21 9 5 5 3 6 6 5 3) (22 10 9 3 6 6 5 3))
   ((23 5 6 5 2 3 5 7 7) (29 6 5 2 3 5 7 7))
   ((25 3 6 5 2 3 5 7 7) (26 6 9 3 6 6 5 3))
   ((29 5 6 2 3 5 7 3 3) (35 6 2 3 5 7 3 3))
   ((31 3 6 2 3 5 7 3 3) (32 6 3 3 6 6 5 3))
   ((33 7 13 1 2 4 1 1 1) (34 10 2 4 5 3 3 3))
   ((37 4 2 2 4 5 3 3 3) (38 6 2 4 5 3 3 3))
   ((46 1 2 3 4 4 1 1 1) (48 2 3 4 4 1 1 1)))





More information about the Gambit-list mailing list