nordisk/facett

OSM 2D — where the frame time actually went

nornir:class=design

The 2D navigator was reported slow on a 32-core Threadripper PRO with an RTX 4090. This is the measurement, the cause, and the fix. Only the chosen design is named (L8); the rejected alternatives are not.

f0 — the short version

1. It was not the GPU. .nornir/gpu-adapter-selection-design.md establishes, with the enumeration printed, that facett was already rendering on the RTX 4090 — not llvmpipe, not the ASPEED BMC (which does not even enumerate: it has no render node and no Vulkan/GL driver). The adapter hypothesis is refuted.

2. It was the CPU, in MapIndex — and it was the same bug class that had already been found three times in three files: a "cost tracks what is on screen" claim whose implementation actually tracked the dataset.

3. Two full-dataset scans per frame, both in the way layer:

   • MapIndex::query_visible — a brute-force bbox test over every way in the dataset, every frame;
   • facett_map::gpu::ways_origin(...) — the data-local GPU origin, a constant of the way set, re-derived by walking every way in the dataset, every frame.

At the demo's ceiling of MAX_WAYS_2D = 400000 that is millions of bbox tests a second before a single pixel is drawn. At 1000000 ways the two together cost 19094600 ns per frame — a 52 ms frame from CPU book-keeping alone, on a box whose GPU was idle.

1. After the fix the same street-level frame costs 1435 ns, an 8084x reduction on the cull and effectively O(1) on the origin.

f1 — the bug, precisely

facett-map/src/index.rs, before:

/// CPU-fallback visibility query: ways in tiers up to the zoom's LOD whose
/// bbox intersects the viewport. Brute-force (the GPU path culls on-device).
pub fn query_visible(&self, vp: [f32; 4], lod: u32) -> Vec<&Way> {
    …
    out.extend(tier.iter().filter(|w| hit(w)));   // every way, every frame
}

The doc comment contains the excuse and the mistake: "the GPU path culls on-device". It does — for the line layer. But OsmView::view calls query_visible on every frame regardless of whether the GPU lane drew, because the visible way set also feeds:

• the filled silhouettes (Sutherland–Hodgman clip + filled_mesh, always CPU),
• the road-name label layer (candidate collection + collision placement),
• last_vis_ways, published in state_json.

So the GPU fast path never removed the scan; it sat next to it. "Brute-force because the GPU culls" was true of one consumer and false of the function.

The second one, in facett-geomap/src/osm2d.rs::draw_ways_gpu:

let Some(origin) = facett_map::gpu::ways_origin(self.ways.gpu_ways().map(|(w, _)| w)) else { … };

ways_origin folds a min over every way's bbox — the dataset's Mercator bbox-min. That value cannot change: ways are immutable after build, and recolor only touches colours. It was recomputed 60 times a second. The GPU geometry upload next to it is correctly latched behind an AtomicBool; the origin feeding it was not.

The pattern, now seen four times

The tell is always the same: an arm that is supposed to be viewport-bound times identically to the arm that is dataset-bound. way_index/query_city_block timing worse than way_index/query_whole_country (11601000 vs 10512000 ns at 1M) is that signature exactly — the city block scanned the same N and merely collected fewer results.

f2 — the fix

f2.1 A uniform grid per LOD tier, spanning the tier's own bbox

Same shape as the PointGrid cure, because the mistake was the same. Each of the three LOD tiers gets a lattice sized for ~8 ways per cell (side = sqrt(n/8), clamped 1..=256) laid over that tier's bounding box — never the world, which is what collapsed a regional dataset into a corner last time.

Storage is CSR, not Vec<Vec<u32>>. A 256×256 lattice is 65536 cells; one Vec per cell is 65536 heap allocations to build and a pointer chase per cell to query. Two flat arrays (starts: Vec<u32> of cols*rows+1, items: Vec<u32>) cost one allocation each, make the build a counting sort, and — because cells in a lattice row are adjacent in items — let a query walk one contiguous slice per row instead of one indirection per cell.

Each way lives in exactly one cell (the cell of its bbox min corner), so a query needs no dedup pass and no visited-stamp array. The query widens its cell range by MAX_CELL_SPAN = 2 on the min side only: a registered way reaches at most that many cells right/down, so it can only touch the query if its own cell lies within that many cells before it.

Oversized ways go to an overflow list. A country-spanning coastline would otherwise be registered in thousands of cells (if you insert into every overlapping cell) or make MAX_CELL_SPAN useless (if you widen for the worst case). Ways whose bbox spans more than MAX_CELL_SPAN cells in either axis go into an always-scanned oversized vector instead. On real data that is a handful of entries.

The whole-data fast path. When the viewport contains the entire tier — the zoomed-all-the-way-out frame — the lattice buys nothing: every cell is visited anyway. That case sweeps the tier sequentially, already in insertion order, and skips both the cell walk and the sort.

Order is preserved exactly. The grid visits cells, not ways, so the hit indices are sorted before dereferencing. Paint order (and every golden that depends on it) is byte-identical to the brute-force scan — asserted, not assumed (§f4).

f2.2 The origin is cached at build

MapIndex::build already walks every way to partition it into LOD tiers. It now folds the bbox-min in the same pass and stores it; MapIndex::origin() returns it in O(1). draw_ways_gpu calls that instead of ways_origin. ways_origin itself is untouched (additive, L2) — it is still the right function for a caller that has a way iterator and no index.

f3 — the numbers

facett-geomap/benches/heavy_navigator.rs, group way_index (new). Host oden — AMD Ryzen Threadripper PRO 3975WX, 32 physical cores, SMT off, 499 GB RAM, NVIDIA RTX 4090. NORNIR_MACHINE=oden. This is a NEW host row; never merge it with the constellation's loki · 12 cores tables.

Single-threaded arms. Plain numbers, ns. The box was not quiet (several agents building; load average 42–69), so both runs were taken with the bench binary pinned to one core at real-time priority — chrt -f 50 taskset -c 30 — which insulates the measurement from the build storm. Before and after were taken the same way, minutes apart, so the comparison is like-for-like.

The dataset is a deterministic Sweden-shaped road network built through the real Way::from_lonlat (motorway / primary / secondary / residential in the proportions a road network has) plus four country-spanning coastline ways, so the oversized overflow path is exercised at every size.

The headline — the per-frame way cull

way_index/query_city_block — the street-level frame, the claim that cost tracks the screen and not the dataset:

Read it as a curve, which is the whole point: after the fix the cost goes 387 → 1435 ns while the dataset grows 100x. Before, it went 12753 → 11601000 ns — i.e. it tracked the dataset exactly, which is what the type promised it would not do.

The per-frame origin

way_index/origin — a constant of the dataset, formerly re-derived every frame:

Flat, because it is now a field read.

The rest

The zoomed-out arm improves 45x even though "everything is visible", because the whole-data fast path sweeps the tier sequentially instead of bbox-testing every way and pushing through a filter iterator.

build is 12% slower at 1M — the counting sort and the CSR fill are real work. That is the deliberate trade: it is paid once, at load, against a per-frame saving of 19 ms. (Most of the build number is the bench cloning 1M Ways, each of which owns three heap allocations; the index construction is the smaller half.)

What one frame now costs

A street-level frame at 1000000 ways, way layer only:

19.09 ms of CPU book-keeping per frame — on its own more than a 60 Hz budget — became 1.4 µs.

f4 — RED-when-broken proofs

facett-map/src/index.rs tests. The oracle for a spatial index is equivalence, not a timing (timings are the bench's job):

f4b — the LIVE demo: two more findings, from perf on the running process

The bench above measures the library. Rickard was looking at the app, so the app was profiled too — perf record -F 499 -g on the running release binary, OSM 2D tab.

f4b.1 The pane was never opted into the GPU line lane it ships

state_json said it outright and nobody had read it:

gpu_enabled = false   gpu_lines = false   visible_ways = 41702   fps = 4.24

OsmView carries the entire wgpu compute-cull + draw_indirect line path; main.rs installs the GpuMapRenderer; and osm_tabs::osm2d_view() never called .with_gpu(true). The demo's map tab did. The OSM 2D tab did not. So every one of Sigtuna's 41702 ways went through the egui CPU tessellator on one core, every frame, with a 4090 idle.

Measured on oden, release, OSM 2D, with the robot state channel on in both runs so the comparison is like-for-like (that channel re-serialises the whole app to disk every frame, so both figures are below what a human sees):

2.03x. For scale, the same binary in a debug build reads 1.89 fps — anyone judging the demo's speed from target/debug is measuring the compiler, not the renderer.

The fail-safe this exposed. Handing the line layer to the GPU means not drawing it on the CPU that frame, and draw_ways_gpu returned true as soon as it emitted the callback — whether or not any renderer existed to service it. A host that opts in without calling install_renderer would render a map with no line ways at all: worse than slow. The headless egui_kittest harness is exactly such a host, and it has a RenderState, so "is there a RenderState" is the wrong question. facett_map::gpu::install_renderer now latches a process flag, renderer_installed() exposes it, and the pane falls back to the CPU painter when it is not set. Unknown ⇒ CPU.

f4b.2 The demo rebuilt the WHOLE app's state_json every frame — to read one string

The profile of the running app, before the fix (--percent-limit 1, self time):

Graph centrality was being computed inside a paint frame. The cause is one line in facett-demo/src/lib.rs:

if self.deck.state_json()["active"] == "syschart" {

FacetDeck::state_json walks every facet and calls its state_json() and caps(). Those are not cheap getters: MapView::state_json derives its layer breakdown from the geometry, GeoMap::bbox walks every point, and the graph facets run schema(), edge_indices() and betweenness. All of it, ~27 facets, every frame — to compare one string, on every tab, whichever tab you are looking at.

FacetDeck::active_title() is an O(1) field read and already existed.

After the fix, every one of those symbols is gone from the top of the profile (the remaining hot symbols are the 3D pane's clip_tri_frustum / shade_mesh_tris — the attract-mode tab cycle walks onto OSM 3D — plus the 2D pane's own clip_poly_to_rect and stroke_and_fill_path). Directly attributable samples were ~20% of the frame, plus a large share of the ~20% allocator/memcmp traffic those BTreeMap<String, Value> builds generate.

This is the fifth appearance of the bug class in this repo, and the widest: it was not "one pane scales with its dataset", it was "every frame pays for every pane, including panes nobody is looking at".

f5 — what is still slow (honest list)

• No count budget on the way layer. The point layer decimates to MAX_DRAWN_POINTS via budget_stride; the way layer has only the zoom→LOD tier gate. A zoomed-out frame on a dense region can still hand egui hundreds of thousands of polylines to tessellate on one core. This is the next real win and is the same shape as the point-layer fix. (The zoom-LOD half of this is being worked in facett-geomap by another agent — commit b6c013e — so it is left alone here rather than collided with.)
• [CLOSED 2026-08-31 for MapFacet] The draw list was rebuilt and re-sorted every frame. MapFacet::features_for_cpu walked every enabled layer and re-sorted the whole Vec<DrawFeature> on the declared PaintKey on every pass, so a still screen paid exactly what a pan paid — the same "cost tracks the dataset, not the screen" class this file's f1 names, one level up. Memoised on (layer_epoch, view, gpu_layers, gpu_owns). Stated as work removed rather than as milliseconds — absolute frame times on this box are contention-dominated (the same binary and fixture measured 15.91 ms and 36.78 ms four minutes apart, load 39–262 on 32 cores) — over 501 identical asks of a 20 000-way facet: 1 layer walk instead of 501, 1 sort instead of 501, 20 000 way_paint_key computations instead of 10 020 000. Shape, key, red arms and the honest hit ratio: maptrait-design.md §f4. The legacy MapView/OsmView path this file measures is unchanged. What is now the dominant still-frame CPU cost on a labelled pane is place_map_labels, and §f4 says why it is not on the same key.
• CPU tessellation of the filled silhouettes. Every filled way is reprojected from lonlat in f64, Sutherland–Hodgman clipped and meshed on the CPU every frame, even when the GPU line lane is active. Bounded by the visible set now, which is the prerequisite — but it is still per-frame CPU work that could be uploaded once.
• The point layer culls twice. visible_count(vp) then visible_into(vp, stride, …) walk the same cells: the stride depends on the count, so the count has to come first. Both are viewport-bound, so this is a 2x on an already-small number, not a scaling bug.
• The graph overlay is not culled. OsmView's optional GeoGraph overlay projects every node and edge each frame and rejects off-screen ones after projecting. It is an annotation layer (hundreds of nodes), so it does not show up — but it is the same pattern and will bite if anyone points it at a real graph.
• way_index/build at 1M is 322 ms. One-off, at load, and dominated by Way cloning rather than the index. Fine today; worth revisiting if load time ever becomes the complaint.

f6 — "not smooth, kind of fast then slow" (2026-08-31, lane LANE)

Rickard, after using the korp client: "it feels like my first Turbo Pascal 1996 map, it's not smooth… it kind of fast then slow", and then precisely: "the lines must be PUT in the GPU and THEN not manipulated from egui."

Everything below is MEASURED on oden's RTX 4090 (Vulkan, DiscreteGpu) — the adapter is printed by every test in facett-map/tests/gpu_lane_share.rs, which refuses to report a lane number from a software rasteriser, because this box silently selects llvmpipe when the 4090 is saturated. Load on the box ran 6–223 on 32 cores during the session, so counts and bytes are quoted, not milliseconds.

f6.1 The "1 280 bytes" was not the lane's frame — it was one group's event

The case for "the lane owns nothing" was one korp line:

FIRST-PAINT lod=5 after 91 ms — … upload 25 us (1280 bytes) · gpu 5589 us

set beside "1 264 ways". Both halves of that reading are wrong.

• LaneClockStats::last_upload_bytes is the bytes of one upload EVENT, and the tile lane calls note_upload once per hand-over GROUP. MEASURED: a 640-way korp-shaped scene warms in 480 upload events / 744 960 bytes — ~1 552 bytes per event, the same order as the 1 280 that was read as a whole frame.
• The two numbers are not the same moment. 1280 bytes is oden-ui-fresh.log line 33, lod=5, 91 ms in. 1264 ways is line 451, a lod=15 street-level serve four hundred lines later.

LaneClockStats now also carries upload_bytes_total, which is the field that can answer a per-frame question, by difference across two reads.

f6.2 The lane is not declining. It takes every way.

MapFacet::gpu_lane_share counts WAYS on each side, off the very Arc<Vec<DrawFeature>> the frame paints from. Over a korp-shaped scene (1 200 ways, 150 producer-stamped tiles, 8 feature classes), at three real cameras:

RED arm in the same body: the adapter-less plan (CpuOnly::NoRenderer, what every host without a RenderState gets) puts 840 ways back on the painter. The guard moves.

What actually makes way_lane_plan decline is only two things, and neither is about geometry quality: NoRenderer (a process-global latch) and NoLineWays (no enabled layer answered Some to gpu_ways/gpu_fills — and WaysLayer is the ONLY implementor that overrides those defaults). RotatedCamera is unreachable since MapTransform gained the compass. gpu_fillable's lonlat.len() >= 3 clause cannot discriminate on the OSM path — from_lonlat_styled assigns a fill only when is_closed_ring, which needs ≥ 4 — so it is not the fill gate anyone was looking for; it is a live guard only for the Way::filled door, which checks nothing (synthetic fixtures; korp never calls it).

f6.3 A pan re-bakes nothing — and the origin is not the camera's

gpu_geometry_signature(gpu_layers, origin) folds origin, which reads like "a pan invalidates the whole bake". It does not: gpu::ways_origin is the data bbox-min over the way set, camera-independent by construction, and on korp's grouped path each group bakes against its OWN origin (TileGroupPlan::origin), so a new tile cannot move an existing group's key. MEASURED over 24 frames of real pan_by_px:

f6.4 The payload was put in the GPU. The GROUPING around it was rebuilt every frame.

This is Rickard's sentence, exactly: the bytes were uploaded once and manipulated from egui afterwards anyway. add_gpu_tiled_callback walked every way of every taken layer twice into a fresh HashMap, collected the keys and sorted them, on every frame, only to hand over geometry: None for nearly all of them. Nothing in that grouping depends on the camera: the group id is (draw_band, tile_key), both read off the way, and the bake origin is that group's own ways. Only the per-group MapTransform and its rebased viewport are camera-dependent, and those are O(groups).

The grouping is now TileGroupPlan, memoised per apply on the same (epoch, layers, generations) key as the signature memo. MEASURED, counted at two frame counts so a per-frame walk cannot pass:

Two, not one, and the second is honest: the device marks a key known only once the payload has landed, so the first frame that hits the plan memo can still owe bytes for some group and has to gather its ways. It is a constant of the APPLY, not of the frame count — which is why the guard compares two frame counts instead of asserting a single number.

f6.5 The THIRD walk — ways_origin, in the caller, for a value the grouped path throws away

f0.3 of this very file named ways_origin as one of two full-dataset scans per frame and fixed it in MapIndex. The GPU lane's own caller kept doing it: add_gpu_ways_callback folded ways_origin over every way of every taken layer before it asked gpu_lane_needs_grouping — and the grouped path immediately discards that origin. korp is always the grouped path (every served way carries tile_key = w.tile from classify_rows), so on the machine being complained about that fold ran over the whole way set, every frame, and its result was dropped on the next line.

gpu_lane_needs_grouping short-circuits on the first stamped way, so asking it first is O(1) there. The empty case is unchanged — an empty lane set makes it false and still falls through to the origin guard. MEASURED (lane_origin_walk_count):

f6.6 What is left, and it is NOT the lane

The lane takes 100 % of the ways and a pan uploads nothing. What a korp frame still pays, panning or still, is the group census:

census — 900 groups over 150 tiles (6.00/tile, 8 classes) for 1200 ways
       ⇒ ≥5400 queue.write_buffer calls PER FRAME

GpuMapRenderer::run_cull_tiles_clocked writes one 16-byte indirect reset per chunk and one viewport per group, every frame, and MapPaintCallback::prepare writes five uniform buffers per group. Rickard's own session log covers 4–156 tiles (median 30), so it sits in the same range. And the lane's in-GPU pass clock in that log — 22 samples — reads median 48 524 µs, max 182 627 µs. Forty-eight milliseconds of cull on a 4090. That is the next lever, and it is a per-group traffic problem, not a "the lines are on the CPU" problem.

Two other costs in the same log, both outside facett-map:

• korp rebuilds the whole 2D facet on the UI thread. 54 REBUILD 2D events in one session, cause=geometry-generation for 53 of them, median 143 116 ways fed (max 303 240), median 50.8 ms, max 686.4 ms, 4 629 ms in total. That is the stutter's shape: a smooth stretch, then a level lands and the thread blocks.
• The 3D view had no GPU lane at all in that binary. Every korp::map3d LANE line in the log reads gpu_lane_selected false … renderer_installed n/a (map3d-gpu not compiled in) — 5 of 5 — with extrude up to 766 ms for 247 741 ways on the CPU. Any 3D frame-time quoted from that session is the CPU painter, not a lane.