From: Jon Harrop <jon@...>
Date: 2006-08-03T13:30:04+09:00
Subject: Re: For performance, write it in OCaml

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"
    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 () = add_a_row 0

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