nordisk/facett

Barnes–Hut force layout — design

Class: design · Function axis: f0 the scalable force-layout subsystem · f1 facett_core::barnes_hut (the shared kernel) · f2 the per-crate consumers (facett-core::positions, facett-graph, facett-graphnav, facett-graph3d) · f3 the freeze cache + absorb contract. Strict: this file states only the shape we run. The alternatives we rejected live at the end under Rejected.

f0 — the problem this kills

The graph viewer (korp) hung at ~30 000 nodes. The cause was not the draw (wgpu instances the node/edge cloud fine) — it was the force layout. Every facett force-directed layout was a Fruchterman–Reingold sim whose repulsion term is all-pairs, O(n²) per iteration, and in the 2-D viewers it was re-run every frame in the render path. O(n²) × 120 iterations × every frame = the hang.

Two independent fixes, both additive (small graphs keep the exact old algorithm):

1. Barnes–Hut drops the repulsion from O(n²) → O(n log n).
2. Converge-once-then-freeze stops the layout re-running every frame.

f1 — the shared kernel (facett_core::barnes_hut)

One kernel, consumed by every copy (L5 reuse — the FR loop was twinned in ~5 places). It is dimension-generic over const D: D = 2 is the quadtree (plane), D = 3 the octree (cube), D = 1 a segment tree (the callgraph z-only pass).

• NBodyTree::<D>::build(pos) — a spatial tree over the body positions. Bodies insert into a 2^D-way subdivision; each cell carries a center of mass + body count. Serial, O(n log n). A depth cap (48) + a min-cell-size floor make coincident points safe (they merge into one center-of-mass leaf).
• NBodyTree::force(p, self_idx, k, theta) — the net repulsion on one body. A stack walk: a cell whose width subtends an angle below theta (width² < θ²·d²) is used as a single point mass at its center of mass; otherwise descend. theta = 0 ⇒ every leaf is a single body ⇒ exact all-pairs sum (the parity we test).
• repulsion_forces::<D>(pos, k, theta) — build the tree, then compute the per-node force in parallel across every core via the znippy gatling fork-join engine (gatling_for_each, one worker per core; rayon is FORBIDDEN). Each node is computed by one worker traversing the shared immutable tree in a fixed order, so the float sums are byte-deterministic regardless of worker count — the property the determinism goldens rely on.
• relax_new::<D>(pos, edges, new_lo, k, theta, iters, step) — the absorb relaxation: a few local FR iterations that move ONLY the nodes at index ≥ new_lo (existing nodes frozen), Barnes–Hut repulsion + spring attraction on incident edges.
• structure_sig(layout_key, n, edges) — the cheap u64 a force layout is a pure function of; backs the freeze.
• BH_THRESHOLD = 2000, BH_THETA = 0.7.

The FR magnitude convention the kernel reproduces: repulsion on i is Σ_j (p_i − p_j) · k² / |p_i − p_j|² (direction p_i − p_j, magnitude k²/dist), the same term the exact loops computed.

f2 — the consumers (threshold-gated, additive)

Each copy keeps its own seed / cooling schedule / edge attraction / normalisation and swaps only the repulsion double-loop for repulsion_forces at/above BH_THRESHOLD. Below the threshold the exact O(n²) loop runs unchanged, so every small-graph determinism/golden test is byte-for-byte identical.

callgraph_layouts::force3d is a 1-D N-body: the pairwise push is k²·0.0016·d/|d|², i.e. effective length k·0.04, reproduced by the D = 1 tree.

MDS is a separate problem — O(n²) MEMORY, not compute

callgraph_layouts::mds (classical MDS) builds a dense n×n distance + Gram matrix (~3.6 GB of f32 at 30 000 → OOM). Barnes–Hut does not apply. Above MDS_MAX = 4000 it falls back to mds_landmark: keep the force2d x,y, set z from BFS hop-distance to the highest-degree landmark — O(n + e) memory, a real 3-D relief, no dense matrix. Below the guard the exact classical MDS runs (goldens unchanged).

f3 — the freeze + absorb contract (for korp and other consumers)

A force layout is a pure function of (layout, node count, edges), so it is computed once and frozen:

• facett_core::ForceCache — a host embeds it and calls cache.positions(layout, scene, rect) in the render path; it recomputes only when the structural signature or the paint rect changes. is_settled(..) is the frozen signal. facett-graph::GraphView embeds one (interior-mutable) so its every-frame show no longer re-runs the layout.
• facett-graphnav::GraphNav::positions() caches internally on the same signature; layout_settled() reports the frozen state. Graph3D freezes implicitly — it lays out in new/SetLayout and tick only advances the animation clock.

Absorb — the incremental grow API korp calls (instead of rebuilding via ::new):

• GraphNav::absorb(nodes: Vec<Node>, edges: Vec<Edge>)
• Graph3D::absorb(new_nodes: Vec<(String, Color32)>, new_edges: Vec<(usize, usize)>)

Contract: existing node positions are kept; each new node is seeded at its already-placed neighbours' centroid (fallback: a small deterministic ring around the cloud centroid); only the new nodes are relaxed (relax_new); the result is written straight into the freeze cache. For the deterministic layouts (grid/circular/…, sphere/helix) there is nothing incremental to preserve, so the cheap placement is just recomputed. This is what lets sync_graph_nav stream nodes at frame rate.

Draw is already instanced

facett-graph3d with feature wgpu emits graph_gpu::{NodeInstance, EdgeInstance} arrays (Graph3D::gpu_scene) — the node/edge cloud is GPU-instanced. The draw was never the 30k bottleneck; no renderer rewrite was needed.

Numbers (Loki, 12 cores, release)

30k/10k ≈ 2.8× (2-D) / 3.3× (3-D). O(n²) would be ≈ 9×; O(n log n) ≈ 3.4×. Confirmed sub-quadratic. (At n = 1k the fixed per-iteration thread-spawn overhead dominates — a known, harmless small-n tax.)

Rejected

• Reuse facett-graphview::gpu_layout — it is a different force model (velocity-integrated, gravity, per-node weights) and still O(n²) on the CPU fallback (its own docs list Barnes–Hut as unbuilt roadmap). Routing the existing layouts through it would change their output (regress goldens) and not fix the CPU path. Kept as the separate GPU engine it is.
• A GPU Barnes–Hut — real, but needs a Morton/grid tree in WGSL; the CPU kernel here lands the fix everywhere (native + wasm) first. Documented as future work.