split bench 2

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 rev_split_unrolled xys =
  let rec helper xs ys = function
    | (x0,y0) :: (x1, y1) :: (x2, y2) :: (x3, y3) :: xys ->
       helper
         (x3 :: x2 :: x1 :: x0 :: xs)
         (y3 :: y2 :: y1 :: y0 :: ys)
         xys
    | (x0,y0) :: (x1, y1) :: (x2, y2) :: xys ->
       helper
         (x2 :: x1 :: x0 :: xs)
         (y2 :: y1 :: y0 :: ys)
         xys
    | (x0,y0) :: (x1,y1) :: xys ->
       helper
         (x1 :: x0 :: xs)
         (y1 :: y0 :: ys)
         xys
    | (x, y) :: xys ->
       helper
         (x :: xs)
         (y :: ys) xys
    | [] -> xs, ys

  in
  helper [] [] xys

let split_unrolled xys = rev_split_unrolled (List.rev xys)

let split0 = List.split
let split1 = split
let split2 = split_unrolled

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 took2 = measure (fun () -> bench n size split2) 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

test_output.txt

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

./split_bench.native 
n=1000000
size:    0 took0:0.0035 took1:0.0059 took2:0.0057 => 1.6592 1.6131 
size:    1 took0:0.0089 took1:0.0084 took2:0.0089 => 0.9448 0.9974 
size:    2 took0:0.0161 took1:0.0160 took2:0.0143 => 0.9930 0.8862 
size:    3 took0:0.0213 took1:0.0229 took2:0.0183 => 1.0748 0.8578 
size:    4 took0:0.0266 took1:0.0287 took2:0.0209 => 1.0775 0.7847 
size:    5 took0:0.0329 took1:0.0355 took2:0.0262 => 1.0795 0.7972 
size:    6 took0:0.0391 took1:0.0433 took2:0.0346 => 1.1085 0.8856 
size:    7 took0:0.0439 took1:0.0496 took2:0.0376 => 1.1291 0.8548 
size:    8 took0:0.0484 took1:0.0589 took2:0.0417 => 1.2158 0.8605 
size:    9 took0:0.0530 took1:0.0646 took2:0.0479 => 1.2191 0.9038 
size:   10 took0:0.0588 took1:0.0716 took2:0.0543 => 1.2175 0.9229 
size:   20 took0:0.1222 took1:0.1459 took2:0.1111 => 1.1938 0.9094 
size:   30 took0:0.1915 took1:0.2309 took2:0.1782 => 1.2055 0.9305 
size:   40 took0:0.2465 took1:0.3059 took2:0.2210 => 1.2411 0.8965 
size:   50 took0:0.3214 took1:0.3761 took2:0.3377 => 1.1699 1.0505 
size:   60 took0:0.4367 took1:0.4557 took2:0.3439 => 1.0435 0.7874 
size:   70 took0:0.4227 took1:0.5363 took2:0.3967 => 1.2689 0.9385 
size:   80 took0:0.4881 took1:0.6040 took2:0.4720 => 1.2374 0.9670 
size:   90 took0:0.5514 took1:0.6760 took2:0.5234 => 1.2259 0.9490 
size:  100 took0:0.6168 took1:0.7690 took2:0.5769 => 1.2468 0.9353 
size:  200 took0:1.2960 took1:1.5921 took2:1.2287 => 1.2285 0.9480 
size:  300 took0:2.0224 took1:2.4170 took2:1.8763 => 1.1951 0.9278 
size:  400 took0:2.9768 took1:3.4802 took2:2.6715 => 1.1691 0.8974 
size:  500 took0:4.0135 took1:4.3939 took2:3.9207 => 1.0948 0.9769 
size:  600 took0:4.5230 took1:5.3714 took2:4.5224 => 1.1876 0.9998 
size:  700 took0:6.7124 took1:6.7449 took2:5.5593 => 1.0048 0.8282 
size:  800 took0:6.5634 took1:7.7166 took2:6.3653 => 1.1757 0.9698 
size:  900 took0:7.6115 took1:9.1136 took2:7.2905 => 1.1973 0.9578 
size: 1000 took0:9.5431 took1:9.7274 took2:8.3694 => 1.0193 0.8770 
size:10000 took0:279.0343 took1:264.3891 took2:245.5903 => 0.9475 0.8801