Benchmark interpreters written in OCaml

eval.ml

(*
 * opam install bench
 * ocamlfind ocamlopt -package unix,bench -linkpkg eval.ml && ./a.out
 *)

type binop = Add | Sub | Mul | Div

type expr =
  | Const of int
  | VarX
  | Neg of expr
  | Binop of binop * expr * expr

let string_of_binop = function
  | Add -> "+"
  | Sub -> "-"
  | Mul -> "*"
  | Div -> "/?"

let rec string_of_expr = function
  | Const n -> Printf.sprintf (if n < 0 then "(%d)" else "%d") n
  | VarX -> "x"
  | Neg e -> Printf.sprintf "(-%s)" (string_of_expr e)
  | Binop (binop, e1, e2) ->
      Printf.sprintf "(%s %s %s)"
        (string_of_expr e1) (string_of_binop binop) (string_of_expr e2)

let (/?) = fun x y -> if y = 0 then x else x / y

let eval_binop = function
  | Add -> (+)
  | Sub -> (-)
  | Mul -> ( * )
  | Div -> (/?)

let rec eval e x =
  match e with
  | Const n -> n
  | VarX -> x
  | Neg e -> - eval e x
  | Binop (binop, e1, e2) ->
      (eval_binop binop) (eval e1 x) (eval e2 x)

let rec partial = function
  | Const n -> fun _ -> n
  | VarX -> fun x -> x
  | Neg e -> let f = partial e in fun x -> - f x
  | Binop (binop, e1, e2) ->
      let f_binop = eval_binop binop in
      let f1 = partial e1 in
      let f2 = partial e2 in
      fun x -> f_binop (f1 x) (f2 x)

let rec random_expr deeper_chance =
  if Random.float 1.0 <= deeper_chance then (
    match Random.int 5 with
    | 0 -> Neg (random_expr deeper_chance)
    | n ->
        let e1 = random_expr (0.92 *. deeper_chance) in
        let e2 = random_expr (0.92 *. deeper_chance) in
        let binop =
          match n with
          | 1 -> Add
          | 2 -> Sub
          | 3 -> Mul
          | 4 -> Div
          | _ -> failwith "random_expr: impossible"
        in
        Binop (binop, e1, e2)
  ) else (
    match Random.bool () with
    | false -> Const (Random.int 1000)
    | true -> VarX
  )

(** Evaluate constant subexpressions and collapse double negations. We do this to make sure the
 * compiled version of the code doesn't seem faster just because the OCaml compiler does this. If
 * the OCaml compiler rewrites by other arithmetic identities, we ought to do that here too. *)
let rec simplify = function
  | Const n -> Const n
  | VarX -> VarX
  | Neg e ->
      begin match simplify e with
      | Const n -> Const (-n)
      | Neg e' -> e'
      | e -> Neg e
      end
  | Binop (binop, e1, e2) ->
      begin match simplify e1, simplify e2 with
      | Const n1, Const n2 -> Const (eval_binop binop n1 n2)
      | e1, e2 -> Binop (binop, e1, e2)
      end

let compiled = fun x ->
  (((2040 /? (248 - ((990 /? x) * ((x /? x) - (x + x))))) + (((x + (x - (((x + 262) + (910 /? x)) * x))) + ((870 + (x + 226000)) + ((x /? (325 + x)) /? ((x - 437) - 988)))) * 23)) /? ((-(((710 - (x /? (-34176))) /? (247 + x)) - ((-x) * (-((-(1156 - (((x - x) * 33) /? 651))) + x))))) * (((-(x - x)) * ((-((x /? (-((x + (x /? 23)) * 557))) /? (643 - (((-x) + 109) /? 588)))) /? (((150 * (80 /? (x + x))) * 476) * (x * 334)))) /? 262)))

let () =
  Random.init 1;
  let e = simplify (random_expr 1.0) in
  Printf.printf "let compiled = %s\n%!" (string_of_expr e);
  let after_partial = partial e in
  (* Check that all implementations compute the same result. *)
  for x = 0 to 9999 do
    let n = eval e x in
    assert (after_partial x = n);
    assert (compiled x = n);
  done;
  (* Benchmark using the 'bench' package available in opam. *)
  Bench.bench [
    "eval", (fun () ->
      for x = 0 to 9999 do ignore (eval e x) done
    );
    "partial", (fun () ->
      for x = 0 to 9999 do ignore (after_partial x) done
    );
    "partial, fully applied", (fun () ->
      for x = 0 to 9999 do ignore (partial e x) done
    );
    "compiled", (fun () ->
      for x = 0 to 9999 do ignore (compiled x) done
    );
  ]

(*
compiled (1.25 ms) is 71.1% faster than
partial (4.33 ms) which is 25.7% faster than
eval (5.83 ms) which is 44.2% faster than
partial, fully applied (10.45 ms)
*)