immutable-chunkmap 2.1.2

A fast immutable map and set with batch insert and update methods, COW operations, and big O efficient implementations of set and merge operations
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

open Core

let min_iter = 1_000_000

let random_string () =
  let size = 32 in
  let s = Bytes.create size in
  for i = 0 to size - 1 do
    let c = Option.value_exn (Char.of_int (Random.int 254)) in
    Bytes.set s i c;
  done;
  Bytes.to_string s

let random_array size mk k =
  let s = Hash_set.create ~size k in
  while Hash_set.length s < size do
    Hash_set.add s (mk ())
  done;
  Hash_set.to_array s

let bench_add cmp k v =
  let kv = Option.value_exn (Array.zip k v) in
  let st = Time_float.now () in
  let m =
    Array.fold kv ~init:(Map.empty cmp)
      ~f:(fun m (k, v) -> Map.set m ~key:k ~data:v)
  in
  let en = Time_float.now () in
  (m, Time_float.diff en st)

let bench_find m k =
  let st = Time_float.now () in
  let i = ref 0 in
  let len = Array.length k in
  let iter = Int.max len min_iter in
  while !i < iter do
    assert (Option.is_some (Map.find m (Array.unsafe_get k (!i mod len))));
    incr i
  done;
  let en = Time_float.now () in
  Time_float.diff en st

let bench_remove m k =
  let st = Time_float.now () in
  let m = Array.fold k ~init:m ~f:(fun m k -> Map.remove m k) in
  if Map.length m <> 0 then failwith "remove is broken";
  let en = Time_float.now () in
  Time_float.diff en st

let () =
  let args = Sys.get_argv () in
  let size =
    if Array.length args = 4 then Int.of_string args.(3)
    else begin
      printf "usage: test <unused> <kind> <size>\n%!";
      exit 0
    end
  in
  let str t sz = sprintf "%g" (Time_float.Span.to_ns t /. float sz) in
  match args.(2) with
    "ptr" -> begin
      let mk () = Random.int Int.max_value in
      let k = random_array size mk (module Int) in
      let ks = random_array size mk (module Int) in
      let v = random_array size mk (module Int) in
      Array.sort ~compare:Int.compare ks;
      let (m, add) = bench_add (module Int) k v in
      let (_, adds) = bench_add (module Int) ks v in
      let find = bench_find m k in
      let rm = bench_remove m k in
      printf "%d,%s,%s,%s,%s,%s,%s\n%!"
        size (str add size) (str adds size) "0."
        (str find (Int.max min_iter size)) "0" (str rm size)
    end
  | "str" -> begin
      let k = random_array size random_string (module String) in
      let ks = random_array size random_string (module String) in
      let v = random_array size random_string (module String) in
      Array.sort ~compare:String.compare ks;
      let (m, add) = bench_add (module String) k v in
      let (_, adds) = bench_add (module String) ks v in
      let find = bench_find m k in
      let rm = bench_remove m k in
      printf "%d,%s,%s,%s,%s,%s,%s\n%!"
        size (str add size) (str adds size) "0."
        (str find (Int.max min_iter size)) "0" (str rm size)
    end
  | _ -> failwith "invalid kind. Allowed kinds: [ptr, str]"