Open doug719 opened 3 years ago
tizoc
commented
3 years ago @doug719 being able to look at the code you are running would be helpful.
I'm almost sure SBCL supports TCO when compiled with the correct optimization settings (Shen/SBCL is compiled with (proclaim '(optimize (debug 0) (speed 3) (safety 3)))).
Have you tried with Shen/Scheme ? does it work?
tizoc
commented
3 years ago There is some info here: https://0branch.com/notes/tco-cl.html#sec-2-2
I haven't tried the options, but if you compiler Shen yourself you can experiment with these settings by changing boot.lsp.
doug719
commented
3 years ago Hello Bruno,
Thanks for the prompt reply. The code for ack is listed below. I will try shen/scheme and your sbcl suggestions and let you know the results. I have benchmarks for quite a few scheme implementations that I will send you later. Shen is quite a bit slower on the fib benchmark (no optimizations) (fib 45) and fails on the ack 2 5 benchmark. Regards,Doug
(define ack X 0 -> 0 0 Y -> (* 2 Y) X 1 -> 2 X Y -> (ack (- X 1) (ack X (- Y 1))) )
On Monday, April 26, 2021, 11:40:05 AM MDT, Bruno Deferrari ***@***.***> wrote: There is some info here: https://0branch.com/notes/tco-cl.html#sec-2-2
I haven't tried the options, but if you compiler Shen yourself you can experiment with these settings by changing boot.lsp.
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.
tizoc
commented
3 years ago @doug719 just tried in Shen/Scheme and it works fine. But you may want to measure it anyway, it would be interesting to know how it compares to Chez Scheme (since it is the underlying compiler it uses).
The function is not fully tail-recursive, so that means that the real problem is that by default SBCL's stack size is too low (I checked, it is 2MB).
Try changing this on the shen-cl Makefile:
to
.PHONY: build-sbcl
build-sbcl:
$(SBCL) --control-stack-size 8 --load boot.lspThat will set the stack size to 8MB.
tizoc
commented
3 years ago Btw, tested it myself and I was able to execute (ack 2 5) without a stack overflow on Shen/SBCL.
doug719
commented
3 years ago Hello Bruno,
I downloaded shen-scheme source from github. When trying to build it I get:
"main.c:66:5: note: ‘snprintf’ output between 11 and 4106 bytes into a destination of size 4096
66 | snprintf(shen_scheme_bootfile_path, PATH_MAX, "%s%sshen.boot",
| ^~~~~~~~~~~~~~
67 | shen_scheme_home_path,PATH_SEPARATOR);
| ~~~~~~~~~
mkdir -p _build/bin
cc -o _build/bin/shen-scheme _build/chez/csv9.5.4/ta6le/boot/ta6le/kernel.o main.o -lm -ldl -lpthread -luuid
make: *** No rule to make target 'shen-scheme.scm', needed by '_build/lib/shen-scheme/shen.boot'. Stop.
" I downloaded a binary version. It ran (ack 2 5) fine. Timing on fibonacci: (fib 45)
shen-sbcl 22.65 secondsshen-scheme 6.6 seconds
Note that the chez scheme time is 5.9 seconds. chez scheme is my favorite scheme, so I plan to stick with shen-scheme instead of shen-sbcl. Regards,Doug
On Monday, April 26, 2021, 2:00:01 PM MDT, Bruno Deferrari ***@***.***> wrote: Btw, tested it myself and I was able to execute (ack 2 5) without a stack overflow on Shen/SBCL.
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.
The highly recursive ackermann function is a standard lisp benchmark. (ack 2 5) runs on all of the scheme implementations that I have tried (about 7). I compiled a version of sbcl with --dynamic-space-size=16Gb and then compiled a version of shen. With the release shen binary (22.2), and also my version of shen, (ack 2 5) results in " (3-) (ack 2 5) INFO: Control stack guard page unprotected Control stack guard page temporarily disabled: proceed with caution
debugger invoked on a SB-KERNEL::CONTROL-STACK-EXHAUSTED in thread
<THREAD "main thread" RUNNING {1001720103}>:
Control stack exhausted (no more space for function call frames). This is probably due to heavily nested or infinitely recursive function calls, or a tail call that SBCL cannot or has not optimized away.