assoc_timing.ml

(*
 * ocamlbuild -pkg unix assoc_timing.native
 *
 * When visiting all keys in an association list, when does it
 * make sense to build a map first? According to this,
 * building the map is amortised for list longer than 20 to 30
 * elements.
 *)

module Int = struct
  type t = int
  let compare (x:int) (y:int) = compare x y
end
module IntMap = Map.Make(Int)

let seq n =
  let rec loop acc = function
    | 0 -> acc
    | n -> loop (n::acc) (n-1)
  in
  loop [] n

let data n =
  seq n
  |> List.map (fun n -> (n, Random.int n))
  |> List.sort (fun (_,y1) (_,y2) -> compare y1 y2)

let map_of pairs =
  let add map (k,v) = IntMap.add k v map in
  List.fold_left add IntMap.empty pairs

let elapsed f =
  let before  = Unix.gettimeofday () in
  let ()      = f () |> ignore in
  let after   = Unix.gettimeofday () in
  after -. before

let rec repeat n f = match n with
  | 0 -> ()
  | n -> f (); repeat (n-1) f

let visit keys data =
  List.iter (fun key -> List.assoc key data |> ignore) keys

let visit' keys data =
  let map   = map_of data in
  List.iter (fun key -> IntMap.find key map |> ignore) keys

let run n =
  let keys  = seq n in
  let assoc = data n in
  let timed f =
    elapsed (fun () -> repeat 10000 @@ fun () -> f keys assoc) in
  let t  = timed visit in
  let t' = timed visit' in
  ( Printf.printf "%5fs List.assoc\n" t
  ; Printf.printf "%5fs Map.find\n" t'
  )

let main () =
  let argv = Array.to_list Sys.argv in
  let this = Sys.executable_name in
  let () = Random.init 0 in
  match argv with
  |[_;n] -> run (int_of_string n)
  | _    -> Printf.eprintf "usage: %s n\n" this

let () = if !Sys.interactive then () else main ()