From: Jon Harrop <jon@...>
Date: 2006-08-04T08:50:09+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

That was 64-bit. Here are my 32-bit timings (language versions are the
same):

        Compile  Run
C       0.126s    0.386s  gcc -O3 -Wall
OCaml2  0.089s    0.391s  ocamlopt
OCaml2  0.010s   10.111s  ocamlc
Java    1.615s   12.745s  javac

Again, OCaml is basically as fast as C. Note that C and OCaml get slower
moving to 64-bit but Java gets >7x faster. Amazingly, OCaml's interpreted
bytecode is faster than Java on 32-bit, whilst being >160x faster to
compile!

Here's my latest OCaml (I think we could revert to the simpler list-based
permuter because no significant time is spent generating the permutations):

let rec fact n = if n=0 then 1 else n*fact(n-1)

let size = 5

(* 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

let n = fact size

(* Permutations *)
let perms = Array.init n (fun _ -> ignore(gen_perm()); Array.copy p)

let incompat =
  let rec aux (px : int array) py i =
    i<size && (px.(i) = py.(i) || aux px py (i+1)) in
  Array.init n (fun x -> Array.init n (fun y -> aux perms.(x) perms.(y) 0))

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)) ':'

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
    end else
    for latest = 0 to n - 1 do
      let prev_row = ref 0 in
      let incompat = incompat.(latest) in
      while !prev_row < row && not incompat.(board.(!prev_row)) do
        incr prev_row;
      done;
      if !prev_row = row then begin
          board.(row) <- latest;
          add_a_row (row + 1)
        end
      done

let () =
  op.[size*(size+1)-1] <- '\n';
  add_a_row 0

-- 
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists