Compare performance of filtering on list and arrays in OCaml

bench_filter_list_array.ml

let rec loop a f len n i =
  if i < len then
    let x = Array.unsafe_get a i in
    if f x then begin
      let res = loop a f len (n + 1) (i + 1) in
      Array.unsafe_set res n x;
      res
    end else
      loop a f len n (i + 1)
  else
    Array.make n (Array.unsafe_get a 0)

let filter_a f a =
  let len = Array.length a in
  if len = 0 then a else
  loop a f len 0 0

let filter_l f l =
  let rec loop = function
    | x::xs when f x -> x::loop xs
    | _::xs -> loop xs
    | [] -> []
  in
  loop l

let big_l n =
  let rec loop i =
    if i = n then []
    else i::loop (i+1)
  in loop 1

let get_time n f =
  Gc.compact ();
  let t = Unix.gettimeofday () in
  for _i = 1 to n do
    ignore (f ())
  done;
  let t2 = Unix.gettimeofday () in
  Gc.compact ();
  t2 -. t

let () =
  List.iter
    (fun n ->
       let big_l = big_l n in
       let big_a = Array.of_list big_l in
       let niters = 400000000 / n in
       let t_l = get_time niters (fun () -> filter_l (fun x -> x mod 2 = 0) big_l) in
       let t_a = get_time niters (fun () -> filter_a (fun x -> x mod 2 = 0) big_a) in
       Printf.printf "% 7i   | %.02f  | %.02f | %.02f\n%!" n t_l t_a (100. *. ((t_a /. t_l) -. 1.))
    )
    [10; 100; 1_000; 10_000; 100_000; 500_000]