bench_fri_fold_tree/
lib.rs

1//! FRI fold-tree walk benchmark — mirrors `p3_fri::verify`'s hot loop.
2//!
3//! Builds a synthetic flat merkle-tree buffer (deterministic content;
4//! we don't bother computing real internal-node hashes since the
5//! bench measures access patterns + per-step ops, not commitment
6//! correctness). For each of `NUM_QUERIES` queries:
7//!   - Pick a random leaf index from the transcript.
8//!   - Walk the tree from leaf to root, `TRACE_LOG` levels.
9//!   - At each level: read scattered sibling, Poseidon2-mix,
10//!     Goldilocks-fold.
11//!
12//! Complements `mini-verifier`: that workload hashes the same 8-cell
13//! state buffer repeatedly (cache-warm). FRI walks scattered indices
14//! in a flat 64 KiB tree buffer — exposes cache + allocator pressure
15//! that the composite verifier didn't isolate.
16
17#![cfg_attr(target_os = "none", no_std)]
18
19use nub_rt as _;
20
21#[cfg(target_os = "none")]
22extern crate alloc;
23
24#[cfg(target_os = "none")]
25use alloc::vec::Vec;
26
27use gp::{add, canonical, mul, permute, sub, ONE, ZERO};
28
29const TRACE_LOG: u32 = 12;
30const N: usize = 1 << TRACE_LOG;
31const TREE_SIZE: usize = 2 * N - 1;
32const NUM_QUERIES: u32 = 30;
33const SEED: u64 = 0x123456789abcdef0;
34const MULTIPLIER: u64 = 0x9E3779B97F4A7C15;
35
36pub fn fri_fold_tree_bench() -> u32 {
37    let mut tree: Vec<u64> = Vec::with_capacity(TREE_SIZE);
38    let mut x: u64 = SEED;
39    let mut i = 0;
40    while i < TREE_SIZE {
41        x = mul(x, MULTIPLIER);
42        tree.push(x);
43        i += 1;
44    }
45
46    let mut offsets = [0usize; (TRACE_LOG + 1) as usize];
47    let mut acc = 0;
48    let mut sz = N;
49    let mut l = 0;
50    while l <= TRACE_LOG as usize {
51        offsets[l] = acc;
52        acc += sz;
53        sz >>= 1;
54        l += 1;
55    }
56
57    let mut state: [u64; 8] = [
58        0xdeadbeef_00000000,
59        0xdeadbeef_00000001,
60        0xdeadbeef_00000002,
61        0xdeadbeef_00000003,
62        0xdeadbeef_00000004,
63        0xdeadbeef_00000005,
64        0xdeadbeef_00000006,
65        0xdeadbeef_00000007,
66    ];
67    let mut k = 0;
68    while k < 4 {
69        permute(&mut state);
70        k += 1;
71    }
72
73    let mut accum = ZERO;
74    let mut q = 0;
75    while q < NUM_QUERIES {
76        let mut idx = (state[(q as usize) % 8] & ((N as u64) - 1)) as usize;
77        let mut current = tree[idx];
78        let mut level = 0;
79        while level < TRACE_LOG as usize {
80            let sibling = tree[offsets[level] + (idx ^ 1)];
81            let mut h = state;
82            h[0] = current;
83            h[1] = sibling;
84            permute(&mut h);
85            let challenge = h[0];
86            let one_minus_c = sub(ONE, challenge);
87            current = add(mul(one_minus_c, current), mul(challenge, sibling));
88            idx >>= 1;
89            level += 1;
90        }
91        accum = add(accum, current);
92        q += 1;
93    }
94
95    (canonical(accum) & 0xFFFF_FFFF) as u32
96}
bench_fri_fold_tree/lib.rs

bench_fri_fold_tree/
lib.rs
