ackermann benchmark aborts

[doug719]

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.

[tizoc]

@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]

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]

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]

@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:

https://github.com/Shen-Language/shen-cl/blob/c26776641fe4b63aacfbc6013fad9c1c16974a5e/Makefile#L166-L168

to

.PHONY: build-sbcl
build-sbcl:
	$(SBCL) --control-stack-size 8 --load boot.lsp

That will set the stack size to 8MB.

[tizoc]

Btw, tested it myself and I was able to execute (ack 2 5) without a stack overflow on Shen/SBCL.

[doug719]

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.