Skip to content

Instantly share code, notes, and snippets.

@jj-issuu jj-issuu/eval.ml
Last active Aug 29, 2015

Embed
What would you like to do?
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.