1//! Benchmark for building a [`miden_crypto::merkle::MerkleTree`]. This is intended to be compared
 2//! with the results from `benches/smt-subtree.rs`, as building a fully balanced Merkle tree with
 3//! 256 leaves should indicate the *absolute best* performance we could *possibly* get for building
 4//! a depth-8 sparse Merkle subtree, though practically speaking building a fully balanced Merkle
 5//! tree will perform better than the sparse version. At the time of this writing (2024/11/24), this
 6//! benchmark is about four times more efficient than the equivalent benchmark in
 7//! `benches/smt-subtree.rs`.
 8use std::{hint, mem, time::Duration};
 9
10use criterion::{criterion_group, criterion_main, BatchSize, Criterion};
11use miden_crypto::{merkle::MerkleTree, Felt, Word, ONE};
12use rand_utils::prng_array;
13
14fn balanced_merkle_even(c: &mut Criterion) {
15    c.bench_function("balanced-merkle-even", |b| {
16        b.iter_batched(
17            || {
18                let entries: Vec<Word> =
19                    (0..256).map(|i| [Felt::new(i), ONE, ONE, Felt::new(i)]).collect();
20                assert_eq!(entries.len(), 256);
21                entries
22            },
23            |leaves| {
24                let tree = MerkleTree::new(hint::black_box(leaves)).unwrap();
25                assert_eq!(tree.depth(), 8);
26            },
27            BatchSize::SmallInput,
28        );
29    });
30}
31
32fn balanced_merkle_rand(c: &mut Criterion) {
33    let mut seed = [0u8; 32];
34    c.bench_function("balanced-merkle-rand", |b| {
35        b.iter_batched(
36            || {
37                let entries: Vec<Word> = (0..256).map(|_| generate_word(&mut seed)).collect();
38                assert_eq!(entries.len(), 256);
39                entries
40            },
41            |leaves| {
42                let tree = MerkleTree::new(hint::black_box(leaves)).unwrap();
43                assert_eq!(tree.depth(), 8);
44            },
45            BatchSize::SmallInput,
46        );
47    });
48}
49
50criterion_group! {
51    name = smt_subtree_group;
52    config = Criterion::default()
53        .measurement_time(Duration::from_secs(20))
54        .configure_from_args();
55    targets = balanced_merkle_even, balanced_merkle_rand
56}
57criterion_main!(smt_subtree_group);
58
59// HELPER FUNCTIONS
60// --------------------------------------------------------------------------------------------
61
62fn generate_word(seed: &mut [u8; 32]) -> Word {
63    mem::swap(seed, &mut prng_array(*seed));
64    let nums: [u64; 4] = prng_array(*seed);
65    [Felt::new(nums[0]), Felt::new(nums[1]), Felt::new(nums[2]), Felt::new(nums[3])]
66}