74 lines
2.6 KiB
Rust
74 lines
2.6 KiB
Rust
//! 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);
|