nordisk/facett

The graph family — the instanced GPU cloud, and legibility at scale

nornir:class=design

Function axis: f0 the two walls · f1 one renderer, shared down into facett-core · f2 the fail-dangerous shape and why it is now structurally impossible · f3 legibility (facett_core::legibility) · f4 what each pane got · f5 pin labels — the other half of the map lesson · f6 the numbers · f7 RED-when-broken.

Only the chosen design is named here. Strict: every claim points at a real file:line or a bench arm.

f0 — the two walls, and why one cure is not the other

graph3d-rotate-perf-design.md measured the frame of a 3-D node cloud and found the wall was not where anyone had assumed. At 30 000 nodes the per-node projection costs 0.020 ms/frame; egui's CPU tessellation of the resulting 2 470 000 triangles costs 33.751 ms/frame, single-threaded. Fanning the projection across 32 cores is a pessimisation — it adds ~1 ms of fork-join to a 0.02 ms job. The cure is to stop tessellating: upload the cloud as GPU instances and issue two draw calls.

That is a speed cure, and it is the whole of what graph3d got. It does nothing whatsoever for the second wall:

A GPU that draws 100 000 overlapping labels at 240 fps has drawn an unreadable pane very quickly.

At 100 000 nodes on one screen there is no arrangement of pixels in which every label is legible; there is no arrangement in which 900 000 edges show structure. The pane is a grey rectangle with names smeared over it, and it renders that way at any frame rate. "Make facett graph viewer as good and better for viewing data" is a request about the second wall, and it needs different code: not faster drawing, but deciding what is worth drawing.

So this round ships two independent, independently-measured things:

f1 — ONE renderer, moved down (L5)

The instanced cloud was born as facett_graph3d::graph_gpu. Nothing about it is 3-D: every input it takes is already screen-space pixels — a node is a centre + radius, an edge is two endpoints + a half-width. The 2-D family hits the identical wall for the identical reason.

So the renderer moved to facett-core/src/render/gpu/graphcloud.rs (feature wgpu) and facett_graph3d::graph_gpu is now a pub use re-export (facett-graph3d/src/lib.rs:64). Everything under facett_graph3d::graph_gpu::… still resolves exactly as before; there is still exactly one GraphGpu, one CloudPaintCallback, one install_cloud_renderer, one process-global install flag.

Two shared helpers were added there rather than re-derived per crate:

• cloud::draw_cloud(ui, rect, use_gpu, build) — the whole opt-in + install-check + physical-px protocol in one function. Graph3D::draw_gpu_cloud now calls it too, so the 3-D pane and the 2-D panes cannot drift.
• CloudBuilder — the shared lowering (sRGB→linear radiance curve, emissive scale, edge gain, edges-under-nodes ordering). Byte-identical curve to the one Graph3D::gpu_scene_at has always used, so the 2-D and 3-D clouds look like the same renderer because they are.

f2 — the fail-dangerous shape, made structurally impossible

The graph3d defect worth restating, because this round hands the same opt-in to four more panes:

Graph3D was registered. Its instanced cloud was proven by tests and installed by no host, and with_gpu(true) skips the CPU painter — so opting in rendered a blank pane. That was the entire "the 3D graphs are missing" symptom, and nothing was red: the pixel oracle said a frame was produced, the state oracle said the model had nodes, and neither said "nothing drew because nobody installed the renderer".

The guarantee is therefore not "remember to check the flag". A pane may skip its CPU painter only on a true returned by cloud::draw_cloud, and that function returns false unless cloud_renderer_installed() is true in this process. A pane physically cannot reach the skip without going through it. Without the wgpu/gpu-cloud feature the whole lane compiles to false.

Pinned by a GPU-less test in every pane, on a box where no renderer is installed — the exact state that used to render blank:

• facett-graphpan/tests/gpu_fallback.rs::opting_into_gpu_without_a_renderer_falls_back_vertex_for_vertex
• facett-graphview/tests/legibility.rs::gpu_optin_without_a_renderer_falls_back_vertex_for_vertex
• facett-graphnav/tests/legibility.rs::gpu_optin_without_a_renderer_falls_back_vertex_for_vertex

Each compares egui's own tessellated vertex count between with_gpu(false) and with_gpu(true) and demands equality — "vertex for vertex" is literal. Each also asserts against an empty pane, so the equality cannot be two blanks agreeing.

f3 — facett_core::legibility: three primitives, all reporting their own cost

facett-core/src/legibility.rs. Pure, deterministic, no egui painting, no GPU.

ScreenGrid — a screen-space bin lattice for hover/pick. Sized from the data's own bounding box so occupancy stays near 8/cell at any extent. (That sizing rule is the PointGrid lesson: facett-geomap's lattice spanned the whole [0,1] Mercator square, so a Swedish dataset landed in ~90 live cells at ~11 000 points each and a city-block query still swept them.) nearest() returns NearestHit::candidates — how many points were actually distance-tested.

place_labels — greedy screen-space collision avoidance. Priority order (pinned → priority → input index, a total order, so it is deterministic under HashMap-free rules), a 5-position ladder per label (Mapbox variable placement), bin-local overlap tests. LabelPlacement reports placed / suppressed / considered / collision_tests.

Why drop rather than merge: the map's pins cluster — a pile of markers becomes one badge carrying a count, and no information is lost. Text cannot do that. Two overlapping names are strictly less readable than one name, so the only honest move is to rank and drop, and the ranking is the design: pinned (selection / hover / path / search hit) never drops.

thin_edges — an ink budget per screen cell, per quantised direction. Each on-screen segment is walked across the lattice and charged to every cell it crosses; an edge draws only if every cell on its path still has quota for its direction.

Two choices whose obvious alternatives are worse:

• Charge the whole path, not the midpoint. Midpoint binning is cheap and wrong: a long edge deposits ink over hundreds of cells while being charged to one, so a hairball of long edges passes every counter and renders exactly as black. This was caught by the pixel oracle (edge_ink_profile), which is why the function is written to satisfy the pixels rather than the bookkeeping.
• Quota per direction. A pile of near-parallel filaments is redundant; an edge crossing them at another angle is the structure you are trying to see.

And why not a uniform 1-in-k sample: it thins the sparse regions exactly as hard as the dense ones, destroying the readable parts of the graph to fix the unreadable parts. A budget leaves a bin under quota completely untouched.

plan_frame — the single entry point a pane calls: index-aligned slices in (FrameInput), a plan out (FramePlan = which edges, where the labels go, plus a FrameReport). Every pane lowers into this vocabulary, so two panes cannot end up with two different definitions of "readable".

The honesty fields. Every structure reports the work it actually did as DATA (candidates, considered, collision_tests, peak_density_before/peak_density). The PointGrid claim shipped as prose and was false for months because prose cannot go red. A test asserts on those numbers instead.

f4 — what each pane got

Why the navigator defaults legibility ON and the GPU OFF. They are not the same kind of switch. The GPU lane changes how pixels are produced and needs a host to install a renderer, so it must be opted into and default off to keep every golden byte-identical. Label collision and the ink budget change what is worth drawing, cost nothing when nothing collides (a small graph places every label and thins no edge — identical output), and are the entire reason the navigator exists. Defaulting them off would ship the unreadable pane and hide the cure behind a flag nobody sets.

The navigator's hover was the sharpest find. render resolved the hovered node by iterating every node in the graph, projecting it and taking a distance — on every mouse move, including nodes far off-screen — while the paint loop immediately below it was already viewport-culled. The frame's paint half scaled with the screen and its pointer half scaled with the dataset. That is the same shape as the PointGrid bug, in a different repo, three files later.

Everything is published through state_json ("legibility"), so a robot asserts on numbers rather than on a screenshot.

f5 — pin labels: the other half of the MapLibre lesson

Pins already clustered (osm-2d-navigator-design.md): co-located markers collapse into one count badge and split apart on zoom-in. Their labels did not. At the zoom where the marker cure has finished its job and every pin is its own single, all the names appear at once, on top of each other. The pixels still say "there are pins here"; they no longer say which.

OsmView::place_pin_labels (facett-geomap/src/osm2d.rs) runs the singles' labels through the same facett_core::legibility::place_labels the graph panes use. Selected pin is pinned; shorter names win (a short name fits where a long one does not, so dropping the long one costs the fewest labels). Group badges never compete — their count lives inside their own disc.

One thing fell out of doing it properly: the road-name pass used to reserve a fixed 90 × 26 px box per pin so street names would dodge the markers. It now reserves the actual marker discs and the actual boxes the pin labels won — the old guess was both too big for a short name and, once labels could be displaced, in the wrong place.

state_json publishes pin_labels + pin_labels_suppressed.

f6 — the numbers

facett-core/benches/heavy_legibility.rs (criterion, cargo bench -p facett-core --bench heavy_legibility). Host oden — AMD Ryzen Threadripper PRO 3975WX, 32 physical cores, SMT off, 499 GB RAM. 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. Taken on a quiet box (load average 1.6–7.2, no builders).

The pointer cost — the headline

Read it: the indexed probe goes 360 → 1156 ns while the dataset grows 100x; the scan goes 26755 → 2580300 ns, i.e. it tracks the dataset exactly. That is the claim, as a curve. 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.

The rest

place_offscreen_heavy is the "cost tracks the screen" arm: 100 000 candidates of which 500 are on screen costs 1 185 000 ns against 26 101 000 ns for 100 000 on-screen ones — 22x less for the same input size, because off-viewport candidates are rejected before any collision work.

Three findings the bench itself produced

1. A bench arm was measuring a best case no caller ever gets. edges/thin originally passed an empty weight slice. Every sort key then compared equal, the input was already index-ordered, and the merge sort detected one long run and ran in O(n) — so the arm read 5.1 ms at 100 000 while a real caller with real weights paid 47 ms at 120 000. The arm now supplies weights, and the sort materialises its keys into a (u8, u32, u32) triple sorted by sort_unstable (see monotonic_key), which removes both the four bounds-checked slice reads per comparison and the trap.
2. The ink budget walked every segment three times — once for the before-density, once to spend the budget, once for the after-density — and the DDA walk is the cost of the function (it is proportional to the ink, not the edge count). Folded into one pass: −37% on edges/thin.
3. The walk's per-step constant mattered more than its step count. The obvious t = s/steps + lerp form costs a divide and two multiply-adds per step; 120 000 viewport-spanning segments cross ~55 cells each, i.e. ~6 600 000 steps per frame. Incremental stepping (one add per axis) took frame/plan_30k_nodes_120k_edges from 48823000 → 31982000 ns (−34%) and edges/thin/100000 from 8628700 → 7325100.

A fourth, recorded because the first measurement of every one of these arms was contaminated: a concurrent agent was building in the same checkout and the load average reached 381 on 32 cores, which read frame/plan_edges_only_120k at 812 ms against its true 30 ms — a 27x error. The numbers above were re-taken at load 1.6–7.2. The constellation keeps having to retract contaminated numbers; the cheap defence is to print uptime on both sides of the run.

What is still slow, stated plainly

A 30 000-node / 120 000-edge frame plan is 31.98 ms and does not fit in a 16.7 ms 60 fps budget. The label half is 3.63 ms; the edge walk is the other 28.5 ms. It is still the right trade — the alternative is tessellating 120 000 edges on one core, which graph3d-rotate-perf-design.md measures an order of magnitude above that — but "60 fps at 30k with edges thinned" is not claimed. Open work, in order of expected value: cull edges to the viewport before the walk rather than testing inside it; coarsen the ink lattice (the walk is proportional to ink / cell, so cell 32 buys ~25%); and consider charging only the segment's endpoints-plus-samples rather than every cell, with the pixel oracle as the arbiter of whether that still bounds the ink.

f7 — RED-when-broken

Every claim above has an assertion that fails if it is reverted, and where the claim is about pixels the oracle rasterizes the result rather than reading the algorithm's own counters.

The label-placement bug the pixel oracle caught during development, recorded because it is the class this constellation keeps re-finding: the occupancy lattice skipped out-of-range bins instead of clamping into them, so two labels overlapping only in the region beyond the lattice consulted no shared bin, collided, and both drew. Every counter in LabelPlacement looked correct. max_label_overlap reported 2.