[MLton] Speedup from unrolling and tail-recursion

[Wesley W. Terpstra]

--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
Content-Disposition: attachment; filename="add.sml"

fun addn 0 = 0
  | addn x = addn (x-1) + 1

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

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="addt.sml"

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

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

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="addtu.sml"

exception Unreachable
fun addn x = 
  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 n = addn 2000000000
val () = print (Int.toString n ^ "\n")

--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="addu.sml"

exception Unreachable
fun addn x = 
  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
  else addn (x-1-1-1-1-1-1-1-1) +1+1+1+1+1+1+1+1

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

--lrZ03NoBR/3+SXJZ--