Skip to content

Instantly share code, notes, and snippets.

@jj-issuu
Last active June 14, 2023 21:20
Show Gist options
  • Save jj-issuu/8caa9ed31b2f689af96d to your computer and use it in GitHub Desktop.
Save jj-issuu/8caa9ed31b2f689af96d to your computer and use it in GitHub Desktop.
Benchmark interpreters written in OCaml
(*
* 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)
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment