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 subsoil as _;
20
21#[cfg(target_os = "none")]
22extern crate alloc;
23
24#[cfg(target_os = "none")]
25mod bump_alloc {
26    use core::alloc::{GlobalAlloc, Layout};
27    use core::cell::UnsafeCell;
28
29    const HEAP_SIZE: usize = 256 * 1024;
30
31    pub struct BumpAlloc {
32        heap: UnsafeCell<[u8; HEAP_SIZE]>,
33        pos: UnsafeCell<usize>,
34    }
35
36    unsafe impl Sync for BumpAlloc {}
37
38    unsafe impl GlobalAlloc for BumpAlloc {
39        unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
40            let pos = unsafe { &mut *self.pos.get() };
41            let aligned = (*pos + layout.align() - 1) & !(layout.align() - 1);
42            let next = aligned + layout.size();
43            if next > HEAP_SIZE {
44                return core::ptr::null_mut();
45            }
46            *pos = next;
47            unsafe { (*self.heap.get()).as_mut_ptr().add(aligned) }
48        }
49        unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {}
50    }
51
52    #[global_allocator]
53    static ALLOC: BumpAlloc = BumpAlloc {
54        heap: UnsafeCell::new([0; HEAP_SIZE]),
55        pos: UnsafeCell::new(0),
56    };
57}
58
59#[cfg(target_os = "none")]
60use alloc::vec::Vec;
61
62use gp::{add, canonical, mul, permute, sub, ONE, ZERO};
63
64const TRACE_LOG: u32 = 12;
65const N: usize = 1 << TRACE_LOG;
66const TREE_SIZE: usize = 2 * N - 1;
67const NUM_QUERIES: u32 = 30;
68const SEED: u64 = 0x123456789abcdef0;
69const MULTIPLIER: u64 = 0x9E3779B97F4A7C15;
70
71pub fn fri_fold_tree_bench() -> u32 {
72    let mut tree: Vec<u64> = Vec::with_capacity(TREE_SIZE);
73    let mut x: u64 = SEED;
74    let mut i = 0;
75    while i < TREE_SIZE {
76        x = mul(x, MULTIPLIER);
77        tree.push(x);
78        i += 1;
79    }
80
81    let mut offsets = [0usize; (TRACE_LOG + 1) as usize];
82    let mut acc = 0;
83    let mut sz = N;
84    let mut l = 0;
85    while l <= TRACE_LOG as usize {
86        offsets[l] = acc;
87        acc += sz;
88        sz >>= 1;
89        l += 1;
90    }
91
92    let mut state: [u64; 8] = [
93        0xdeadbeef_00000000,
94        0xdeadbeef_00000001,
95        0xdeadbeef_00000002,
96        0xdeadbeef_00000003,
97        0xdeadbeef_00000004,
98        0xdeadbeef_00000005,
99        0xdeadbeef_00000006,
100        0xdeadbeef_00000007,
101    ];
102    let mut k = 0;
103    while k < 4 {
104        permute(&mut state);
105        k += 1;
106    }
107
108    let mut accum = ZERO;
109    let mut q = 0;
110    while q < NUM_QUERIES {
111        let mut idx = (state[(q as usize) % 8] & ((N as u64) - 1)) as usize;
112        let mut current = tree[idx];
113        let mut level = 0;
114        while level < TRACE_LOG as usize {
115            let sibling = tree[offsets[level] + (idx ^ 1)];
116            let mut h = state;
117            h[0] = current;
118            h[1] = sibling;
119            permute(&mut h);
120            let challenge = h[0];
121            let one_minus_c = sub(ONE, challenge);
122            current = add(mul(one_minus_c, current), mul(challenge, sibling));
123            idx >>= 1;
124            level += 1;
125        }
126        accum = add(accum, current);
127        q += 1;
128    }
129
130    (canonical(accum) & 0xFFFF_FFFF) as u32
131}
bench_fri_fold_tree/lib.rs

bench_fri_fold_tree/
lib.rs
