[MLton] Speedup from unrolling and tail-recursion

Fri, 21 Jan 2005 22:51:14 +0100

```--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

As I understand it, scheme and lisp can do these two optimizations
automatically. I was curious to see how much performance gain MLton
could see from this.

Attached are four versions of a very silly example function.
The human-written version		 11428571 ops/ms
Loop unrolled				 93023255 ops/ms
Tail recursion optimized		288975581 ops/ms
Tail recursion and loop unrolled	636334712 ops/ms

I understand that automatic tail-recursion is hard to do, but I think a
scheme compiler, Rabbit (?) was able to do it with only a few simple rules.
Recursion/loop unrolling isn't very hard though, and MLton already has
inlining, so why is this not done?

--
Wesley W. Terpstra

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii

val () = print (Int.toString n ^ "\n")

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii

let
fun tail 0 a = a
| tail x a = tail (x-1) (a+1)
in tail x 0 end

val () = print (Int.toString n ^ "\n")

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii

exception Unreachable
let
fun tail x a =
if x < 8 then case x of
0 => a
| 1 => a+1
| 2 => a+1+1
| 3 => a+1+1+1
| 4 => a+1+1+1+1
| 5 => a+1+1+1+1+1
| 6 => a+1+1+1+1+1+1
| 7 => a+1+1+1+1+1+1+1
| _ => raise Unreachable
else tail (x-1-1-1-1-1-1-1-1) (a+1+1+1+1+1+1+1+1)
in tail x 0 end

val () = print (Int.toString n ^ "\n")

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii

exception Unreachable
if x < 8 then case x of
0 => 0
| 1 => 1
| 2 => 1+1
| 3 => 1+1+1
| 4 => 1+1+1+1
| 5 => 1+1+1+1+1
| 6 => 1+1+1+1+1+1
| 7 => 1+1+1+1+1+1+1
| _ => raise Unreachable