facett-core/benches/heavy_legibility.rs
//! **HEAVY benchmark — the LEGIBILITY frame budget at graph scale.**
//!
//! "As good and better for viewing data" is a performance claim as much as a visual
//! one: a cure that makes a 100 000-node pane readable at 4 fps has not made it
//! usable. Every legibility primitive therefore gets a bench arm, swept over dataset
//! sizes, so the "cost tracks the screen, not the dataset" claim is a **measured
//! curve** rather than a doc comment. (The map side shipped exactly that claim as prose
//! and it was false for months — see `facett-geomap`'s `PointGrid` lattice bug.)
//!
//! | arm | what it measures |
//! |---|---|
//! | `screen_grid/build` | one-off index build over N projected nodes |
//! | `screen_grid/hover_probe` | **THE claim**: one pointer probe costs a neighbourhood, not N |
//! | `screen_grid/hover_probe_linear` | the linear scan it replaced, same answer, same N |
//! | `labels/place` | collision-avoiding placement of N labels |
//! | `labels/place_offscreen_heavy` | N candidates, 500 on screen — cost must track the 500 |
//! | `edges/thin` | the per-cell ink budget over N segments |
//! | `frame/plan_30k_nodes_120k_edges` | the rollup: one whole navigator frame's plan |
//!
//! The linear arm is not padding: it is the control. Without it "the index is fast" is
//! a number with nothing to be fast *against*, and a regression that quietly restored
//! the scan would still look like a plausible absolute time.
//!
//! Plain numbers only (L3). Host-stamped by the runner; the authoritative run is the
//! bencher's. Run: `cargo bench -p facett-core --bench heavy_legibility`.
use std::hint::black_box;
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput};
use egui::{pos2, vec2, Pos2, Rect};
use facett_core::legibility::{
place_labels, plan_frame, thin_edges, EdgeThinOpts, FrameInput, FrameOpts, LabelCandidate,
PlaceOpts, ScreenGrid,
};
const VIEW_W: f32 = 1600.0;
const VIEW_H: f32 = 1000.0;
fn viewport() -> Rect {
Rect::from_min_size(pos2(0.0, 0.0), vec2(VIEW_W, VIEW_H))
}
/// Dataset sizes. `FACETT_BENCH_N` overrides (comma list).
fn sizes() -> Vec<usize> {
match std::env::var("FACETT_BENCH_N") {
Ok(v) => v.split(',').filter_map(|s| s.trim().parse().ok()).collect(),
Err(_) => vec![10_000, 100_000, 1_000_000],
}
}
/// A deterministic node cloud over the viewport (fixed xorshift — no RNG crate, so the
/// numbers are reproducible run to run and machine to machine).
fn cloud(n: usize) -> Vec<Pos2> {
let mut s = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
(s >> 11) as f32 / (1u64 << 53) as f32
};
(0..n).map(|_| pos2(next() * VIEW_W, next() * VIEW_H)).collect()
}
fn bench_screen_grid(c: &mut Criterion) {
let mut g = c.benchmark_group("screen_grid");
for n in sizes() {
let pts = cloud(n);
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("build", n), &n, |b, _| {
b.iter(|| black_box(ScreenGrid::build(black_box(&pts))));
});
let grid = ScreenGrid::build(&pts);
// One probe = one mouse-move's worth of work. Throughput is per PROBE (1), not
// per point — the whole point is that the probe does not touch the points.
g.throughput(Throughput::Elements(1));
g.bench_with_input(BenchmarkId::new("hover_probe", n), &n, |b, _| {
let mut k = 0u32;
b.iter(|| {
k = k.wrapping_add(1);
let p = pos2((k % 1600) as f32, ((k * 7) % 1000) as f32);
black_box(grid.nearest(black_box(&pts), p, 10.0))
});
});
// THE CONTROL — the scan the index replaced, on the identical data.
g.bench_with_input(BenchmarkId::new("hover_probe_linear", n), &n, |b, _| {
let mut k = 0u32;
b.iter(|| {
k = k.wrapping_add(1);
let p = pos2((k % 1600) as f32, ((k * 7) % 1000) as f32);
black_box(
pts.iter()
.enumerate()
.map(|(i, q)| (i, p.distance(*q)))
.filter(|&(_, d)| d <= 10.0)
.min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0))),
)
});
});
}
g.finish();
}
fn bench_labels(c: &mut Criterion) {
let mut g = c.benchmark_group("labels");
// Labels are bounded by what fits on a screen, so the sweep is smaller than the
// node sweep — but it still has to cover "far more candidates than can be drawn".
for n in [1_000usize, 10_000, 100_000] {
let cands: Vec<LabelCandidate> = cloud(n)
.into_iter()
.enumerate()
.map(|(i, p)| LabelCandidate::new(p, vec2(84.0, 13.0), (i % 997) as f32))
.collect();
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("place", n), &n, |b, _| {
b.iter(|| black_box(place_labels(black_box(&cands), viewport(), PlaceOpts::default())));
});
// The "cost tracks the screen" arm: n candidates, 500 of them on screen. A
// placer that considered everything would scale with n here.
let mut mixed: Vec<LabelCandidate> = cands[..500.min(n)].to_vec();
mixed.extend((0..n).map(|i| {
LabelCandidate::new(pos2(90_000.0 + i as f32, -70_000.0), vec2(84.0, 13.0), 1.0)
}));
g.bench_with_input(BenchmarkId::new("place_offscreen_heavy", n), &n, |b, _| {
b.iter(|| black_box(place_labels(black_box(&mixed), viewport(), PlaceOpts::default())));
});
}
g.finish();
}
fn bench_edges(c: &mut Criterion) {
let mut g = c.benchmark_group("edges");
for n in [10_000usize, 100_000, 500_000] {
let a = cloud(n);
let b_pts = cloud(n + 1);
let segs: Vec<(Pos2, Pos2)> =
a.iter().zip(b_pts.iter()).map(|(&x, &y)| (x, y)).collect();
// Weights MUST be supplied here. With an empty weight slice every sort key is
// equal and the already-index-ordered input collapses into one run, so the arm
// measures a best-case sort no caller ever gets — which is exactly how a 9x
// cost stayed hidden. A real navigator always has edge weights.
let weight: Vec<f32> = (0..n).map(|i| (i % 1009) as f32).collect();
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("thin", n), &n, |bh, _| {
bh.iter(|| {
black_box(thin_edges(
black_box(&segs),
&weight,
&[],
viewport(),
EdgeThinOpts::default(),
))
});
});
}
g.finish();
}
/// **The rollup** — one whole navigator frame's legibility plan: 30 000 nodes with
/// labels + 120 000 edges through the ink budget. This is the number that has to fit
/// inside a 16.7 ms 60 fps budget alongside everything else the frame does.
fn bench_frame(c: &mut Criterion) {
let nodes = 30_000usize;
let edges_n = 120_000usize;
let centres = cloud(nodes);
let label_size: Vec<egui::Vec2> = (0..nodes).map(|_| vec2(84.0, 13.0)).collect();
let label_priority: Vec<f32> = (0..nodes).map(|i| (i % 997) as f32).collect();
let label_pinned: Vec<bool> = (0..nodes).map(|i| i % 5000 == 0).collect();
let edges: Vec<(u32, u32)> = (0..edges_n)
.map(|i| ((i * 37 % nodes) as u32, ((i * 91 + 7) % nodes) as u32))
.collect();
let edge_always: Vec<bool> = (0..edges_n).map(|i| i % 4000 == 0).collect();
let edge_weight: Vec<f32> = (0..edges_n).map(|i| (i % 13) as f32).collect();
let mut g = c.benchmark_group("frame");
g.throughput(Throughput::Elements((nodes + edges_n) as u64));
// The two halves, separately — so a regression in the rollup can be attributed
// instead of guessed at.
g.bench_function("plan_labels_only_30k", |b| {
b.iter(|| {
black_box(plan_frame(
&FrameInput {
centres: black_box(¢res),
label_size: &label_size,
label_priority: &label_priority,
label_pinned: &label_pinned,
edges: &[],
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
},
FrameOpts { thin_edges: false, ..FrameOpts::legible() },
))
});
});
g.bench_function("plan_edges_only_120k", |b| {
b.iter(|| {
black_box(plan_frame(
&FrameInput {
centres: black_box(¢res),
label_size: &[],
label_priority: &[],
label_pinned: &[],
edges: &edges,
edge_always: &edge_always,
edge_weight: &edge_weight,
viewport: viewport(),
},
FrameOpts { thin_labels: false, ..FrameOpts::legible() },
))
});
});
g.bench_function("plan_30k_nodes_120k_edges", |b| {
b.iter(|| {
black_box(plan_frame(
&FrameInput {
centres: black_box(¢res),
label_size: &label_size,
label_priority: &label_priority,
label_pinned: &label_pinned,
edges: &edges,
edge_always: &edge_always,
edge_weight: &edge_weight,
viewport: viewport(),
},
FrameOpts::legible(),
))
});
});
g.finish();
}
criterion_group!(benches, bench_screen_grid, bench_labels, bench_edges, bench_frame);
criterion_main!(benches);