bench_pertaro/
bench_pertaro.rs

1//! Zero-dependency latency benchmark for PERTARO.
2//!
3//! Run with: `cargo run --release --example bench_pertaro`
4//!
5//! No cycle counter: the crate forbids `unsafe`, and `_rdtsc` needs it.
6//! `Instant` is wall-clock nanoseconds; pin the process and quiet the machine
7//! for stable numbers. For cache-miss counts run under
8//! `perf stat -e L1-dcache-load-misses,L1-dcache-loads`.
9//!
10//! Sections 1 to 3 are compute-bound: `prune_frontier` is hundreds of
11//! nanoseconds of arithmetic over 256 sequential bytes, so the prefetcher hides
12//! the cache tier. Section 4 is the one that can show an L1 cliff: a light pass
13//! over an arena of N words in pseudo-random order, so the working set, not the
14//! arithmetic, sets the cost.
15
16use pertaro::{
17    xorshift64, PertaroArena121, PertaroExpert243, Sentinel, Word256, ARENA_NODES, FNV1A64_BASIS,
18    FRONTIER_START, ROOT_SENTINEL,
19};
20use std::hint::black_box;
21use std::time::Instant;
22
23fn seeded_expert() -> PertaroExpert243 {
24    let mut raw = Word256 {
25        hash: FNV1A64_BASIS,
26        parent: 0,
27        trits: [17u8; 244],
28    };
29    raw.trits[0] = Sentinel::NullNode as u8;
30    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
31    PertaroExpert243(raw)
32}
33
34/// Light per-node work: derive a seed from the node and write it back.
35/// Touches the header of one 256-byte word, roughly one cache line.
36#[inline(always)]
37fn touch(node: &mut PertaroExpert243, atom: u8) -> u64 {
38    let s = node.reground_seed(atom, Sentinel::BusIndirect);
39    node.0.hash = s;
40    s
41}
42
43/// Dependent chase: the next index comes from the word just touched, so every
44/// load waits for the previous one. This exposes load-to-use latency, which
45/// independent loads hide behind memory-level parallelism.
46fn chase_pass(arena: &mut [PertaroExpert243], passes: usize) -> f64 {
47    let n = arena.len();
48    let mut i = 0usize;
49    let mut acc = 0u64;
50    let t = Instant::now();
51    for _ in 0..passes {
52        for _ in 0..n {
53            let s = touch(&mut arena[i], (acc & 0xFF) as u8 % 243);
54            acc ^= s;
55            i = (s % n as u64) as usize;
56        }
57    }
58    black_box(acc);
59    t.elapsed().as_nanos() as f64 / (passes * n) as f64
60}
61
62fn random_pass(arena: &mut [PertaroExpert243], passes: usize) -> f64 {
63    let n = arena.len();
64    let mut rng = FNV1A64_BASIS;
65    let mut acc = 0u64;
66    let t = Instant::now();
67    for _ in 0..passes {
68        for _ in 0..n {
69            rng = xorshift64(rng);
70            let i = (rng % n as u64) as usize;
71            acc ^= touch(&mut arena[i], (rng >> 32) as u8 % 243);
72        }
73    }
74    black_box(acc);
75    t.elapsed().as_nanos() as f64 / (passes * n) as f64
76}
77
78fn main() {
79    const ITERS: usize = 100_000;
80    let expert = seeded_expert();
81
82    // 1. One word: materialize + two reduct passes + in-place tombstoning.
83    let t0 = Instant::now();
84    for _ in 0..ITERS {
85        let mut e = black_box(expert);
86        black_box(e.prune_frontier());
87    }
88    let ns_single = t0.elapsed().as_nanos() as f64 / ITERS as f64;
89
90    // 1b. Same, with pseudo-random leaf bytes (coordinates and every sentinel
91    // kind), so branch predictors see a realistic payload, not one byte repeated.
92    let mut rnd = Word256 {
93        hash: FNV1A64_BASIS,
94        parent: 0,
95        trits: [0u8; 244],
96    };
97    let mut g = 0x1234_5678_9ABC_DEF0u64;
98    for t in rnd.trits.iter_mut() {
99        g = xorshift64(g);
100        *t = match g % 10 {
101            0 => Sentinel::NullNode as u8,
102            1 => Sentinel::Tombstone as u8,
103            2 => 243 + ((g >> 8) % 13) as u8,
104            _ => ((g >> 16) % 243) as u8,
105        };
106    }
107    rnd.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
108    let rnd_expert = PertaroExpert243(rnd);
109    let t0b = Instant::now();
110    for _ in 0..ITERS {
111        let mut e = black_box(rnd_expert);
112        black_box(e.prune_frontier());
113    }
114    let ns_single_rnd = t0b.elapsed().as_nanos() as f64 / ITERS as f64;
115
116    // 1c. Stage attribution on the random payload: field, materialize, one reduct pass.
117    let mut field = [0u8; 243];
118    let t_f = Instant::now();
119    for i in 0..ITERS {
120        PertaroExpert243::default_field(black_box(rnd_expert.seed() ^ i as u64), &mut field);
121        black_box(&field);
122    }
123    let ns_field = t_f.elapsed().as_nanos() as f64 / ITERS as f64;
124    let t_m = Instant::now();
125    for _ in 0..ITERS {
126        black_box(black_box(rnd_expert).materialize());
127    }
128    let ns_mat = t_m.elapsed().as_nanos() as f64 / ITERS as f64;
129    let mat = rnd_expert.materialize();
130    let empty = pertaro::AnswerSetMask::empty();
131    let t_r = Instant::now();
132    for _ in 0..ITERS {
133        black_box(black_box(rnd_expert).gl_reduct_consequences(black_box(&mat), black_box(&empty)));
134    }
135    let ns_reduct = t_r.elapsed().as_nanos() as f64 / ITERS as f64;
136
137    // 2. Tier-4 arena: expand, prune the 81 frontier nodes, reground.
138    let mut arena = Box::new(PertaroArena121 {
139        nodes: [expert; ARENA_NODES],
140    });
141    let arena_iters = 10_000usize;
142    let mut seed = FNV1A64_BASIS;
143    let t1 = Instant::now();
144    for step in 0..arena_iters {
145        arena.expand_from_root(seed, (step % 243) as u8, Sentinel::BusIndirect);
146        let mut winner = 0u8;
147        for node in arena.frontier_mut() {
148            if let Some(w) = node.prune_frontier().first_winner() {
149                winner = w;
150            }
151        }
152        seed = arena.nodes[ARENA_NODES - 1].reground_seed(winner, Sentinel::BusIndirect);
153        black_box(seed);
154    }
155    let ns_l1_node = t1.elapsed().as_nanos() as f64 / (arena_iters * ARENA_NODES) as f64;
156
157    // 3. Tier-6 flat bank, 1093 words, every node pruned: compute-bound control.
158    const TIER6_NODES: usize = 1093;
159    let mut bank = vec![expert; TIER6_NODES];
160    let spill_iters = 2_000usize;
161    let t2 = Instant::now();
162    for step in 0..spill_iters {
163        for (i, node) in bank.iter_mut().enumerate() {
164            node.0.hash = seed.wrapping_add(i as u64);
165            black_box(node.prune_frontier());
166        }
167        seed = seed.wrapping_add(step as u64);
168    }
169    let ns_spill_node = t2.elapsed().as_nanos() as f64 / (spill_iters * TIER6_NODES) as f64;
170
171    // 4. The cliff test: light random-order touches over growing working sets.
172    let sizes = [121usize, 364, 1093, 3280, 9841, 29524];
173    let mut cliff = Vec::new();
174    for &n in &sizes {
175        let mut a = vec![expert; n];
176        random_pass(&mut a, 2); // warm
177        let passes = (2_000_000 / n).max(20);
178        let independent = random_pass(&mut a, passes);
179        let dependent = chase_pass(&mut a, passes);
180        cliff.push((n, n * 256, independent, dependent));
181    }
182
183    println!("==============================================================");
184    println!(
185        " PERTARO LATENCY (Word256 = 256 B, Arena121 = {} B)",
186        ARENA_NODES * 256
187    );
188    println!("==============================================================");
189    println!("1. one word, materialize + reduct + prune : {ns_single:>8.1} ns  (uniform payload)");
190    println!("1b. same, random payload                  : {ns_single_rnd:>8.1} ns");
191    println!("1c. attribution (random payload):");
192    println!("      default_field (243 digits)          : {ns_field:>8.1} ns");
193    println!("      materialize (field + resolve)       : {ns_mat:>8.1} ns");
194    println!("      one gl_reduct pass                  : {ns_reduct:>8.1} ns");
195    println!("2. tier-4 arena, expand + 81 prunes       : {ns_l1_node:>8.1} ns/node");
196    println!("3. tier-6 bank, 1093 prunes (control)     : {ns_spill_node:>8.1} ns/node");
197    println!("4. light touch, by working set (tier-4 frontier starts at node {FRONTIER_START}):");
198    println!("     nodes      bytes   independent ns   dependent ns");
199    for (n, bytes, ind, dep) in cliff {
200        println!("   {n:>7} {bytes:>10} {ind:>14.2} {dep:>14.2}");
201    }
202    println!("   independent = random index from an RNG (loads overlap)");
203    println!("   dependent   = next index from the word just loaded (loads serialize)");
204    println!("==============================================================");
205}
bench_pertaro/bench_pertaro.rs

bench_pertaro/
bench_pertaro.rs
