facett-geomap/benches/heavy_navigator.rs
//! **HEAVY benchmark — the OSM 2D NAVIGATOR frame budget.**
//!
//! "FAST RENDERING" is an explicit requirement of the navigator, and a rendering
//! claim without a number is not done (L3). This benches the parts a navigator
//! frame is actually made of, not "draw a map":
//!
//! | arm | what it measures |
//! |---|---|
//! | `point_grid/build` | one-off spatial index build over N points |
//! | `point_grid/cull_whole_country` | the per-frame viewport cull with everything on screen |
//! | `point_grid/cull_city_block` | THE claim: a zoomed-in frame costs what is ON SCREEN, not N |
//! | `point_grid/cull_lod_stride8` | the same cull with LOD decimation |
//! | `camera/project_f64_to_px` | the f64 Mercator → screen projection, per point |
//! | `pins/cluster` | screen-space pin clustering, per pin |
//! | `points/lod_decision` | the building-vertex LOD verdict, per frame |
//! | `points/cull_then_lod_wide` | cull + LOD at a ZOOMED-OUT camera (the sea case) |
//! | `frame/cull_1m_plus_cluster_5k_pins` | the rollup: one navigator frame |
//!
//! Every arm carries a `Throughput::Elements` so the report is in points/s and
//! pins/s (plain numbers, L3), and the dataset sizes sweep 10k → 1M so the
//! "cost tracks the viewport, not the dataset" claim is a measured curve rather
//! than an assertion.
//!
//! Run: `cargo bench -p facett-geomap`
use std::hint::black_box;
use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main};
use facett_geomap::mercator;
use facett_geomap::osm2d::{MercatorCamera, OsmView, PointGrid, cluster};
/// Dataset sizes swept by the point arms. `GEOMAP_BENCH_N` overrides (comma list).
fn point_sizes() -> Vec<usize> {
match std::env::var("GEOMAP_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 Sweden-shaped point cloud (no RNG crate: a fixed xorshift so
/// the numbers are reproducible run to run and machine to machine).
fn points(n: usize) -> Vec<(f64, f64)> {
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 11) as f64 / (1u64 << 53) as f64
};
(0..n).map(|_| (11.0 + next() * 13.0, 55.0 + next() * 14.0)).collect()
}
const RECT: egui::Rect = egui::Rect { min: egui::pos2(0.0, 0.0), max: egui::pos2(1600.0, 1000.0) };
/// A camera framing the whole country (the "everything on screen" worst case) and
/// one zoomed into a city block (the "cost must not track N" case).
fn cameras() -> (MercatorCamera, MercatorCamera) {
let (x0, y0) = mercator(11.0, 69.0);
let (x1, y1) = mercator(24.0, 55.0);
let mut wide = MercatorCamera::default();
wide.fit_merc_bbox([x0.min(x1), y0.min(y1), x0.max(x1), y0.max(y1)], RECT);
let mut close = wide;
for _ in 0..8 {
close.zoom_by(2.0);
// `zoom_by` moves `target_zoom`; the live `zoom` (which
// `viewport_merc_bbox` reads) eases toward it. Settle it here, or the
// "close" camera is byte-identical to the wide one and this arm silently
// benches the same viewport twice.
while close.tick() {}
}
assert!(
close.zoom > wide.zoom * 100.0,
"the close camera must really be zoomed in ({} vs {})",
close.zoom,
wide.zoom
);
(wide, close)
}
fn bench_point_grid(c: &mut Criterion) {
let mut g = c.benchmark_group("point_grid");
for n in point_sizes() {
let pts = points(n);
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("build", n), &n, |b, _| {
b.iter(|| PointGrid::build(black_box(pts.clone())))
});
let grid = PointGrid::build(pts.clone());
let (wide, close) = cameras();
let wide_bbox = wide.viewport_merc_bbox(RECT);
let close_bbox = close.viewport_merc_bbox(RECT);
let mut out = Vec::with_capacity(1 << 16);
g.bench_with_input(BenchmarkId::new("cull_whole_country", n), &n, |b, _| {
b.iter(|| {
grid.visible_into(black_box(wide_bbox), 1, &mut out);
black_box(out.len())
})
});
// THE claim: a zoomed-in frame must cost about what is on screen, not N.
g.bench_with_input(BenchmarkId::new("cull_city_block", n), &n, |b, _| {
b.iter(|| {
grid.visible_into(black_box(close_bbox), 1, &mut out);
black_box(out.len())
})
});
g.bench_with_input(BenchmarkId::new("cull_lod_stride8", n), &n, |b, _| {
b.iter(|| {
grid.visible_into(black_box(wide_bbox), 8, &mut out);
black_box(out.len())
})
});
}
g.finish();
}
/// A deterministic **road network** of `n` short ways spread over the same
/// Sweden-shaped extent as [`points`], plus a handful of country-spanning
/// coastline ways (the "oversized bbox" case a grid index has to handle without
/// exploding). Built through the real `Way::from_lonlat` so the styles / LOD
/// tiers / bboxes are exactly what the viewer indexes.
fn ways(n: usize) -> Vec<facett_map::Way> {
let th = facett_core::Theme::default();
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 11) as f64 / (1u64 << 53) as f64
};
let road = |k: &str| vec![("highway".to_owned(), k.to_owned())];
let mut out: Vec<facett_map::Way> = Vec::with_capacity(n + 8);
for i in 0..n {
let (lon, lat) = (11.0 + next() * 13.0, 55.0 + next() * 14.0);
// ~30–120 m segments: the real thing a city-block viewport must isolate.
let (dx, dy) = (0.0004 + next() * 0.001, 0.0004 + next() * 0.001);
let kind = match i % 8 {
0 => "motorway",
1 => "primary",
2 => "secondary",
_ => "residential",
};
if let Some(w) = facett_map::Way::from_lonlat(
i as i64,
&[(lon, lat), (lon + dx, lat + dy), (lon + 2.0 * dx, lat + dy * 0.5)],
&road(kind),
&th,
) {
out.push(w);
}
}
// Four coastline ways spanning the whole country — a single one of these makes
// a naive "insert into every overlapping cell" grid blow up, so the index has
// to carry them in an oversized overflow list.
for k in 0..4 {
let lon = 11.0 + k as f64 * 3.0;
let ring: Vec<(f64, f64)> =
(0..64).map(|j| (lon + (j as f64) * 0.05, 55.0 + (j as f64) * 0.21)).collect();
if let Some(w) = facett_map::Way::from_lonlat(
-(k as i64) - 1,
&ring,
&[("natural".to_owned(), "coastline".to_owned())],
&th,
) {
out.push(w);
}
}
out
}
/// **The way layer** — the other half of a navigator frame, and the same "cost
/// must track the screen, not the dataset" claim the point grid makes.
///
/// | arm | what it measures |
/// |---|---|
/// | `way_index/build` | one-off LOD partition + spatial index over N ways |
/// | `way_index/query_whole_country` | the per-frame way cull, everything on screen |
/// | `way_index/query_city_block` | THE claim: a street-level frame costs what is ON SCREEN |
/// | `way_index/origin` | the data-local GPU origin the paint path needs every frame |
fn bench_way_index(c: &mut Criterion) {
let mut g = c.benchmark_group("way_index");
for n in point_sizes() {
let ws = ways(n);
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("build", n), &n, |b, _| {
b.iter(|| facett_map::index::MapIndex::build(black_box(ws.clone())))
});
let idx = facett_map::index::MapIndex::build(ws.clone());
let (wide, close) = cameras();
let wide_bbox = wide.viewport_merc_bbox(RECT);
let close_bbox = close.viewport_merc_bbox(RECT);
g.bench_with_input(BenchmarkId::new("query_whole_country", n), &n, |b, _| {
b.iter(|| black_box(idx.query_visible(black_box(wide_bbox), 2).len()))
});
// THE claim: a street-level frame must cost about what is on screen, not N.
g.bench_with_input(BenchmarkId::new("query_city_block", n), &n, |b, _| {
b.iter(|| black_box(idx.query_visible(black_box(close_bbox), 2).len()))
});
// The GPU line path needs the dataset's Mercator bbox-min every frame. It is
// a CONSTANT of the dataset, so anything that scales with N here is pure
// waste repeated 60 times a second.
g.bench_with_input(BenchmarkId::new("origin", n), &n, |b, _| {
b.iter(|| black_box(idx.origin()))
});
}
g.finish();
}
fn bench_project(c: &mut Criterion) {
let mut g = c.benchmark_group("camera");
let n = 200_000usize;
let pts = points(n);
let merc: Vec<(f64, f64)> = pts.iter().map(|&(lon, lat)| mercator(lon, lat)).collect();
let (wide, _) = cameras();
g.throughput(Throughput::Elements(n as u64));
g.bench_function("project_f64_to_px", |b| {
b.iter(|| {
let mut acc = 0.0f32;
for &(mx, my) in &merc {
let p = wide.to_px(black_box(mx), black_box(my), RECT);
acc += p.x;
}
black_box(acc)
})
});
g.finish();
}
fn bench_pin_cluster(c: &mut Criterion) {
let mut g = c.benchmark_group("pins");
for n in [1_000usize, 10_000, 100_000] {
// A dense screen-space pile: exactly the case clustering exists for.
let projected: Vec<(egui::Pos2, String, String)> = (0..n)
.map(|i| {
let x = ((i * 37) % 1600) as f32;
let y = ((i * 53) % 1000) as f32;
(egui::pos2(x, y), format!("p{i}"), format!("p{i}"))
})
.collect();
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("cluster", n), &n, |b, _| {
b.iter(|| {
black_box(
cluster::cluster_projected(black_box(&projected), cluster::CLUSTER_BIN_PX).len(),
)
})
});
}
g.finish();
}
/// **The BUILDING-VERTEX LOD.** The verdict that stops a zoomed-out frame painting
/// a sea of corner dots has to be *cheaper than the drawing it prevents*, or the
/// cure costs more than the disease. Two arms:
///
/// * `lod_decision` — the verdict alone (pure arithmetic over the dot count), which
/// is what every frame pays whether it draws or not;
/// * `cull_then_lod_wide` — the whole zoomed-out point path: viewport cull, then
/// the verdict. This is the frame the owner was looking at, and its cost is now the
/// cull plus a few flops, with the tens of thousands of `circle_filled`
/// tessellations it used to emit removed entirely.
fn bench_point_lod(c: &mut Criterion) {
let mut g = c.benchmark_group("points");
let v = OsmView::new("bench", Vec::new(), Vec::new());
let dot = OsmView::point_dot_px(1_000_000.0);
g.throughput(Throughput::Elements(1));
g.bench_function("lod_decision", |b| {
b.iter(|| black_box(v.points_pass_lod(black_box(40_000), black_box(dot), black_box(RECT))))
});
g.finish();
let mut g = c.benchmark_group("points");
for n in point_sizes() {
let grid = PointGrid::build(points(n));
let (wide, _) = cameras();
let bbox = wide.viewport_merc_bbox(RECT);
let dot = OsmView::point_dot_px(wide.zoom);
let mut out = Vec::with_capacity(1 << 16);
g.throughput(Throughput::Elements(n as u64));
g.bench_with_input(BenchmarkId::new("cull_then_lod_wide", n), &n, |b, _| {
b.iter(|| {
grid.visible_into(black_box(bbox), 1, &mut out);
black_box(v.points_pass_lod(out.len(), dot, RECT))
})
});
}
g.finish();
}
/// The ROLLUP: one navigator frame's worth of work — cull the visible points,
/// then cluster the pin overlay — at a realistic 1M-point / 5k-pin load.
fn bench_frame(c: &mut Criterion) {
let mut g = c.benchmark_group("frame");
let n = 1_000_000usize;
let grid = PointGrid::build(points(n));
let (_, close) = cameras();
let bbox = close.viewport_merc_bbox(RECT);
let pins: Vec<(egui::Pos2, String, String)> = (0..5_000)
.map(|i| {
let x = ((i * 37) % 1600) as f32;
let y = ((i * 53) % 1000) as f32;
(egui::pos2(x, y), format!("pin{i}"), String::new())
})
.collect();
let mut out = Vec::with_capacity(1 << 16);
g.throughput(Throughput::Elements(n as u64));
g.bench_function("cull_1m_plus_cluster_5k_pins", |b| {
b.iter(|| {
grid.visible_into(black_box(bbox), 1, &mut out);
let nodes = cluster::cluster_projected(black_box(&pins), cluster::CLUSTER_BIN_PX);
black_box(out.len() + nodes.len())
})
});
g.finish();
}
criterion_group!(
benches,
bench_point_grid,
bench_way_index,
bench_project,
bench_pin_cluster,
bench_point_lod,
bench_frame
);
criterion_main!(benches);