Add Util.generate_push_and_pop_sequence for benchmarking queues

polytypic · polytypic · commit df392866622e · 2024-01-16T11:15:02.000+02:00
diff --git a/lib/multicore_bench.mli b/lib/multicore_bench.mli
@@ -63,4 +63,14 @@ module Util : sig
     ?rate:Rate.t ->
     Times.t ->
     Yojson.Safe.t list
+
+  module Bits : sig
+    type t
+
+    val create : unit -> t
+    val push : t -> bool -> unit
+    val iter : (bool -> unit) -> t -> unit
+  end
+
+  val generate_push_and_pop_sequence : ?state:Random.State.t -> int -> Bits.t
 end
diff --git a/lib/util.ml b/lib/util.ml
@@ -32,3 +32,57 @@ let thruput_metrics ~n ~singular ?(plural = singular ^ "s") ~config
            ~description:(Printf.sprintf "Total number of %s processed" plural)
            ~units:(Rate.to_mnemonic rate);
     ]
+
+module Bits = struct
+  type t = { mutable bytes : Bytes.t; mutable length : int }
+
+  let create () = { bytes = Bytes.create 1; length = 0 }
+
+  let push t bool =
+    let capacity = Bytes.length t.bytes lsl 3 in
+    if t.length == capacity then
+      t.bytes <- Bytes.extend t.bytes 0 (capacity lsr 3);
+    let byte_i = t.length lsr 3 in
+    let mask = 1 lsl (t.length land 7) in
+    t.length <- t.length + 1;
+    let byte = Char.code (Bytes.unsafe_get t.bytes byte_i) in
+    let byte = if bool then byte lor mask else byte land lnot mask in
+    Bytes.unsafe_set t.bytes byte_i (Char.chr byte)
+
+  let length t = t.length
+
+  let rec iter fn t i =
+    let n = t.length in
+    if i < n then begin
+      let byte = Char.code (Bytes.unsafe_get t.bytes (i lsr 3)) in
+      fn (0 <> byte land 1);
+      if i + 1 < n then fn (0 <> byte land 2);
+      if i + 2 < n then fn (0 <> byte land 4);
+      if i + 3 < n then fn (0 <> byte land 8);
+      if i + 4 < n then fn (0 <> byte land 16);
+      if i + 5 < n then fn (0 <> byte land 32);
+      if i + 6 < n then fn (0 <> byte land 64);
+      if i + 7 < n then fn (0 <> byte land 128);
+      iter fn t (i + 8)
+    end
+
+  let iter fn t = iter fn t 0
+end
+
+let generate_push_and_pop_sequence ?(state = Random.State.make_self_init ())
+    n_msgs =
+  let bits = Bits.create () in
+  let rec loop length n_push n_pop =
+    if 0 < n_push || 0 < n_pop then begin
+      let push = Random.State.bool state && 0 < n_push in
+      Bits.push bits push;
+      loop
+        (if push then length + 1 else if 0 < length then length - 1 else length)
+        (n_push - Bool.to_int push)
+        (n_pop - Bool.to_int ((not push) && 0 < length))
+    end
+    else length
+  in
+  let length = loop 0 n_msgs n_msgs in
+  assert (length = 0);
+  bits
