1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

use crate::{
    evm_circuit::{
        step::ExecutionState, table::Table, util::constraint_builder::EVMConstraintBuilder,
    },
    util::cell_manager::CellType,
};
use eth_types::Field;
use itertools::Itertools;

type StepSize = Vec<(CellType, ColumnSize)>;
/// Contains (width, height, num_cells)
type ColumnSize = (usize, usize, usize);

/// Instrument captures metrics during the compilation of a circuit.
#[derive(Clone, Debug, Default)]
pub struct Instrument {
    // States -> Cell Types -> (width, height, num_cells)
    states: Vec<(ExecutionState, StepSize)>,
}

impl Instrument {
    /// Collects `CellManager` stats from a compiled EVMCircuit in order to
    /// extract metrics.
    pub(crate) fn on_gadget_built<F: Field>(
        &mut self,
        execution_state: ExecutionState,
        cb: &EVMConstraintBuilder<F>,
    ) {
        let sizes = cb
            .curr
            .cell_manager
            .get_stats()
            .into_iter()
            .sorted()
            .collect::<Vec<_>>();

        self.states.push((execution_state, sizes));
    }

    /// Disassembles the instrumentation data and returns a collection of
    /// `ExecStateReport`s. One for each EVM `ExecutionState`.
    pub fn analyze(&self) -> Vec<ExecStateReport> {
        let mut report_collection = vec![];
        for (state, sizes) in &self.states {
            // Create a state report
            let mut report = ExecStateReport::from(state);
            // Compute max_height required for any kind of CellType for the current
            // `ExecutionState`.
            let top_height: usize = sizes.iter().map(|(_, (_, h, _))| *h).max().unwrap();

            // Obtain `ExecutionState` metrics per column type.
            for (cell_type, (width, _, cells)) in sizes {
                let unused_cells = width * top_height - cells;
                let total_available_cells = width * top_height;
                let utilization =
                    ((*cells as f64) / (*width as f64 * top_height as f64) * 100f64).round();

                let data_entry = StateReportRow {
                    available_cells: total_available_cells,
                    unused_cells,
                    used_cells: *cells,
                    top_height,
                    used_columns: cells / top_height,
                    utilization,
                };

                match cell_type {
                    CellType::StoragePhase1 => {
                        report.storage_1 = data_entry;
                    }
                    CellType::StoragePhase2 => {
                        report.storage_2 = data_entry;
                    }
                    CellType::StoragePermutation => {
                        report.storage_perm = data_entry;
                    }
                    CellType::Lookup(Table::U8) => {
                        report.u8_lookup = data_entry;
                    }
                    CellType::Lookup(Table::U16) => {
                        report.u16_lookup = data_entry;
                    }
                    CellType::Lookup(Table::Fixed) => {
                        report.fixed_table = data_entry;
                    }
                    CellType::Lookup(Table::Tx) => {
                        report.tx_table = data_entry;
                    }
                    CellType::Lookup(Table::Rw) => {
                        report.rw_table = data_entry;
                    }
                    CellType::Lookup(Table::Bytecode) => {
                        report.bytecode_table = data_entry;
                    }
                    CellType::Lookup(Table::Block) => {
                        report.block_table = data_entry;
                    }
                    CellType::Lookup(Table::Copy) => {
                        report.copy_table = data_entry;
                    }
                    CellType::Lookup(Table::Keccak) => {
                        report.keccak_table = data_entry;
                    }
                    CellType::Lookup(Table::Exp) => {
                        report.exp_table = data_entry;
                    }
                    CellType::Lookup(Table::Sig) => {
                        report.sig_table = data_entry;
                    }
                    CellType::Lookup(Table::ChunkCtx) => {
                        report.chunk_ctx_table = data_entry;
                    }
                }
            }
            report_collection.push(report);
        }
        report_collection
    }
}

/// Struct which contains a Cost/ColumnType report for a particular EVM
/// [`ExecStep`](bus_mapping::circuit_input_builder::ExecStep).
#[derive(Clone, Debug, Default)]
pub struct ExecStateReport {
    pub state: ExecutionState,
    pub storage_1: StateReportRow,
    pub storage_2: StateReportRow,
    pub storage_perm: StateReportRow,
    pub u8_lookup: StateReportRow,
    pub u16_lookup: StateReportRow,
    pub byte_lookup: StateReportRow,
    pub fixed_table: StateReportRow,
    pub tx_table: StateReportRow,
    pub rw_table: StateReportRow,
    pub bytecode_table: StateReportRow,
    pub block_table: StateReportRow,
    pub copy_table: StateReportRow,
    pub keccak_table: StateReportRow,
    pub exp_table: StateReportRow,
    pub sig_table: StateReportRow,
    pub chunk_ctx_table: StateReportRow,
}

impl From<ExecutionState> for ExecStateReport {
    fn from(state: ExecutionState) -> Self {
        ExecStateReport {
            state,
            ..Default::default()
        }
    }
}

impl From<&ExecutionState> for ExecStateReport {
    fn from(state: &ExecutionState) -> Self {
        ExecStateReport {
            state: *state,
            ..Default::default()
        }
    }
}

/// Struct that contains all of the measurament values required to evaluate the
/// costs of a particular `ColumnType` of an `ExecStateReport`
#[derive(Debug, Clone, Default)]
pub struct StateReportRow {
    // Given a rigion of x columns and y rows, we have x * y cells available for computation.
    pub available_cells: usize,
    // The cells not used in the computation in the x*y region. These are the wasted cells.
    pub unused_cells: usize,
    // The cells used in the computation in the x*y region.
    pub used_cells: usize,
    // The largest y within all the `CellType`.
    pub top_height: usize,
    // If we fully utilize y, how large is the x really needed?
    pub used_columns: usize,
    // The percentage of cells used in computation in the x * y region.
    pub utilization: f64,
}