[m-dev.] Mutually recursive tailcalls in hlc.
paul at bone.id.au
Thu Nov 5 16:17:33 AEDT 2015
The high level backends do not support optimising mutual recursion. But if
they did fewer programs would have stack overflows and some programs may run
I setup a small test to see if it was worthwhile investigating further (and
it is!). I've compiled mandelbrot in hlc.gc with --no-optimise-tailcalls
--no-c-optimize. The C optimisations are disabled because C may be
optimising tailcalls for me. Then edited the generated C code to create my
test. This example uses direct recursion, that's okay, I'm using it as a
proxy for mutual recursion because with this small benchmark I can
confidently modify the hand generated C files to setup my test.
I have three sinarios:
Normal: compiled without --no-optimiise-tailcalls. This represents the
performance if somehow C supported native mutual recursion.
No tailcalls: Compiled with --no-tailcalls, this represents the current
performance for mutually-recursive code.
Trampoline: My test, a trampoline transformation.
My aim was that the trampoline code is no slower than the no-tailcalls code.
That way getting constant stack space usage for mutually recursive code does
not come at a performance cost.
./mandelbrot-normal -x 800 -y 800 -d -p no 29.12s user 0.01s system 99% cpu 29.153 total
./mandelbrot-no-tailcalls -x 800 -y 800 -d -p no 40.04s user 0.00s system 99% cpu 40.082 total
./mandelbrot-Trampoline -x 800 -y 800 -d -p no 35.36s user 0.00s system 99% cpu 35.401 total
The trampoline transformation creates code that is faster than the
no-tailcalls case, which is the best I could have hoped for. This test case
is a micro-benchmark and so the effect is exaggerated. Nevertheless using a
transformation like this will allow mutually recursive code to run on
constant stack space, and perhaps improve performance at the same time.
I propose to introduce such a transformation for mutually recursive code
within the same module. That is, only on SCCs with more than two
More information about the developers