From: William James <w_a_x_man@...>
Date: 2006-08-04T03:10:10+09:00
Subject: Re: For performance, write it in OCaml

Jon Harrop wrote:
> M. Edward (Ed) Borasky wrote:
> > *This* expert suggests comparing performance between the C version and
> > the Ocaml version on the *same* machine! :)
>
> On my machine (Athlon X2 4400+, Debian Linux, gcc 4.0.4, OCaml 3.09.2, Sun
> JDK 1.5):
>
>         Compile Run
> C       0.137s  0.386s gcc -O3 -Wall
> OCaml   0.171s  0.668s ocamlopt
> OCaml   0.161s  0.626s ocamlopt -inline 100 -unsafe
> OCaml2  0.165s  0.415s ocamlopt
> OCaml2  0.165s  0.401s ocamlopt -unsafe
> Java    1.565s  1.688s javac
>
> Some niggles:
>
> 1. A lot of precalculation has been done in the C and Java, to the extent
> that we're breaking Java compilers (always a bad sign).
>
> 2. Java is nothing like as slow as the OP claimed.
>
> 3. OCaml is only 4% slower than C and only 10% slower with bounds checking.
>
> 4. Whether Ruby is fast enough or not, you should be programming in OCaml
> and not in Ruby or C. ;-)
>
> Here's my OCaml2 (based upon William's):
>
> let rec fact n = if n=0 then 1 else n*fact(n-1)
>
> let size = 5
> let n = fact size
>
> (* Permutation generator *)
> let p = Array.make size 0
> let xx = Array.init size (fun i -> if i<size-1 then 0 else -1)
> let gen_perm() =
>   let i = ref (size - 1) in
>   while !i > 0 && xx.(!i) = !i do
>     xx.(!i) <- 0;
>     decr i
>   done;
>   if !i = 0 then 1 else begin
>       xx.(!i) <- xx.(!i) + 1;
>       p.(0) <- 1;
>       for i=0 to size - 1 do
>         p.(i) <- p.(i - xx.(i));
>         p.(i - xx.(i)) <- i+1
>       done;
>       0
>     end
>
> (* Permutations *)
> let perms = Array.init n (fun _ -> ignore(gen_perm()); Array.copy p)
>
> let incompat =
>   let aux x y =
>     Array.iteri (fun i px -> if px = perms.(y).(i) then raise Exit) perms
> (x);
>     false in
>   Array.init n (fun x -> Array.init n (fun y -> try aux x y with Exit ->
> true))
>
> let join list = String.concat "" (Array.to_list (Array.map string_of_int
> list))
> let output_strings = Array.map join perms
> let board = Array.make size 0
>
> let op = String.make (size*(size+1)-1) ':'
>
> let rec add_a_row row =
>   if row = size then begin
>       for i=0 to size-1 do
>         String.blit output_strings.(board.(i)) 0 op (i*(size+1)) size
>       done;
>       print_string op;
>       print_string "\n"

A small point.
  print_endline op
is shorter.  Is it faster?