Source file carbonated_map_costs.ml

(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2022 Trili Tech, <contact@trili.tech>                       *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

module S = Saturation_repr
open Gas_limit_repr

type cost = Saturation_repr.may_saturate Saturation_repr.t

(** This is a good enough approximation *)
let log2 x = S.safe_int (1 + S.numbits x)

(** Collect benchmark from [Carbonated_map_benchmarks.Find_benchmark].

    The model is similar to the gas model as from [Michelson_v1_gas.map_get].
    The user is responsible for providing the [compare_key_cost] which depends
    on the size of the [key]. See [Carbonated_map_benchmarks.Find_benchmark] for
    an example.
    The rational for the model is:
    - [intercept] is for paying a fixed cost regardless of size.
    - [compare_key_cost] is for the log2 of steps comparing keys
    - [traversal_overhead] is for the overhead of log2 steps walking the tree
 *)
let find_cost ~compare_key_cost ~size =
  let intercept = S.safe_int 50 in
  let size = S.safe_int size in
  let compare_cost = log2 size *@ compare_key_cost in
  let traversal_overhead = log2 size *@ S.safe_int 2 in
  intercept +@ compare_cost +@ traversal_overhead

(**
    Modelling the precise overhead of update compared with [find] is tricky.
    The cost of [find] depends on the cost of comparing keys. When the tree
    is recreated, after looking up the element, this cost is no longer a factor.
    On the other hand, if the old map is no longer used, some nodes are going to
    be garbage collected at a later stage which incurs an extra cost.

    We here use the same model as in [Michelson_v1_gas.map_update]. That is
    providing an overestimate by doubling the cost of [find].
  *)
let update_cost ~compare_key_cost ~size =
  S.safe_int 2 *@ find_cost ~compare_key_cost ~size

(** Collect benchmark from [Carbonated_map_benchmarks.Fold_benchmark].

    The cost of producing a list of elements is linear in the size of the map
    and does not depend on the size of the elements nor keys.
*)
let fold_cost ~size = S.safe_int 50 +@ (S.safe_int 24 *@ S.safe_int size)