Proto: Carbonated map utility module

Context

This is the fifth of a series of MRs for introducing a ticket accounting feature in the protocol as described in this document.

See the milestone for a break down of the work.

This a stand-alone MR that introduces a generic module, Carbonated_map, that provides an API for working with an in-memory map structure, where each operation is gas-metered.

Currently the API provides a functor for constructing maps:

module type COMPARABLE = sig
  include Compare.COMPARABLE
  val compare_key_cost : Alpha_context.Gas.cost
end

module Make (O : COMPARABLE) : S with type key := O.t

The user of the module will have to provide a benchmarked compare_key_cost for any instance of the map.

Manually testing the MR

No manual tests required. Unit tests for this MR are run with:

> dune build @src/proto_alpha/lib_protocol/runtest_carbonated_map

Running the benchmarks

There are four benchmarks for the functions in Carbonated_map_costs.

All parameters are inferred as part of:

dune exec tezt/snoop/main.exe -- --verbose

To list benchmark

It's for inferring the coefficient for the linear cost of converting a map to a list. It's run by:

./tezos-snoop benchmark Carbonated_map_to_list_alpha and save to Carbonated_map_to_list_alpha.workload --bench-num 500 --nsamples 3000 --seed 12897
./tezos-snoop infer parameters for model carbonated_map  on data Carbonated_map_to_list_alpha.workload using lasso --lasso-positive --save-solution Carbonated_map_to_list_alpha.sol --plot
./tezos-snoop generate code using solution Carbonated_map_to_list_alpha.sol and model Carbonated_map_to_list_alpha

Compare cost benchmark

The cost of comparing int keys (provided as an example Benchmarks_int.Compare). Run with:

./tezos-snoop benchmark Carbonated_map_compare_int_alpha and save to compare_int.workload --bench-num 500 --nsamples 3000 --seed 12897

Find benchmark

A benchmark for the find model:

./tezos-snoop benchmark Carbonated_map_find_alpha and save to Carbonated_map_find_alpha.workload --bench-num 500 --nsamples 3000 --seed 12897
./tezos-snoop infer parameters for model carbonated_map on data Carbonated_map_find_alpha.workload using lasso --lasso-positive --save-solution Carbonated_map_find_alpha.sol --plot
./tezos-snoop generate code using solution Carbonated_map_find_alpha.sol and model Carbonated_map_find_alpha

Find intercept

A benchmark for the intercept parameter for the find model:

> ./tezos-snoop benchmark Carbonated_map_find_intercept_alpha and save to Carbonated_map_find_intercept_alpha.workload --bench-num 500 --nsamples 3000 --seed 12897
> ./tezos-snoop generate code using solution Carbonated_map_find_intercept_alpha.sol and model Carbonated_map_find_intercept_alpha

Checklist

• Document the interface of any function added or modified (see the coding guidelines)
• Document any change to the user interface, including configuration parameters (see node configuration)
• Provide automatic testing (see the testing guide).
• For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, the Development Version section of CHANGES.md for everything else).
• Select suitable reviewers using the Reviewers field below.
• Select as Assignee the next person who should take action on that MR