facett-graphnav/tests/render_index_scales.rs
//! **The navigator's per-frame lookups must not be linear scans of the node list.**
//!
//! `GraphNav::render` resolved an edge's endpoints with `PropGraph::index_of`, which is
//! `nodes.iter().position(|n| n.id == id)` — a linear scan with a string compare — and
//! it did it TWICE PER EDGE, twice per frame (the `edge_pairs` legibility input and
//! the edge draw loop). It also built `label_priority` from
//! `PropGraph::neighbours(id)`, a full pass over the edge list, ONCE PER NODE. All
//! three are `O(V · E)` per frame.
//!
//! MEASURED on oden, 2026-09-03, thin `korp-ui` on Xvfb :131 against the live
//! FalkorDB: the 🏬 Warehouse ▸ 🕸 explorer opened `sweden_roads_1e56d149`
//! (89 130 nodes / 91 998 edges), the operator pinned `navigator_2d`, and the main
//! thread went to 137 % CPU and stopped writing `$KORP_STATE` for the rest of the run.
//! `gdb -p` on the live process, thread 1:
//!
//! ```text
//! #0 __memcmp_avx2_movbe
//! #1 <Map<Iter<facett_graphnav::model::Edge>, GraphNav::render::{closure#1}::{closure#14}> …>::fold
//! #3 <GraphNav::render::{closure#1} as FnOnce<(&mut egui::ui::Ui,)>>::call_once
//! #6 <facett_graphnav::GraphNav>::render
//! ```
//!
//! That is 89 130 × 91 998 × 2 ≈ 1.6·10^10 string compares for ONE frame.
//!
//! These tests measure the primitives the render calls, not the render itself (an egui
//! frame needs a context; the cost is in the lookups and is measurable directly). The
//! linear and indexed lanes are three orders of magnitude apart, so the thresholds sit
//! in a gap no machine load can close.
use facett_graphnav::model::{Edge, Node, PropGraph};
fn chain(n: usize) -> PropGraph {
let mut g = PropGraph::new();
for i in 0..n {
g.add_node(Node::new(format!("n{i:06}"), "T"));
}
for i in 1..n {
g.add_edge(Edge::new(format!("n{:06}", i - 1), format!("n{i:06}"), "R"));
}
g
}
#[test]
fn resolving_every_edges_endpoints_is_one_indexed_pass() {
let g = chain(20_000);
let t0 = std::time::Instant::now();
let idx = g.index_map();
let pairs: Vec<(usize, usize)> = g
.edges
.iter()
.filter_map(|e| Some((*idx.get(e.from.as_str())?, *idx.get(e.to.as_str())?)))
.collect();
let ms = t0.elapsed().as_secs_f64() * 1e3;
assert_eq!(pairs.len(), 19_999);
assert_eq!(pairs[0], (0, 1), "the index really resolves, it is not an empty map");
assert_eq!(pairs[19_998], (19_998, 19_999));
// Indexed: single-digit ms. Per-edge `index_of`: 20 000 × 20 000 = 4·10^8 compares.
assert!(ms < 300.0, "{ms:.1} ms for 20 000 edges — that is a scan per edge, not an index");
// …and the SAME work through the scan it replaces, so the win is measured here and
// not merely asserted. An `index_map` that is secretly linear fails this.
//
// HOW it is measured matters, and the first version got it wrong. It compared the
// two lanes at ONE size (2 000 nodes) and demanded the index be 20x faster. That is
// a constant-factor claim, not a complexity claim: on a chain the scan finds node
// `i` after `i` seven-byte memcmps, the index pays a SipHash per lookup, and in an
// unoptimised test build on a fast box the two landed 15.3x apart (18.33 ms ->
// 1.20 ms, loki, 2026-09-18). The index was fine; the test went red on `main`
// because a CPU was quick at memcmp.
//
// What separates "indexed" from "secretly a scan" on EVERY machine is how the time
// GROWS. Resolve the same chain at n and at 8n: one pass per edge grows ~8x, a
// scan per edge grows ~64x. The bars below sit between those with room on both
// sides, and the constant factor — the thing that differs between machines —
// cancels out of a ratio of the lane against itself.
let scan = |g: &PropGraph| -> Vec<(usize, usize)> {
g.edges.iter().filter_map(|e| Some((g.index_of(&e.from)?, g.index_of(&e.to)?))).collect()
};
let indexed = |g: &PropGraph| -> Vec<(usize, usize)> {
let ix = g.index_map();
g.edges.iter().filter_map(|e| Some((*ix.get(e.from.as_str())?, *ix.get(e.to.as_str())?))).collect()
};
// Best-of-N: the MINIMUM is the run least disturbed by the scheduler, which is the
// one that reflects the algorithm. A mean would let one preempted run move a ratio.
fn best_ms<T>(runs: usize, mut f: impl FnMut() -> T) -> f64 {
(0..runs)
.map(|_| {
let t0 = std::time::Instant::now();
std::hint::black_box(f());
t0.elapsed().as_secs_f64() * 1e3
})
.fold(f64::INFINITY, f64::min)
}
let (small, large) = (chain(2_000), chain(16_000));
assert_eq!(scan(&small), indexed(&small), "the two lanes answer identically");
let ix_growth = best_ms(7, || indexed(&large)) / best_ms(7, || indexed(&small)).max(1e-6);
// 32, not the geometric midpoint (~23): measured on loki with a release build of
// another repo saturating every core, this read 8.1x, 8.2x and once 15.7x. 32 is
// still 2x under quadratic and 4x over linear, so load cannot flip it either way.
assert!(
ix_growth < 32.0,
"the indexed resolve grew {ix_growth:.1}x for 8x the graph — one pass per edge grows ~8x, \
a scan per edge ~64x. At 89 130 nodes that is the difference between a frame and a hang"
);
// …and the control: the scan lane really IS the quadratic one. Without this the
// bar above could pass because BOTH lanes are fast, which would prove nothing about
// the lane the render used to call. 2 000 -> 8 000 keeps the slow lane affordable.
let mid = chain(8_000);
let scan_growth = best_ms(3, || scan(&mid)) / best_ms(3, || scan(&small)).max(1e-6);
assert!(
scan_growth > 8.0,
"the per-edge `index_of` scan grew only {scan_growth:.1}x for 4x the graph — linear would be \
4x, quadratic 16x. If this is no longer quadratic, `index_of` changed and this test's \
premise needs re-reading"
);
println!("indexed resolve, 2 000 -> 16 000 nodes: {ix_growth:.1}x (linear = 8x, quadratic = 64x)");
println!("scan resolve, 2 000 -> 8 000 nodes: {scan_growth:.1}x (linear = 4x, quadratic = 16x)");
println!("20 000-node edge resolve, indexed: {ms:.2} ms");
}
#[test]
fn every_nodes_degree_is_one_indexed_pass() {
let g = chain(20_000);
let t0 = std::time::Instant::now();
let adj = g.adjacency();
let degrees: Vec<usize> = g.nodes.iter().map(|n| adj.get(n.id.as_str()).map_or(0, Vec::len)).collect();
let ms = t0.elapsed().as_secs_f64() * 1e3;
assert_eq!(degrees[0], 1, "an end of the chain has one neighbour");
assert_eq!(degrees[10_000], 2, "an interior node has two");
assert_eq!(degrees.iter().sum::<usize>(), 2 * 19_999, "every edge counted from both ends");
assert!(ms < 300.0, "{ms:.1} ms for 20 000 nodes — that is an edge scan per node, not an index");
}
/// `GraphNav::render` calls `PropGraph::schema()` every frame, and `schema` resolved
/// both endpoints of every edge with `node(&id)` — a linear scan. Third site of the
/// same defect, and the one the client was sitting in when it stopped repainting on
/// the 89 130-node road slice.
#[test]
fn the_schema_of_a_large_graph_is_one_indexed_pass() {
let g = chain(20_000);
let t0 = std::time::Instant::now();
let sc = g.schema();
let ms = t0.elapsed().as_secs_f64() * 1e3;
assert_eq!(sc.node_labels.get("T").copied(), Some(20_000));
assert_eq!(sc.edge_types.get("R").copied(), Some(19_999));
assert_eq!(sc.triples.len(), 1, "one (T)-[R]->(T) triple");
assert_eq!(sc.triples[0].count, 19_999, "and every edge was resolved, not skipped");
assert!(ms < 300.0, "schema() took {ms:.1} ms on 20 000 nodes — that is a scan per endpoint");
}
#[test]
fn the_index_agrees_with_the_scan_it_replaces() {
// RED-when-broken for the INDEX itself: an index that is merely fast but wrong
// would pass the two budgets above. Every id must resolve to the same answer the
// linear lookups give, and an absent id must still be absent.
let g = chain(500);
let idx = g.index_map();
let adj = g.adjacency();
for (i, n) in g.nodes.iter().enumerate() {
assert_eq!(idx.get(n.id.as_str()).copied(), g.index_of(&n.id), "index_of disagrees at {i}");
let mut a: Vec<String> = adj.get(n.id.as_str()).cloned().unwrap_or_default().into_iter().map(str::to_string).collect();
let mut b = g.neighbours(&n.id);
a.sort();
b.sort();
assert_eq!(a, b, "neighbours disagree at {}", n.id);
}
assert!(!idx.contains_key("nope"));
assert!(!adj.contains_key("nope"));
// Duplicate edges must not become duplicate neighbours — `neighbours` dedupes.
let mut d = PropGraph::new();
d.add_node(Node::new("a", "T"));
d.add_node(Node::new("b", "T"));
d.add_edge(Edge::new("a", "b", "R"));
d.add_edge(Edge::new("a", "b", "R"));
assert_eq!(d.neighbours("a").len(), 1);
assert_eq!(d.adjacency().get("a").map_or(0, Vec::len), 1, "the index dedupes exactly as the scan does");
}