facett-map/tests/draw_list_memo.rs
//! **The CPU draw list is built once per distinct frame, not once per frame** — proven
//! by counting the work (LAW 2), and proven not to go stale by breaking the key.
//!
//! `MapFacet::features_for_cpu` allocated a fresh `Vec<DrawFeature>`, walked every
//! enabled layer through `MapLayer::features_into` — computing a `PaintKey` per feature —
//! and re-sorted the whole list, **every frame**. Nothing invalidated it, so a still
//! screen paid exactly what a pan paid.
//!
//! # The result is WORK ELIMINATED, not milliseconds
//!
//! Absolute frame times on this box are contention-dominated and must not be quoted as a
//! speed-up. Lane BENCH measured korp's `map_speed` on the same binary and the same
//! fixture at **15.91 ms and 36.78 ms four minutes apart**, with the box load ranging
//! **39–262 on 32 cores**, while the vertex count came back at 383 708 on every single
//! run — only the clock moved. So the primary oracle here is a COUNT, which is
//! deterministic and does not depend on who else is building.
//!
//! Over 501 identical asks of the 20 000-way fixture below
//! (`a_still_frame_never_rebuilds_the_draw_list`):
//!
//! | | before | after |
//! |---|---:|---:|
//! | layer walks (`features_into` passes) | 501 | **1** |
//! | features materialised = `way_paint_key` computations = sort comparands | 10 020 000 | **20 000** |
//! | `sort_by_key` passes over the whole list | 501 | **1** |
//!
//! One build per *distinct* frame instead of one per frame. `an_invalidated_frame_…`
//! also prints a wall-clock pair; it is there to show the cost genuinely returns when the
//! memo is invalidated, **not** as a speed-up figure, and it is labelled accordingly.
//!
//! # Why a counter and not the output
//!
//! Same argument as `frame_churn_memo.rs` and `MapLayer::ear_clips`: "it is cached" is a
//! claim about work that did NOT happen, and the painted frame is byte-identical either
//! way. So the oracle is `MapFacet::draw_list_build_count()` /
//! `draw_list_feature_count()` — the counters the build body itself bumps — never the
//! list that comes back.
//!
//! # The gates, and the red arm for each
//!
//! | gate | claim | red arm |
//! |---|---|---|
//! | `a_still_frame_never_rebuilds_the_draw_list` | N identical frames ⇒ ONE walk, ONE sort, 20 000 paint keys | pan the camera between frames: the counters climb once per frame (asserted in the next test, so the green is not vacuous) |
//! | `an_invalidated_frame_rebuilds_every_time` | every frame that changes an input rebuilds | *is* the red arm — the counters climb 1:1 with the frames |
//! | `the_key_covers_the_camera` / `..._the_layer_roster` / `..._the_lane` | changing each keyed input changes the LIST | drop that field from `DrawListKey` and the matching assertion fires — swept field by field, table below |
//! | `the_key_covers_bearing_and_tilt` | a layer that reads `bearing_deg`/`tilt_deg` is not served a stale list | no in-crate layer reads them, so the arm is a `MapLayer` written here that does |
//! | `hit_ratio_over_a_pan_zoom_sequence` | the honest ratio, not a still-frame ratio | — it is a measurement, and it prints both halves |
//!
//! Run it:
//! ```text
//! CARGO_TARGET_DIR=~/scratch/cargo/facett-memo \
//! cargo test -p facett-map --release --test draw_list_memo -- --nocapture
//! ```
use egui::Color32;
use facett_map::Way;
use facett_map::layer::{
DrawFeature, DrawGeom, LatLon, LayerKind, LayerStyle, MapFacet, MapLayer, MapTheme, MapView,
PointsLayer, WaysLayer,
};
const PANE: (f32, f32) = (1600.0, 1000.0);
/// A dense way set with the shape a decoded OSM way actually has — ~30 vertices, a
/// quarter of them closed filled rings (lakes), the rest polylines (roads). Sized and
/// placed so that at zoom 12 over the fixture's centre **every** way reaches the
/// painter: a fixture that culls most of itself would make every number below a
/// measurement of the cull.
fn ways(n: usize) -> Vec<Way> {
let mut v = Vec::with_capacity(n);
for k in 0..n {
let f = k as f64;
let y = 59.0 + (f * 0.00013) % 0.20;
let x = 18.0 + (f * 0.00021) % 0.30;
let ring: Vec<(f64, f64)> =
(0..30).map(|j| (x + j as f64 * 0.0004, y + ((j % 5) as f64) * 0.0003)).collect();
if k % 4 == 0 {
let mut r = ring.clone();
r.push(ring[0]);
v.push(Way::filled(k as i64, "water", r, Color32::BLUE, Color32::DARK_BLUE, 1.0));
} else {
v.push(Way::line(k as i64, "road", ring, Color32::GRAY, 2.0));
}
}
v
}
fn view() -> MapView {
MapView::new(LatLon::new(59.1, 18.15), 12.0, PANE)
}
fn facet(n: usize) -> MapFacet {
MapFacet::new("memo", view(), MapTheme::default())
.with_layer(Box::new(WaysLayer::new("w", ways(n))))
}
/// The frame's own entry point: the `Arc` `MapFacet::ui` paints out of, through the
/// public test hook. `&[]`/`GpuOwns::NONE` is the pure-CPU frame.
fn frame(f: &MapFacet) -> std::sync::Arc<Vec<DrawFeature>> {
f.features_for_cpu_for_test(&[], false, false)
}
// ── GATE 1 — GREEN: the still frame ──────────────────────────────────────────
/// **A still screen builds the draw list ONCE.** Same camera, same layer set, no
/// toggles, 500 frames.
///
/// Non-vacuity is asserted twice over: the fixture must really produce a full 20 000
/// features (a facet that draws nothing would build an empty list very quickly), and
/// every frame's list must be the same `Arc` — a memo that rebuilt an *equal* list would
/// satisfy a length check and fail this.
#[test]
fn a_still_frame_never_rebuilds_the_draw_list() {
let f = facet(20_000);
let first = frame(&f);
assert_eq!(first.len(), 20_000, "fixture: every way must reach the painter, or this is vacuous");
assert_eq!(f.draw_list_build_count(), 1, "the first frame builds");
for _ in 0..500 {
let again = frame(&f);
assert!(
std::sync::Arc::ptr_eq(&first, &again),
"a still frame must be served the SAME list, not an equal one"
);
}
let asks = 501;
let builds = f.draw_list_build_count();
let feats = f.draw_list_feature_count();
// THE RESULT, in the deterministic units: walks, paint keys, sorts.
eprintln!(
"work eliminated over {asks} identical asks: layer walks {builds}/{asks}, \
sorts {builds}/{asks}, features materialised (= way_paint_key computations \
= sort comparands) {feats}/{}",
asks * 20_000
);
assert_eq!(builds, 1, "501 unchanged asks must walk and sort the layers exactly once");
assert_eq!(
feats, 20_000,
"…and must materialise each feature — and so compute each PaintKey — exactly once"
);
}
// ── GATE 2 — RED, and it is seen: invalidate every frame ─────────────────────
/// **Force invalidation on every frame and the work comes straight back.** This is the
/// red arm for the test above, and it is a REAL invalidation (a one-pixel pan is what a
/// dragging finger does), not a test hook that reaches into the memo.
///
/// The ASSERTED result is the counters: 60 moving frames ⇒ 60 walks, 60 sorts and
/// 60 × 20 000 paint keys, against the still run's zero. The wall-clock pair it prints is
/// **not a speed-up figure** — absolute ms on this box are contention-dominated (see the
/// file header) — it is only there to show the cost is genuinely restored rather than
/// silently absorbed. The one thing asserted on it is an ORDER-OF-MAGNITUDE floor, which
/// survives the noise; the same test reads 2.88–3.12 ms in release and 24.9 ms in debug
/// on the same box, which is itself the argument for not quoting either as the win.
#[test]
fn an_invalidated_frame_rebuilds_every_time() {
let mut f = facet(20_000);
let frames = 60;
// ── still ──
let _ = frame(&f);
let base = f.draw_list_build_count();
let feats_base = f.draw_list_feature_count();
let t = std::time::Instant::now();
let mut acc = 0usize;
for _ in 0..frames {
acc += frame(&f).len();
}
let still = t.elapsed().as_secs_f64() / f64::from(frames);
assert_eq!(f.draw_list_build_count(), base, "the still run must not have rebuilt at all");
assert_eq!(
f.draw_list_feature_count(),
feats_base,
"…and must not have materialised a single feature"
);
// ── invalidated: a genuine one-pixel pan per frame ──
let t = std::time::Instant::now();
for _ in 0..frames {
f.view_mut().pan_by_px(1.0, 0.0);
acc += frame(&f).len();
}
let moving = t.elapsed().as_secs_f64() / f64::from(frames);
let builds = f.draw_list_build_count() - base;
let feats = f.draw_list_feature_count() - feats_base;
eprintln!(
"invalidated every frame: {builds}/{frames} layer walks, {builds}/{frames} sorts, \
{feats} features materialised (still run: 0 / 0 / 0). \
Wall clock, NOT a speed-up figure and contention-dominated on this box: \
still {:.0} ns/frame, rebuild {:.3} ms/frame (acc {acc})",
still * 1e9,
moving * 1e3
);
assert_eq!(
builds, frames as usize,
"a camera that moves every frame must rebuild every frame — {builds} builds in {frames} frames"
);
assert_eq!(
feats,
frames as usize * 20_000,
"…and re-materialise every feature, so re-compute every PaintKey, every frame"
);
// An order-of-magnitude FLOOR, not a measurement: it holds in debug and in release,
// loaded box or idle, and its only job is to catch a memo that has quietly become a
// rebuild while the counters are still somehow satisfied.
assert!(
still * 20.0 < moving,
"the memoised ask must be at least 20x cheaper than the rebuild \
(still {still:e}s, rebuild {moving:e}s)"
);
}
// ── GATE 3 — the key must not serve a stale list ─────────────────────────────
//
// One assertion per keyed input. Each changes exactly that input and demands the LIST
// change — an applied-output oracle, never a counter, because a counter that climbed
// while the list stayed stale would be the exact bug this section exists to catch.
//
// SEEN RED on oden 2026-08-31 by dropping each field from `DrawListKey` in turn (the
// field was neutralised at the key's construction site — `epoch: 0`, `view: MapView {
// center: LatLon::new(0.0, 0.0), ..self.view }`, and so on) and re-running the file:
//
// dropped from the key arm that fired
// ------------------------ ---------------------------------------------------------
// epoch the_key_covers_the_layer_roster
// view.center the_key_covers_the_camera (+ an_invalidated_frame…, hit_ratio…)
// view.zoom the_key_covers_the_camera (+ hit_ratio…)
// view.size_px the_key_covers_the_camera
// view.bearing_deg + tilt the_key_covers_bearing_and_tilt
// gpu_layers the_key_covers_the_lane
// gpu_owns the_key_covers_the_lane
//
// An input that cannot be made to fail is an input that is not really in the key — and
// the sweep earned its keep immediately: `view.size_px` came back ALL GREEN on the first
// pass, because the arm's preceding ask had already changed the key. The arm now primes
// the memo at the baseline camera first, and the sweep turns it red.
/// A cheap identity for a draw list: what it draws, in what order, with which geometry
/// kind. Two lists that agree here are the same picture.
fn shape(feats: &[DrawFeature]) -> Vec<(i64, i32, u8)> {
feats
.iter()
.map(|f| {
let kind = match f.geom {
DrawGeom::Point(_) => 0u8,
DrawGeom::Line(_) => 1,
DrawGeom::Polygon { .. } => 2,
DrawGeom::Label { .. } => 3,
DrawGeom::Glow { .. } => 4,
};
(f.id, f.order.rank, kind)
})
.collect()
}
/// **`view.center`, `view.zoom` and `view.size_px` are all in the key.** Each is moved
/// on its own, from the same still baseline, and each must change the picture.
#[test]
fn the_key_covers_the_camera() {
let mut f = facet(4_000);
let base = shape(&frame(&f));
assert!(!base.is_empty(), "fixture: the baseline must draw something");
// centre — pan right off the fixture's eastern half.
f.view_mut().center.lon += 0.20;
let panned = shape(&frame(&f));
assert_ne!(panned, base, "a panned camera must not be served the old draw list");
// zoom — back to centre, then out to the country tier where the LOD gate bites.
*f.view_mut() = view();
assert_eq!(shape(&frame(&f)), base, "sanity: the camera really is back where it started");
f.view_mut().zoom = 3.0;
let zoomed = shape(&frame(&f));
assert_ne!(zoomed, base, "a zoomed camera must not be served the old draw list");
// size_px — a pane a tenth the width shows a tenth of the world. The memo is primed
// at the baseline camera FIRST, so the only thing that differs at the next ask is the
// pane size; without that prime this arm passes even with `size_px` out of the key,
// because the *previous* ask (zoom 3.0) already made the key differ. That is exactly
// the vacuity the red sweep caught.
*f.view_mut() = view();
assert_eq!(shape(&frame(&f)), base, "sanity: prime the memo at the baseline camera");
f.view_mut().size_px = (160.0, 100.0);
let resized = shape(&frame(&f));
assert_ne!(resized, base, "a resized pane must not be served the old draw list");
}
/// **`layer_epoch` is in the key.** All three `&mut self` roster ops are exercised, not
/// just the convenient one: a memo keyed on a field that only `toggle_layer` bumps would
/// pass a one-op test and still serve a stale list after `push_layer`.
#[test]
fn the_key_covers_the_layer_roster() {
let mut f = facet(4_000);
let base = shape(&frame(&f));
f.set_layer_enabled("w", false);
let off = shape(&frame(&f));
assert!(off.is_empty(), "a stack with nothing enabled draws nothing");
assert_ne!(off, base, "a disabled layer must not be served the old draw list");
f.toggle_layer("w");
assert_eq!(shape(&frame(&f)), base, "toggling back must restore the same picture");
f.push_layer(Box::new(PointsLayer::new(
"pts",
(0..200).map(|i| (18.10 + f64::from(i) * 1e-4, 59.10)).collect(),
Color32::RED,
)));
let pushed = shape(&frame(&f));
assert_ne!(pushed, base, "a pushed layer must not be served the old draw list");
assert!(pushed.len() > base.len(), "…and its features must actually be in the list");
}
/// **`gpu_layers` and `gpu_owns` are in the key.** `way_lane_plan` re-decides them every
/// frame, so two frames at the same camera and epoch genuinely differ here — and the
/// three ownership states must each give a different CPU list.
#[test]
fn the_key_covers_the_lane() {
let f = facet(4_000);
let cpu = shape(&f.features_for_cpu_for_test(&[], false, false));
let lines = shape(&f.features_for_cpu_for_test(&[0], true, false));
let fills = shape(&f.features_for_cpu_for_test(&[0], false, true));
let both = shape(&f.features_for_cpu_for_test(&[0], true, true));
assert_ne!(lines, cpu, "a layer taken for its LINES must not be served the pure-CPU list");
assert_ne!(fills, cpu, "a layer taken for its FILLS must not be served the pure-CPU list");
assert!(both.is_empty(), "a layer taken for both leaves the CPU painter nothing");
// …and `gpu_layers` itself, separately from `gpu_owns`: same ownership, no layer named.
assert_eq!(
shape(&f.features_for_cpu_for_test(&[], true, true)),
cpu,
"naming NO layer must leave every feature on the CPU whatever `gpu_owns` says"
);
// …and the memo is ONE slot, so what it must serve is the state it was last asked
// for. (A frame asks once; `way_lane_plan` gives the same answer to every frame of an
// unchanged pane, so a second slot would buy nothing and cost a way-set's memory.)
let n = f.draw_list_build_count();
for _ in 0..10 {
let _ = f.features_for_cpu_for_test(&[], true, true);
}
assert_eq!(f.draw_list_build_count(), n, "repeating the LAST lane state must be a hit");
}
// ── the bearing/tilt arm: a layer that actually reads them ───────────────────
/// A `MapLayer` whose feature set depends on **`bearing_deg`** — one point per whole
/// 90° of compass heading.
///
/// It exists because none of the four layers in `layer.rs` reads bearing or tilt (their
/// culling goes through `MapView::merc_bbox`, which is deliberately rotation-agnostic),
/// so without it the key's camera coverage could not be shown red for those two fields —
/// and `MapLayer` is a PUBLIC trait: a korp collector's own layer may read the whole
/// camera and would be handed a stale list by a key that only carried three of the
/// camera's five fields.
struct BearingLayer {
style: LayerStyle,
enabled: bool,
}
impl MapLayer for BearingLayer {
fn id(&self) -> &str {
"bearing"
}
fn kind(&self) -> LayerKind {
LayerKind::Point
}
fn features(&self, view: &MapView) -> Vec<DrawFeature> {
let n = (view.bearing_deg / 90.0) as i64 + (view.tilt_deg / 30.0) as i64 * 10;
(0..=n)
.map(|i| DrawFeature {
id: i,
geom: DrawGeom::Point(LatLon::new(59.1, 18.15)),
color: self.style.color,
width: self.style.width,
fill: None,
order: facett_map::PaintKey::simple(facett_map::paint_order::POINT_BAND, facett_map::Lod::Country, i),
tri: None,
lod: facett_map::Lod::Country,
dash: false,
})
.collect()
}
fn style(&self) -> &LayerStyle {
&self.style
}
fn enabled(&self) -> bool {
self.enabled
}
fn set_enabled(&mut self, on: bool) {
self.enabled = on;
}
}
/// **A layer that reads `bearing_deg` / `tilt_deg` is not served a stale list.**
///
/// RED: drop `view` from `DrawListKey` and key on `(epoch, zoom, center, size_px)`
/// instead — this fires and the three camera assertions above still pass, which is
/// exactly the hole a narrower key would leave.
#[test]
fn the_key_covers_bearing_and_tilt() {
let mut f = MapFacet::new("bearing", view(), MapTheme::default()).with_layer(Box::new(
BearingLayer { style: LayerStyle::new(LayerKind::Point, Color32::RED, 2.0), enabled: true },
));
let base = frame(&f).len();
f.view_mut().bearing_deg = 180.0;
assert_ne!(frame(&f).len(), base, "a rotated camera must not be served the old draw list");
f.view_mut().bearing_deg = 0.0;
assert_eq!(frame(&f).len(), base, "sanity: bearing back ⇒ the same list");
f.view_mut().tilt_deg = 60.0;
assert_ne!(frame(&f).len(), base, "a pitched camera must not be served the old draw list");
}
// ── GATE 4 — the honest hit ratio ────────────────────────────────────────────
/// **The hit ratio over a realistic pan/zoom sequence, not over a still screen.**
///
/// A memo that always hits is a bug and a memo that never hits buys nothing, so the
/// number that matters is the one a user's hand produces: a drag is ~15 moving frames,
/// and the pane then sits still while the eye reads it. This walks four drags and two
/// wheel notches with 60-frame dwells between them — 60 Hz, so a dwell is one second —
/// and prints the ratio it actually got.
///
/// The ratio itself is a property of THIS script, not of the memo, so what is asserted is
/// the mechanism underneath it: it must hit, it must miss, and the build count must be
/// exactly the moving frames — every dwell frame a hit, every gesture frame a rebuild.
/// Change the script and the printed percentage moves; the `builds` equality moves with
/// it and stays the thing worth checking.
#[test]
fn hit_ratio_over_a_pan_zoom_sequence() {
let mut f = facet(4_000);
let mut asks = 0usize;
for step in 0..6 {
// The gesture: 15 frames of movement.
for _ in 0..15 {
if step % 3 == 2 {
f.view_mut().zoom_by_scroll(6.0);
} else {
f.view_mut().pan_by_px(4.0, 2.0);
}
let _ = frame(&f);
asks += 1;
}
// The dwell: one second of a still pane.
for _ in 0..60 {
let _ = frame(&f);
asks += 1;
}
}
let builds = f.draw_list_build_count();
let hits = asks - builds;
eprintln!(
"pan/zoom sequence: {asks} frames, {builds} builds, {hits} hits — hit ratio {:.1} %",
100.0 * hits as f64 / asks as f64
);
assert!(builds > 0, "a moving camera must rebuild — a memo that always hits is a bug");
assert!(hits > 0, "a still pane must be served — a memo that never hits buys nothing");
assert_eq!(
builds, 90,
"exactly the 6×15 moving frames rebuild; every dwell frame is a hit"
);
}