micro bench compare List's split to a tail recursive version

split_bench.ml

let bench n size split =
  let plist =
    let rec loop acc i v =
      if i = 0
      then acc
      else
        let acc' = (v, string_of_int v ) :: acc in
        loop acc' (i-1) (v+1)
    in
    loop [] size 0
  in
  let rec loop i =
    if i = 0
    then ()
    else
      let _ = split plist in
      loop (i-1)
  in
  loop n





let rev_split xys =
  let rec helper xs ys = function
    | [] -> xs, ys
    | (x, y) :: xys -> helper (x :: xs) (y :: ys) xys
  in
  helper [] [] xys

let split xys = rev_split (List.rev xys)

let split0 = List.split
let split1 = split

let measure f =
  let t0 = Unix.gettimeofday() in
  let _ = f () in
  let t1 = Unix.gettimeofday () in
  t1 -. t0

let () =
  let n = 1_000_000 in
  let sizes= [
      0;
      1; 2; 3;4;5;6;7;8;9;
      10;20;30;40;50;60;70;80;90;
      100;200;300;400;500;600;700;800;900;
      1000;
      10_000;
    ]
  in
  Printf.printf "n=%i\n%!" n;
  List.iter
  (fun size ->
    let took0 = measure (fun () -> bench n size split0) in
    let took1 = measure (fun () -> bench n size split1) in
    let slowdown = took1 /. took0 in
    Printf.printf "size:%5i took0:%f took1:%f => %f \n%!"
                  size took0 took1 slowdown
  ) sizes

test run

$ ocamlopt -version
4.03.0

$ ocamlbuild -use-ocamlfind ./split_bench.native 

$ cat /proc/cpuinfo | grep 'model name' | uniq
model name	: Intel(R) Core(TM) i7-4712HQ CPU @ 2.30GHz

$ ./split_bench.native 
n=1000000
size:    0 took0:0.003356 took1:0.005395 => 1.607559 
size:    1 took0:0.008595 took1:0.007489 => 0.871318 
size:    2 took0:0.014872 took1:0.014498 => 0.974847 
size:    3 took0:0.020168 took1:0.021099 => 1.046151 
size:    4 took0:0.026808 took1:0.030244 => 1.128174 
size:    5 took0:0.033154 took1:0.036501 => 1.100951 
size:    6 took0:0.038851 took1:0.043425 => 1.117733 
size:    7 took0:0.043938 took1:0.048645 => 1.107131 
size:    8 took0:0.048151 took1:0.056677 => 1.177065 
size:    9 took0:0.052771 took1:0.063931 => 1.211477 
size:   10 took0:0.057505 took1:0.071175 => 1.237722 
size:   20 took0:0.115656 took1:0.147330 => 1.273865 
size:   30 took0:0.174865 took1:0.219774 => 1.256821 
size:   40 took0:0.229131 took1:0.297706 => 1.299284 
size:   50 took0:0.287679 took1:0.366683 => 1.274626 
size:   60 took0:0.356239 took1:0.443940 => 1.246185 
size:   70 took0:0.404517 took1:0.516168 => 1.276010 
size:   80 took0:0.464314 took1:0.589174 => 1.268913 
size:   90 took0:0.528787 took1:0.672784 => 1.272316 
size:  100 took0:0.604778 took1:0.743283 => 1.229018 
size:  200 took0:1.222571 took1:1.545418 => 1.264072 
size:  300 took0:2.000342 took1:2.350935 => 1.175266 
size:  400 took0:2.836740 took1:3.314231 => 1.168324 
size:  500 took0:3.565816 took1:4.309448 => 1.208545 
size:  600 took0:4.383300 took1:5.187488 => 1.183466 
size:  700 took0:5.228268 took1:6.240582 => 1.193623 
size:  800 took0:6.481171 took1:7.205253 => 1.111721 
size:  900 took0:7.375133 took1:8.188928 => 1.110343 
size: 1000 took0:8.192356 took1:9.400132 => 1.147427 
size:10000 took0:269.092346 took1:269.189064 => 1.000359