miden_debug_engine/profiling/instrument/
op_histogram.rs

1use miden_core::{Felt, operations::Operation};
2
3use super::{Instrument, InstrumentRegistration};
4use crate::register_instrument;
5
6/// An [`Instrument`] to create operation histograms.
7///
8/// At each cycle, it records the current operation and produces a histogram of executed operations
9/// weighted by cycles per operation. If `opX` takes 4 cycles and was executed twice, its count
10/// will be 8.
11pub struct OpHistogram {
12    total_cycles: u128,
13    counts: [u64; 256],
14}
15
16impl Default for OpHistogram {
17    fn default() -> Self {
18        Self {
19            total_cycles: 0,
20            counts: [0; 256],
21        }
22    }
23}
24
25impl InstrumentRegistration for OpHistogram {
26    const NAME: &'static str = "op-histogram";
27
28    fn build(_config: &crate::profiling::ProfilerConfig) -> Result<Self, super::InstrumentError> {
29        Ok(Self::default())
30    }
31}
32
33register_instrument!(OpHistogram);
34
35impl Instrument for OpHistogram {
36    fn name(&self) -> &'static str {
37        Self::NAME
38    }
39
40    fn on_operation_execution_cycle(&mut self, op: Operation) {
41        self.total_cycles += 1;
42        // `op.op_code` returns u8 which can safely be used as index here
43        self.counts[usize::from(op.op_code())] += 1;
44    }
45
46    fn write_report_to(&self, writer: &mut dyn std::io::Write) -> std::io::Result<()> {
47        const OP_COL_WIDTH: usize = 16;
48        const SHARE_COL_WIDTH: usize = 7;
49
50        let total = self.total_cycles;
51
52        // Header row: the total accounts for 100% of the cycles. Every row is laid out in three
53        // columns (op | share | count) with fixed widths so the output stays aligned. When `total
54        // == 0` there are no data rows, so only this header line is written.
55        writeln!(
56            writer,
57            "{:<col1$} {:>col2$} {}",
58            "total_cycles",
59            "100%",
60            total,
61            col1 = OP_COL_WIDTH,
62            col2 = SHARE_COL_WIDTH,
63        )?;
64
65        for (op, count) in self.sorted_counts() {
66            let share = 100.0 * (count as f64) / (total as f64);
67            // Any payload on the reconstructed `Operation` is just a meaningless placeholder, so
68            // remove it. The report then only contains `push` instead of `push(0)`, for example.
69            let label = op.to_string();
70            let label = label.split('(').next().unwrap();
71            writeln!(
72                writer,
73                "{:<col1$} {:>col2$} {}",
74                label,
75                format!("{share:.2}%"),
76                count,
77                col1 = OP_COL_WIDTH,
78                col2 = SHARE_COL_WIDTH,
79            )?;
80        }
81        Ok(())
82    }
83}
84
85impl OpHistogram {
86    fn sorted_counts(&self) -> SortedCounts {
87        let mut counts: SortedCounts = ALL_OPERATIONS
88            .iter()
89            .map(|&op| (op, self.counts[usize::from(op.op_code())]))
90            .filter(|&(_, count)| count > 0)
91            .collect();
92        // Sort by count descending; break ties by opcode for a stable order.
93        counts.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.op_code().cmp(&b.0.op_code())));
94        counts
95    }
96}
97
98/// Counts per operation, sorted in descending order by count.
99type SortedCounts = Vec<(Operation, u64)>;
100
101/// Every basic-block [`Operation`] variant, with placeholder payloads (`Felt::ZERO`) for the
102/// value-carrying variants. Used to map the `counts` array back into typed operations for
103/// reporting.
104///
105/// A unit test ensures that this list contains *all* relevant operations from `miden-core`.
106const ALL_OPERATIONS: &[Operation] = &[
107    Operation::Noop,
108    Operation::Assert(Felt::ZERO),
109    Operation::SDepth,
110    Operation::Caller,
111    Operation::Clk,
112    Operation::Emit,
113    Operation::Add,
114    Operation::Neg,
115    Operation::Mul,
116    Operation::Inv,
117    Operation::Incr,
118    Operation::And,
119    Operation::Or,
120    Operation::Not,
121    Operation::Eq,
122    Operation::Eqz,
123    Operation::Expacc,
124    Operation::Ext2Mul,
125    Operation::U32split,
126    Operation::U32add,
127    Operation::U32add3,
128    Operation::U32sub,
129    Operation::U32mul,
130    Operation::U32madd,
131    Operation::U32div,
132    Operation::U32and,
133    Operation::U32xor,
134    Operation::U32assert2(Felt::ZERO),
135    Operation::Pad,
136    Operation::Drop,
137    Operation::Dup0,
138    Operation::Dup1,
139    Operation::Dup2,
140    Operation::Dup3,
141    Operation::Dup4,
142    Operation::Dup5,
143    Operation::Dup6,
144    Operation::Dup7,
145    Operation::Dup9,
146    Operation::Dup11,
147    Operation::Dup13,
148    Operation::Dup15,
149    Operation::Swap,
150    Operation::SwapW,
151    Operation::SwapW2,
152    Operation::SwapW3,
153    Operation::SwapDW,
154    Operation::MovUp2,
155    Operation::MovUp3,
156    Operation::MovUp4,
157    Operation::MovUp5,
158    Operation::MovUp6,
159    Operation::MovUp7,
160    Operation::MovUp8,
161    Operation::MovDn2,
162    Operation::MovDn3,
163    Operation::MovDn4,
164    Operation::MovDn5,
165    Operation::MovDn6,
166    Operation::MovDn7,
167    Operation::MovDn8,
168    Operation::CSwap,
169    Operation::CSwapW,
170    Operation::Push(Felt::ZERO),
171    Operation::AdvPop,
172    Operation::AdvPopW,
173    Operation::MLoadW,
174    Operation::MStoreW,
175    Operation::MLoad,
176    Operation::MStore,
177    Operation::MStream,
178    Operation::Pipe,
179    Operation::CryptoStream,
180    Operation::HPerm,
181    Operation::MpVerify(Felt::ZERO),
182    Operation::MrUpdate,
183    Operation::FriE2F4,
184    Operation::HornerBase,
185    Operation::HornerExt,
186    Operation::EvalCircuit,
187    Operation::LogDeferred,
188];
189
190#[cfg(test)]
191mod tests {
192    use std::collections::BTreeSet;
193
194    use miden_core::{Felt, operations::Operation, serde::Deserializable};
195
196    use super::ALL_OPERATIONS;
197    use crate::profiling::instrument::Instrument;
198
199    /// `ALL_OPERATIONS` must contain exactly the set of opcodes that map to a
200    /// valid `Operation`.
201    ///
202    /// We use `Operation`'s `Deserializable` impl as the source of truth.
203    #[test]
204    fn all_operations_covers_every_valid_opcode() {
205        // The payload-carrying variants (Push, Assert, MpVerify, U32assert2)
206        // read an extra `Felt` after the opcode byte, so pad with enough zero
207        // bytes for them to deserialize. Trailing bytes are ignored by the
208        // reader, so this is harmless for the 1-byte variants.
209        let valid: BTreeSet<u8> = (0u8..=u8::MAX)
210            .filter(|&op| Operation::read_from_bytes(&[op, 0, 0, 0, 0, 0, 0, 0, 0]).is_ok())
211            .collect();
212
213        let ours: BTreeSet<u8> = ALL_OPERATIONS.iter().map(|op| op.op_code()).collect();
214
215        // `ALL_OPERATIONS` holds real `Operation` values, so  `ours ⊆ valid`. The list can
216        // therefore only fall out of sync by *missing* a variant.
217        let missing_in_ours: Vec<String> = valid
218            .difference(&ours)
219            .map(|&op| {
220                format!(
221                    "{}",
222                    Operation::read_from_bytes(&[op, 0, 0, 0, 0, 0, 0, 0, 0])
223                        .expect("valid opcode deserializes to an Operation")
224                )
225            })
226            .collect();
227
228        if !missing_in_ours.is_empty() {
229            panic!(
230                "ALL_OPERATIONS is out of sync with miden-core's Operation enum.\n  missing from \
231                 ALL_OPERATIONS (add these): {missing_in_ours:?}"
232            );
233        }
234    }
235
236    #[test]
237    fn op_histogram_reports_recorded_ops() {
238        let mut hist = super::OpHistogram::default();
239
240        // 3 cycles
241        hist.on_operation_execution_cycle(Operation::Add);
242        hist.on_operation_execution_cycle(Operation::Add);
243        hist.on_operation_execution_cycle(Operation::Noop);
244
245        let mut buf = Vec::new();
246        hist.write_report_to(&mut buf).unwrap();
247        let report = String::from_utf8(buf).unwrap();
248
249        let lines: Vec<&str> = report.lines().collect();
250        // First line is the header reporting 100% of 3 cycles.
251        assert!(lines[0].contains("total_cycles") && lines[0].contains('3'));
252
253        // `Add` must preceed `Noop`, due to higher count.
254        assert!(lines[1].contains(Operation::Add.to_string().as_str()) && lines[1].contains("2"));
255        assert!(lines[2].contains(Operation::Noop.to_string().as_str()) && lines[2].contains("1"));
256
257        // no further lines
258        assert_eq!(lines.len(), 3);
259    }
260
261    /// Payload-carrying operations must render with just their mnemonic, e.g. `push` rather than
262    /// `push(0)`.
263    #[test]
264    fn op_histogram_omits_payload_from_mnemonic() {
265        let mut hist = super::OpHistogram::default();
266
267        // All payload carrying variants
268        hist.on_operation_execution_cycle(Operation::Push(Felt::ZERO));
269        hist.on_operation_execution_cycle(Operation::Assert(Felt::ZERO));
270        hist.on_operation_execution_cycle(Operation::MpVerify(Felt::ZERO));
271        hist.on_operation_execution_cycle(Operation::U32assert2(Felt::ZERO));
272
273        let mut buf = Vec::new();
274        hist.write_report_to(&mut buf).unwrap();
275        let report = String::from_utf8(buf).unwrap();
276
277        assert!(
278            !report.contains("(0)"),
279            "report must not contain placeholder payloads: {report}"
280        );
281        for mnemonic in ["push", "assert", "mpverify", "u32assert2"] {
282            assert!(report.contains(mnemonic), "report missing `{mnemonic}`: {report}");
283        }
284    }
285}
miden_debug_engine/profiling/instrument/op_histogram.rs

miden_debug_engine/profiling/instrument/
op_histogram.rs
