bench! bench! bench!

Skew Binary Random-Access Lists - komamitsu.logのベンチマークをとりたいなぁ、と思っていたところ、OCamlにBenchmarkというそのものズバリなライブラリがあったので試してみました。

# ちなみに件のコードは MIT License に.

aptでのインストールは以下

$sudo aptitude install libbenchmark-ocaml-dev

で、ベンチマーク用のコードは以下. List, Array, Skew binary random access listでランダムアクセスさせまくりです。

let max_size = 1000000

let rec loop f n ac =
  if n <= 0 then ac else loop f (n - 1) (f n ac)

let normal_list =
  loop (fun x l -> x::l) max_size []

module RList = SkewBinaryRandomAccessList
let skew_binary_rlist =
  loop (fun x l -> RList.cons x l) max_size RList.empty

let normal_array = 
  Array.init max_size (fun i -> i)

let _ = Random.self_init ()
let rand () = Random.int (max_size - 1)
let bench_list i = List.nth normal_list i
let bench_rlist i = RList.lookup i skew_binary_rlist
let bench_array i = normal_array.(i)

let _ =
  let res = Benchmark.latencyN 1000 [
    ("normal list   ", bench_list, rand ()); 
    ("skew bin rlist", bench_rlist, rand ());
    ("normal array  ", bench_array, rand ())
  ] in
  Benchmark.tabulate res

で、これをコンパイル.

ocamlfind c -package benchmark -linkpkg -o bench skewBinaryRandomAccessList.cmo bench.ml

さて、いよいよ実行です。

komamitsu@potato:~/git/ocaml-skew-binary-random-access-list$ ./bench 
Latencies for 1000 iterations of normal list   , skew bin rlist, normal array  :
normal list   : 83 WALL (66.46 usr +  0.22 sys = 66.68 CPU) @ 15.00/s (n=1000)
skew bin rlist:  0 WALL ( 0.01 usr +  0.00 sys =  0.01 CPU) @ 125000.00/s (n=1000)
            (warning: too few iterations for a reliable count)
normal array  :  0 WALL ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)
                               Rate       normal list      skew bin rlist normal array  
normal list                  15.0/s                   --            -100%          -100%
skew bin rlist             125000/s              833352%               --          -100%
normal array   999999999999999872/s 6667616699999998976% 799999999999556%             --

やはり、Array > SkewBinaryRandomAccessList > List という性能差がはっきり出ているなぁ。

Listを除いて、さらに負荷をかけてみる(n = 3000000)と…

Latencies for 1000000 iterations of skew bin rlist, normal array  :
skew bin rlist: 10 WALL ( 9.57 usr +  0.04 sys =  9.61 CPU) @ 104030.12/s (n=1000000)
normal array  :  0 WALL ( 0.02 usr +  0.00 sys =  0.02 CPU) @ 49997500.12/s (n=1000000)
            (warning: too few iterations for a reliable count)
                     Rate skew bin rlist normal array
skew bin rlist   104030/s             --          -100%
normal array   49997500/s         47961%             --

n = 3000000 なので、Array = O(1), SkewBinaryRandomAccessList = O(min(i, log(n)), List = O(n) の最悪の場合の計算量をざっくり見積もると、それぞれ 1, 15, 3000000位。

う〜ん、それよりも実測値のほうが差が大きい気がするなぁ。
まぁ、やっぱりArrayは速いし、SkewBinaryRandomAccessListもそこそこ速い。