From c071218d76c5dc637a90886742a6eaede31ee7c2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Rapha=C3=ABl=20Cauderlier?=
 <raphael.cauderlier@nomadic-labs.com>
Date: Mon, 9 Jan 2023 16:25:50 +0100
Subject: [PATCH 1/2] Lib_benchmarks: add a sampler for floats

---
 src/lib_benchmark/base_samplers.ml  | 5 +++++
 src/lib_benchmark/base_samplers.mli | 6 ++++++
 2 files changed, 11 insertions(+)

diff --git a/src/lib_benchmark/base_samplers.ml b/src/lib_benchmark/base_samplers.ml
index ad0e2ecc92b1..cb4809060a45 100644
--- a/src/lib_benchmark/base_samplers.ml
+++ b/src/lib_benchmark/base_samplers.ml
@@ -42,6 +42,11 @@ let sample_in_interval ~range:{min; max} state =
   if max - min >= 0 then min + Random.State.int state (max - min + 1)
   else invalid_arg "Base_samplers.sample_in_interval"
 
+let sample_float_in_interval ~min ~max state =
+  let diff = max -. min in
+  if diff > 0. then min +. Random.State.float state diff
+  else invalid_arg "Base_samplers.sample_float_in_interval"
+
 let uniform_bool = Random.State.bool
 
 let uniform_byte state = Char.chr (Random.State.int state 256)
diff --git a/src/lib_benchmark/base_samplers.mli b/src/lib_benchmark/base_samplers.mli
index 366555968155..a37a5fabd169 100644
--- a/src/lib_benchmark/base_samplers.mli
+++ b/src/lib_benchmark/base_samplers.mli
@@ -38,6 +38,12 @@ val range_encoding : range Data_encoding.t
  *)
 val sample_in_interval : range:range -> int sampler
 
+(** [sample_float_in_interval ~min ~max] creates a sampler in the
+    specified interval.
+    @raise Invalid_argument if [max <= min].
+*)
+val sample_float_in_interval : min:float -> max:float -> float sampler
+
 (** Samples a boolean uniformly at random *)
 val uniform_bool : bool sampler
 
-- 
GitLab


From 308fd3079c3168f40c8d4875e3f2d05075ff588c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Rapha=C3=ABl=20Cauderlier?=
 <raphael.cauderlier@nomadic-labs.com>
Date: Mon, 9 Jan 2023 16:31:38 +0100
Subject: [PATCH 2/2] Snoop,Scoru: Uniform sample of the log of the skip list
 len

This commit updates the samplers used for the benchmarks of the skip
list data structure used in Smart Rollups. The models of the
operations on this data structure are logarithmic but the previous
samplers were uniform in the length (in some interval). Because of
this, during the linear inference of the model, very few points of
small abscissa were available and this degraded the precision of the
inferred gas parameters.

To solve this, we now sample the logarithm of the size uniformly
instead of the size itself.
---
 .../skip_list_benchmarks.ml                   | 22 +++++++++++++------
 1 file changed, 15 insertions(+), 7 deletions(-)

diff --git a/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml b/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
index 7efce6c2a750..a74bc9df4045 100644
--- a/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
+++ b/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
@@ -78,9 +78,14 @@ module Next : Benchmark.S = struct
   let create_benchmarks ~rng_state ~bench_num ({max_items} : config) =
     List.repeat bench_num @@ fun () ->
     let workload =
-      Base_samplers.sample_in_interval
-        rng_state
-        ~range:{min = 0; max = max_items}
+      (* Since the model we want to infer is logarithmic in
+         the length, we sample the logarithm of the length
+         (and not the length itself) uniformly in an interval. *)
+      let logmax = log (float_of_int max_items) in
+      let loglen =
+        Base_samplers.sample_float_in_interval ~min:0. ~max:logmax rng_state
+      in
+      int_of_float (exp loglen)
     in
     let prev_cell = create_skip_list_of_len workload in
     let prev_cell_ptr = () in
@@ -144,11 +149,14 @@ module Hash_cell = struct
   let models = [("skip_list_hash", hash_skip_list_cell_model)]
 
   let benchmark rng_state conf () =
-    let skip_list_len =
-      Base_samplers.sample_in_interval
-        ~range:{min = 1; max = conf.max_index}
-        rng_state
+    (* Since the model we want to infer is logarithmic in
+       the length, we sample the logarithm of the length
+       (and not the length itself) uniformly in an interval. *)
+    let skip_list_loglen =
+      let logmax = log (float_of_int conf.max_index) in
+      Base_samplers.sample_float_in_interval ~min:0. ~max:logmax rng_state
     in
+    let skip_list_len = int_of_float (exp skip_list_loglen) in
     let random_hash () =
       Hash.hash_string
         [Base_samplers.string ~size:{min = 32; max = 32} rng_state]
-- 
GitLab