Module Mavryk_benchmark.Model

type (_, _, _) arity =
  1. | Zero_arity : ('elt, 'elt, unit) arity
  2. | Succ_arity : ('elt, 'b, 'a) arity -> ('elt, 'elt -> 'b, int * 'a) arity

Specifying model arity and eliminator type

val arity_0 : ('elt, 'elt, unit) arity
val arity_1 : ('elt, 'elt -> 'elt, int * unit) arity
val arity_2 : ('elt, 'elt -> 'elt -> 'elt, int * (int * unit)) arity
val arity_3 : ('elt, 'elt -> 'elt -> 'elt -> 'elt, int * (int * (int * unit))) arity
module type Model_impl = sig ... end

Abstract representation of models. Models are strongly typed: Model_impl.arg_type exposes what a model expects on input. The relation between arg_type and model_type is encoded through a value of type arity.

type 'arg model = (module Model_impl with type arg_type = 'arg)
type packed_model =
  1. | Model : _ model -> packed_model
module type Instantiated = sig ... end

Instantiation of a Model_impl.Def with a Costlang.S

module Instantiate (X : Costlang.S) (M : Model_impl) : Instantiated with type 'a repr = 'a X.repr and type size = X.size and type arg_type = M.arg_type
module type Applied = functor (X : Costlang.S) -> sig ... end

Model that has been applied to some arguments. Typically, we get an Applied model when we apply some workload from a benchmark to its model. Can be obtained with apply.

type applied = (module Applied)
type 'workload t =
  1. | Abstract : {
    1. conv : 'workload -> 'arg;
    2. model : 'arg model;
    } -> 'workload t
  2. | Aggregate : {
    1. model : 'workload -> applied;
    2. sub_models : packed_model list;
    } -> 'workload t

Model containers for benchmarks. We distinguish two kinds:

  • Abstract, which is simply a 'arg model, with a conv function that transforms a benchmark's workload into the model's arguments.
  • Aggregate, which is usually obtained from multiple models, a subset of which should be in sub_models.
val pp : Stdlib.Format.formatter -> _ t -> unit
val make : ?takes_saturation_reprs:bool -> conv:('a -> 'b) -> 'b model -> 'a t

Build _ t from _ model, with a type conversion fucntion conv. If ~takes_saturation_reprs: true is given, its generated code will take _ Saturation_reprs.t instead of int.

val make_aggregated : model:('a -> applied) -> sub_models:packed_model list -> 'a t
val apply : 'a t -> 'a -> applied

apply takes a model and an appropriate workload, and returns an applied model

val add_model : 'a t -> 'b t -> ('a * 'b) t

Addition on models. Note that the results is always an Aggregate

val precompose : ('a -> 'b) -> 'b t -> 'a t

Transformator for the type of workloads

val get_free_variable_set : _ model -> Free_variable.Set.t

Returns the set of free variables of a model

val get_free_variable_set_of_t : _ t -> Free_variable.Set.t
val get_free_variable_set_applied : 'workload t -> 'workload -> Free_variable.Set.t

Returns the set of free variables of an applied model

Note that this can be very different from get_free_variable_set.

Commonly used abstract models Except for zero, they all require a unique name in Namespace.t, and some Free_variable.ts. Those free are deduced during the inference in Snoop, and the resulting values are (usually) the gas parameters for the protocol.

val zero : unit model

zero is the "zero" for the addition on models. It can be seen as the model of the empty code. fun () -> 0

val unknown_const1 : name:Namespace.t -> const:Free_variable.t -> unit model

Model for code that executes in constant time fun () -> const

val unknown_const1_skip1 : name:Namespace.t -> const:Free_variable.t -> (int * unit) model

Model ignores the arguments. fun n -> const

val unknown_const1_skip2 : name:Namespace.t -> const:Free_variable.t -> (int * (int * unit)) model

Model ignores the arguments. fun n m -> const

val linear : name:Namespace.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> coeff × n

val affine : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> intercept + coeff × n

val affine_offset : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> offset:int -> (int * unit) model

fun n -> intercept + coeff × (n - offset)

val quadratic : name:Namespace.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> coeff * n²

val nlogn : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> intercept + coeff × n×log(n)

val nsqrtn_const : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> intercept + coeff × n×sqrt(n)

val logn : name:Namespace.t -> coeff:Free_variable.t -> (int * unit) model

fun n -> coeff * log(n)

val linear_sum : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × (a+b)

val linear_sat_sub : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × (a-b)

val linear_max : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × max(a,b)

val linear_min : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × min(a,b)

val linear_min_offset : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> offset:int -> (int * (int * unit)) model

fun a b -> intercept + coeff × (min(a,b) - offset)

val linear_mul : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × (a×b)

val bilinear : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> (int * (int * unit)) model

fun a b -> coeff1 × a + coeff2 × b

val bilinear_affine : name:Namespace.t -> intercept:Free_variable.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff1 × a + coeff2 × b

val affine_skip1 : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun a b -> intercept + coeff × b

val nlogm : name:Namespace.t -> intercept:Free_variable.t -> coeff:Free_variable.t -> (int * (int * unit)) model

fun n m -> intercept + coeff × n×log(m)

val n_plus_logm : name:Namespace.t -> intercept:Free_variable.t -> linear_coeff:Free_variable.t -> log_coeff:Free_variable.t -> (int * (int * unit)) model

fun n m -> intercept + (linear_coeff × n) + (log_coeff × log(m))

val trilinear : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> coeff3:Free_variable.t -> (int * (int * (int * unit))) model

fun a b c -> coeff1 × a + coeff2 × b + coeff3 × c

val breakdown : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> break:int -> (int * unit) model

A multi-affine model in two parts. The breakpoint break indicates the point at which the slope changes coefficient.

val breakdown2 : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> coeff3:Free_variable.t -> break1:int -> break2:int -> (int * unit) model

A multi-affine model in three parts, with breakpoints break1 and break2. Expects break1 <= break2

val breakdown2_const : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> coeff3:Free_variable.t -> const:Free_variable.t -> break1:int -> break2:int -> (int * unit) model

breakdown2 with a non-zero value at 0

val breakdown2_const_offset : name:Namespace.t -> coeff1:Free_variable.t -> coeff2:Free_variable.t -> coeff3:Free_variable.t -> const:Free_variable.t -> break1:int -> break2:int -> offset:int -> (int * unit) model

breakdown2 with a non-zero value at 0 and offset

module type Binary_operation = sig ... end
val synthesize : name:Namespace.t -> binop:(module Binary_operation) -> x_label:string -> x_model:'a model -> y_label:string -> y_model:'a model -> 'a model

Synthesize two models of the same signature by the specified binary operation.