//! Latency bench — pointer chasing vs linear, as in algorithmica.org/hpc/cpu-cache/latency
//! E[L] = (s1*l1 + (s2-s1)*l2 + ...)/N ; cliff at s_i
use criterion::{criterion_group, criterion_main, Criterion, BenchmarkId, Throughput};

fn make_single_cycle_perm(n: usize) -> Vec<usize> {
    use rand::{seq::SliceRandom, SeedableRng, rngs::StdRng};
    let mut p: Vec<usize> = (0..n).collect();
    let mut rng = StdRng::seed_from_u64(0xdeadbeef);
    p.shuffle(&mut rng);
    let mut q = vec![0usize; n];
    let mut k = p[n-1];
    for &val in &p {
        let nk = k;
        k = val;
        q[nk] = k;
    }
    // Ensure single cycle: q now is permutation with one cycle
    q
}

fn bench_latency(c: &mut Criterion) {
    let mut group = c.benchmark_group("latency_pointer_chasing");
    // N values to hit L1 (32K), L2 (512K), L3 (8M), RAM
    for &n in &[1_000, 8_000, 64_000, 512_000, 4_000_000] {
        let perm = make_single_cycle_perm(n);
        group.throughput(Throughput::Elements(n as u64));
        group.bench_with_input(BenchmarkId::from_parameter(n), &n, |b, _| {
            let mut k: usize = 0;
            // Keep k live to prevent optimization
            b.iter(|| {
                for _ in 0..100 {
                    for _ in 0..n {
                        k = perm[k];
                    }
                }
                std::hint::black_box(k)
            });
        });
        // Linear baseline for same N
        group.bench_with_input(BenchmarkId::new("linear", n), &n, |b, _| {
            let data = vec![0u64; n];
            b.iter(|| {
                let mut sum = 0u64;
                for _ in 0..100 {
                    for &v in &data { sum = sum.wrapping_add(v); }
                }
                std::hint::black_box(sum)
            });
        });
    }
    group.finish();
}

fn bench_tenant_map_latency(c: &mut Criterion) {
    // Real hotspot: DashMap<ConnId, _> random lookup latency
    use dashmap::DashMap;
    let mut group = c.benchmark_group("dashmap_random_lookup");
    for &n in &[1_000, 10_000, 100_000] {
        let map: DashMap<u32, u32> = DashMap::new();
        for i in 0..n as u32 { map.insert(i*2654435761, i); }
        let keys: Vec<u32> = (0..n as u32).map(|i| i*2654435761).collect();
        group.bench_with_input(BenchmarkId::from_parameter(n), &n, |b, _| {
            let mut sum = 0u32;
            b.iter(|| {
                for k in &keys { if let Some(v) = map.get(k) { sum = sum.wrapping_add(*v); } }
                std::hint::black_box(sum)
            });
        });
    }
    group.finish();
}

criterion_group!(benches, bench_latency, bench_tenant_map_latency);
criterion_main!(benches);