combine_bench.ml

let bench n size combine =
  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 _ = combine plist plist in
      loop (i-1)
  in
  loop n

let rev_combine l1 l2 =
  let rec helper xys xs ys =
    match xs, ys with
    | [], [] -> xys
    | x :: xs, y :: ys -> helper ((x, y) :: xys) xs ys
    | _, _ -> invalid_arg "List.rev_combine"
  in
  helper [] l1 l2

let rev_combine_unrolled l1 l2 =
  let rec helper xys xs ys =
    match xs,ys with
    | x0 :: x1 :: x2 :: x3 :: xs,
      y0 :: y1 :: y2 :: y3 :: ys ->
       helper ((x3,y3) :: (x2, y2) :: (x1, y1) :: (x0, y0) :: xys) xs ys
    | x0 :: x1 :: x2 :: xs,
      y0 :: y1 :: y2 :: ys ->
       helper ((x2, y2) :: (x1, y1) :: (x0, y0) :: xys) xs ys
    | x0 :: x1 :: xs,
      y0 :: y1 :: ys ->
       helper ((x1,y1):: (x0, y0) :: xys) xs ys
    | x :: xs,
      y :: ys ->
       helper ((x, y) :: xys) xs ys
    | [], [] -> xys
    | _, _ -> invalid_arg "List.rev_combine"
  in
  helper [] l1 l2

let combine l1 l2 = rev_combine l1 l2 |> List.rev

let combine0 = List.combine
let combine1 = combine
let combine2 l1 l2 = rev_combine_unrolled l1 l2 |> List.rev

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 combine0) in
    let took1 = measure (fun () -> bench n size combine1) in
    let took2 = measure (fun () -> bench n size combine2) in
    let slowdown1 = took1 /. took0 in
    let slowdown2 = took2 /. took0 in
    Printf.printf "size:%5i took0:%1.4f took1:%1.4f took2:%1.4f => %1.4f %1.4f\n%!"
                  size
                  took0 took1 took2
                  slowdown1 slowdown2
  ) sizes

output

$ ocamlopt -version
4.04.0

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

$ ./combine_bench.native 
n=1000000
size:    0 took0:0.0056 took1:0.0090 took2:0.0051 => 1.6076 0.9073
size:    1 took0:0.0078 took1:0.0084 took2:0.0085 => 1.0751 1.0819
size:    2 took0:0.0126 took1:0.0137 took2:0.0118 => 1.0806 0.9324
size:    3 took0:0.0177 took1:0.0183 took2:0.0175 => 1.0356 0.9891
size:    4 took0:0.0239 took1:0.0264 took2:0.0231 => 1.1044 0.9652
size:    5 took0:0.0297 took1:0.0360 took2:0.0309 => 1.2099 1.0404
size:    6 took0:0.0352 took1:0.0395 took2:0.0325 => 1.1239 0.9248
size:    7 took0:0.0410 took1:0.0467 took2:0.0393 => 1.1409 0.9590
size:    8 took0:0.0460 took1:0.0544 took2:0.0455 => 1.1833 0.9884
size:    9 took0:0.0510 took1:0.0615 took2:0.0528 => 1.2049 1.0339
size:   10 took0:0.0557 took1:0.0680 took2:0.0553 => 1.2205 0.9929
size:   20 took0:0.1118 took1:0.1377 took2:0.1071 => 1.2316 0.9581
size:   30 took0:0.1692 took1:0.2225 took2:0.1693 => 1.3146 1.0005
size:   40 took0:0.2201 took1:0.2836 took2:0.2281 => 1.2881 1.0361
size:   50 took0:0.2737 took1:0.3585 took2:0.2732 => 1.3098 0.9982
size:   60 took0:0.3329 took1:0.4536 took2:0.3381 => 1.3624 1.0155
size:   70 took0:0.3903 took1:0.4895 took2:0.3850 => 1.2543 0.9866
size:   80 took0:0.4448 took1:0.5670 took2:0.4170 => 1.2748 0.9375
size:   90 took0:0.5023 took1:0.6469 took2:0.4972 => 1.2879 0.9898
size:  100 took0:0.5681 took1:0.7276 took2:0.5512 => 1.2809 0.9704
size:  200 took0:1.1460 took1:1.4841 took2:1.1449 => 1.2951 0.9990
size:  300 took0:1.7664 took1:2.2844 took2:1.8540 => 1.2932 1.0495
size:  400 took0:2.4592 took1:3.1950 took2:2.7327 => 1.2992 1.1112
size:  500 took0:3.2117 took1:4.1394 took2:3.6473 => 1.2888 1.1356
size:  600 took0:4.1815 took1:5.1876 took2:4.4646 => 1.2406 1.0677
size:  700 took0:4.9606 took1:6.1555 took2:5.3778 => 1.2409 1.0841
size:  800 took0:5.5924 took1:7.0372 took2:6.4863 => 1.2583 1.1598
size:  900 took0:6.3113 took1:8.4239 took2:7.6055 => 1.3347 1.2051
size: 1000 took0:7.1607 took1:9.5432 took2:8.7544 => 1.3327 1.2226
size:10000 took0:177.1536 took1:218.1006 took2:219.3043 => 1.2311 1.2379