Rust Merkle benchmarking

merkle.rs

use binary_merkle_tree::merkle_root;
use fake::{Fake, Faker};
use rs_merkle::{Hasher, MerkleTree};
use sha3::{Digest, Keccak256};
use sp_core::H256;

#[derive(Clone)]
pub struct KeccakAlgorithm {}

impl Hasher for KeccakAlgorithm {
    type Hash = [u8; 32];

    fn hash(data: &[u8]) -> [u8; 32] {
        Keccak256::digest(data).into()
    }
}

fn main() {
    let mut leaves_arr: Vec<Vec<Vec<u8>>> = vec![];
    for i in 1..10000 {
        let mut leaves: Vec<Vec<u8>> = vec![];
        for _ in 0..i {
            let leaf = Faker.fake::<Vec<u8>>();
            leaves.push(leaf);
        }
        leaves_arr.push(leaves.clone());
        let root_1 = merkle_root_1(leaves.iter().cloned());
        let root_2 = merkle_root_2(leaves.iter().cloned());
        assert_eq!(root_1, root_2);
    }

    let mut start = std::time::Instant::now();
    for leaves in &leaves_arr {
        merkle_root_1(leaves.iter().cloned());
    }
    println!("merkle_root_1: {:?}", start.elapsed());

    start = std::time::Instant::now();
    for leaves in &leaves_arr {
        merkle_root_2(leaves.iter().cloned());
    }
    println!("merkle_root_2: {:?}", start.elapsed());
}

fn merkle_root_1<I>(leaves: I) -> H256
where
    I: Iterator<Item = Vec<u8>>,
{
    merkle_root::<sp_core::KeccakHasher, _>(leaves).into()
}

fn merkle_root_2<I>(leaves: I) -> H256
where
    I: Iterator<Item = Vec<u8>>,
{
    let mut tree = MerkleTree::<KeccakAlgorithm>::new();
    for leaf in leaves {
        tree.insert(<[u8; 32]>::from(Keccak256::digest(leaf)));
    }
    tree.uncommitted_root().unwrap().into()
}