Hello Bill
You did address Marc, but I think I can reply something to your questions as well.
At 0:51 Uhr -0600 05.12.2005, Bill Richter wrote:
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?
If you run code from the repl (start gsc without arguments), using compile-file and load, like (compile-file "Curtis-algorithm" '(debug)) (load "Curtis-algorithm") then when running out of memory the debugger is entered.
(I haven't used batch compilation for such a long time that I don't remember if the resulting executables should enter the debugger as well.)
Note I get 2 different answers, and the compiled answer makes more sense to me:
Might just be coincidence. To see the place in your code where it happens, enter ",b" in the debugger. (Read the fine manual!)
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.
Well, what is your question then? Maybe you want single step your code: use the interpreter, switch tail-call optimization off (read about proper-tail-calls-set! in the manual), then insert (step) statements into your code (or before running it from the repl).
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).
What does "available memory" mean? Hardware RAM, or a resource limit enforced by your OS? That's probably irrelevant anyway if you set a heap limit using gambit options. What's your question? If you want to know how much memory a particular recursion depth takes, why not insert a recursion depth count in your code and stop recursion at a particular depth to let you see at memory usage, or regularly print the current depth?
You probably took Marc Feeley's reply literally ("If you want to limit the depth of recursion for testing your code, you can add the -:hNNNN option"), but this option limits the heap size, not the recursion depth per se (read the help, gsc -:h), and since recursion is only limited by the heap size, this of course also limits recursion depth.
BTW both gsi & gcc crash at the same place:
(I don't understand anything in the following output.)
Christian.
Afficher les réponses par date
Hi Schemers:
I would like to use Scheme with FFI in my work on embedded systems. Gambit is appealing because it specifically mentions serial ports and the code distribution is cleanly organized.
It installs easily on Linux but not on win98 which is my main target. There are options for various compilers in /misc. I don't have the MKS toolkit so I tried the IDE builds for Watcom and VC++ 4. Neither worked since they look for files gsi.c and _back.c which don't exist. I also got compile failures on MSYS/MinGW (but not sure it is installed correctly).
I suspect these IDE projects may have worked at some time for a particular release but have not been kept current. This is a general problem for open-source, cross-platform projects where the project manager may not have the resources to recheck the legacy mail-ins from contributors.
I would like to use one of these win32 compilers:- * OpenWatcom * Borland C++ (the free one) * BloodShed Dev-Cpp
If someone could provide a project file or simple Makefile, I would be delighted and eternally grateful.
regards, -Bob-
"Everything should be as simple as possible, but no simpler" -- Albert Einstein
Can I get the debugger to tell me what's happening when it crashes here?
If you run code from the repl (start gsc without arguments), using compile-file and load, like (compile-file "Curtis-algorithm" '(debug)) (load "Curtis-algorithm") then when running out of memory the debugger is entered.
Thanks, Christian, and I guess that's a general point unrelated to Marc's heap size tip. And the manual explains how to do it in gsi:
gsi -:dr,h10000 Curtis-algorithm *** ERROR IN Poly->Tree, "Lambda-defs.scm"@311.21 -- Heap overflow
But I didn't learn much, because I couldn't find any variables to examine: my debugger transcript below. On to your other points:
What's your question?
The one you sort of answered: how does the debugger help me analyze the heap size error triggered by Marc's idea. But maybe you're asking a more general general question, so let me ramble:
This is Gambit code from near the top of my web page http://www.math.northwestern.edu/~richter/Richter-Curtis-algorithm.tar.gz which doesn't run as fast as I'd like it too. Marc & Germaine gave me some tips before, so it runs a good deal faster than it first did! Now I just learned about tail recursion (I know, I shoulda learned this long ago, but I hadn't seen explained at all usefully before reading Sitaram's Fixnum tutorial (tail recursion = iteration)), so I posted a question which Marc answered: gsc/gcc will *not* optimize away all possible tail recursion problems! Don't let the recursion depth get above 1000 or 10000! So I yelped for help which Marc's heapsize tip didn't tell me anything. And of course you're right, as I realized myself, heap size isn't the same thing as recursion depth. But I think I see some my tail recursion problems. My main loop is Curtis-alg, which looks tail recursive to me:
(define (Curtis-alg a X top-level-tags min-target) (if (Poly-0? X) false (let ([x (Tree-first X)]) (if (Mono-ascending-left-lex x min-target) false (let ([b (lookup-tag x top-level-tags)]) (if b (let ([X+db (merge-tree (Poly->Tree (truncate-poly (d b) min-target)) X)]) (Curtis-alg a X+db top-level-tags min-target)) x))))))
Curtis-alg builds a huge tree, and the functions used, merge-tree & Poly->Tree, don't look tail recursive to me! I'll fiddle with this...
Here's my debugger output, modeled on the informative example in the node "Debugging commands":
,i
#<procedure #2 Poly->Tree> = (lambda (X) (let ((n-terms (lambda (n S) (list n (Poly->Tree S))))) (if (empty? X) empty (let* ((x (first X)) (n (Mono-first x)) (y (Mono-rest x))) (if (Mono-1? y) X (let loop ((n n) (S_n (list y)) (X (rest X))) (if (Poly-0? X) (list (n-terms n (reverse S_n))) (let* ((x (first X)) (m (Mono-first x)) (y (Mono-rest x))) (if (= n m) (loop n (cons y S_n) (rest X)) (cons (n-terms n (reverse S_n)) (loop m (list y) (rest X))))))))))))
,e
(current-exception-handler) = primordial-exception-handler (current-input-port) = '#<input-port #3 (stdin)> (current-output-port) = '#<output-port #4 (stdout)> (current-directory) = "/tmp_mnt/rhome/richter/Gambit-Curtis-alg/statprof/Pol...
,b
0 Poly->Tree "Lambda-defs.scm"@311:21 (list (n-terms n (reve... 1 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 2 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 3 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 4 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 5 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest... 6 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 7 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest... 8 Curtis-alg "Curtis-algorithm.scm"@325:43 (Poly->Tree (trun... 9 calc-d "Curtis-algorithm.scm"@288:22 (Curtis-alg a (Po... ... 12 ##time 13 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (##time (lambda ()... 14 ##load 15 ##main
,+
1 Poly->Tree "Lambda-defs.scm"@299.20 (Poly->Tree S) \1> ,b 1 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 2 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 3 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 4 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 5 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest... 6 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S) 7 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest... 8 Curtis-alg "Curtis-algorithm.scm"@325:43 (Poly->Tree (trun... 9 calc-d "Curtis-algorithm.scm"@288:22 (Curtis-alg a (Po... 10 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (calc-d s t) 11 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (do ((s (if (< t M... 12 ##time 13 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (##time (lambda ()... 14 ##load 15 ##main \1> ,e n = 13 (current-exception-handler) = primordial-exception-handler (current-input-port) = '#<input-port #3 (stdin)> (current-output-port) = '#<output-port #4 (stdout)> (current-directory) = "/tmp_mnt/rhome/richter/Gambit-Curtis-alg/statprof/Pol... \1> ,q
At 0:46 Uhr -0600 07.12.2005, Bill Richter wrote:
so I posted a question which Marc answered: gsc/gcc will *not* optimize away all possible tail recursion problems! Don't let the recursion depth get above 1000 or 10000!
I think he said, if the depth of *non*-tail recursion (i.e. real recursion, not iteration) goes above ~10000 it will start to allocate call frames on the heap and thus get slower. Regarding tail calls, to my knowledge, Gambit always handles them correctly (unless if you intentionally switch off proper-tail-calls (only effective in the interpreter) of course).
(He also said, that if you declare a big inlining-limit, the compiler will partly unroll the recursion code and running it will thus allocate less space for the call frames, which might have had an effect on the speed of your first attempt.)
Curtis-alg builds a huge tree, and the functions used, merge-tree & Poly->Tree, don't look tail recursive to me! I'll fiddle with this...
Here's my debugger output, modeled on the informative example in the node "Debugging commands":
,i
#<procedure #2 Poly->Tree> = (lambda (X) (let ((n-terms (lambda (n S) (list n (Poly->Tree S))))) (if (empty? X) empty (let* ((x (first X)) (n (Mono-first x)) (y (Mono-rest x))) (if (Mono-1? y) X (let loop ((n n) (S_n (list y)) (X (rest X))) (if (Poly-0? X) (list (n-terms n (reverse S_n))) (let* ((x (first X)) (m (Mono-first x)) (y (Mono-rest x))) (if (= n m) (loop n (cons y S_n) (rest X))
this (true) part of the if form is a tail call..
(cons (n-terms n (reverse S_n)) (loop m (list y) (rest X))))))))))))
.. whereas this (false) part is not. To be able to return the result of cons, it first needs to run (loop ...), so it cannot eliminate the current continuation frame. So using "loop" as name in your named let looks misleading as it's not an iteration.
I don't have the time to delve into the code or algorithm you're using.
Maybe I can give some other quick help:
- I think some algorithms really need recursion (and I think especially trees) - sometimes, mutation can replace recursion: for example, you can copy a list by using iteration and appending list elements to the tail of the new list using set-cdr!. - sometimes you can replace recursion with an iterative calculation and a second calculation afterwards: e.g. you can copy a list using iteration and without mutation by reversing it two times, the reversion being the iteration (reverse (reverse lis)). But that only moves from using call frames to using cons cells, so only makes a small linear difference if at all.
Maybe you could reorganize your problem to only need part of the tree in memory? Maybe using lazy evaluation (using streams) helps? (I can't say without looking at the problem in detail)
Christian.
so I posted a question which Marc answered: gsc/gcc will *not* optimize away all possible tail recursion problems! Don't let the recursion depth get above 1000 or 10000!
I think he said, if the depth of *non*-tail recursion (i.e. real recursion, not iteration) goes above ~10000 it will start to allocate call frames on the heap and thus get slower.
Right, thanks for correcting my dumb "typo".
Regarding tail calls, to my knowledge, Gambit always handles them correctly (unless if you intentionally switch off proper-tail-calls (only effective in the interpreter) of course).
Yeah. Didn't know about about switching off proper-tail-calls.
(He also said, that if you declare a big inlining-limit, the compiler will partly unroll the recursion code and running it will thus allocate less space for the call frames, which might have had an effect on the speed of your first attempt.)
Oh, thanks, I didn't understand that part of Marc's reply! The 2 ways that Marc & Germaine helped me was by handing me the inline code (declare (standard-bindings) (fixnum) (not safe) (run-time-bindings) (inline) (inlining-limit 1000) (block)) and by profiling my code, which showed that trees might be good.
So using "loop" as name in your named let looks misleading as it's not an iteration.
Yeah, good point. But I knew Poly->Tree wasn't tail-recursive, I posted that yesterday even. Thanks for your tips:
Maybe I can give some other quick help:
- I think some algorithms really need recursion (and I think especially trees)
I was wondering about that. OK, I think all the non-tail action in my program has to do with trees. Is there a good reference for tail-recursive tree functions? I need to make trees, and merge them. The thing I worry about is something you said in a different context:
But that only moves from using call frames to using cons cells, so only makes a small linear difference if at all.
Yeah, see I understand why my non-tail program bombed that was adding up 1s, I had this huge stack, which in my mind means I wrote down a huge expression (+ 1 (+ 1 (+ 1 (....... 1)))) Well, you gotta allocate space to store this huge expression! And the tail-recursive program didn't do any such thing: it just looped sum <- sum + 1, that doesn't take any space. So a better test (which I haven't done) would be to first build a huge list (1 1 1 ....1) and then tail-recursively sum the list. Well, that huge list is gonna allocate a lotta space!
And that's how it goes for my (presently non-tail) tree functions: Everything on the stack gets put into the answer. That is, my tree functions return a huge tree.
Maybe you could reorganize your problem to only need part of the tree in memory? Maybe using lazy evaluation (using streams) helps? (I can't say without looking at the problem in detail)
I'd be surprised if these tips would help. Uh, what I'm doing isn't that hard or mathematically sophisticated. From my README file:
Defines simple functions for 3datatypes, Indeterminate = Indet = Z Monomials = Mono = (listof Z) Polynomials = Poly = (listof Mono) Tags = (cons Mono (union Mono 'cycle)) Tree ::= empty | (listof (n Tree))
I use the convention that Z = the datatype of integers, N = nonnegative integers, the natural numbers plus 0.
So Mono-1 = Poly-0 = '(), etc. A Monomial is often called a term. We call a term (a b c ...) admissible if b <= 2a, c <= 2b, etc. A term has an s-degree & a t-degree, calculated by Mono-s & Mono-t. The term (a_1 ... a_s) has s-degree s, and t-degree a_1 + ... + a_s + s.
Crucial is the left-lexicographical order, the dictionary order, simplified as we only apply it to terms (words) of the same length.
(a_1 ... a_s) < (b_1 ... b_s) iff either a_1 < b_1, or else a_1 = b_1, and (a_2 ... a_s) < (b_2 ... b_s)
A polynomial (i.e. a list of terms = monomials) is sorted if it's sorted in the left-lex order (in descending order). A polynomial is simplified if it doesn't have any repeated terms. Then Poly->Tree turns a sorted simplified polynomial into a tree, which is supposed to make it easier to find stuff. merge-tree then merges 2 such trees.