facett-graphview/examples/scale_probe.rs
//! **scale_probe** — how many nodes does the CPU path actually hold?
//!
//! `facett-graphview` claims to be a scalable graph engine. This example puts a
//! number on that claim instead of a word. It builds a synthetic [`GraphModel`] at
//! several sizes and times each stage a host would run per frame (or once per
//! layout), printing a table. Nothing here is a benchmark harness — it is a single
//! deterministic run, wall-clock, so the numbers are indicative, not statistical.
//!
//! ```text
//! cargo run --release -p facett-graphview --example scale_probe
//! cargo run --release -p facett-graphview --example scale_probe -- 1000 10000 100000
//! ```
//!
//! Stages, and why each is here:
//!
//! * `build` — constructing the model. Two `String`s per node (id + label).
//! * `fit` — `Camera::fit` / `world_bounds`, one pass over nodes.
//! * `cpu::render` — the reference vello_cpu rasterizer. **No viewport culling**:
//! it rasterizes every node and every edge whether or not it is
//! on screen.
//! * `clipped` — `clip::render_graph_clipped`, the L0 lane that *does* cull to
//! the widget rect. It still projects every node and builds two
//! `HashMap`s sized by the node count first, so the per-frame
//! cost tracks the model, not the viewport.
//! * `plan_view` — the opt-in legibility pass (label collision + edge ink budget).
//! * `pick x1000` — `clip::pick`, the crate's re-exported picker: a linear scan
//! over all nodes, per probe.
//! * `PickIndex` — the grid-indexed twin: one `ensure` (rebuild) + 1000 probes.
//! * `csr` — `GraphCsr::from_edges`, the layout input.
//! * `step_cpu x1` — ONE force-layout iteration. This is the all-pairs O(n²)
//! repulsion loop at `gpu_layout.rs::step_cpu`; a real layout is
//! hundreds of these. Skipped above `--max-layout` (default
//! 30 000) because a single step at 100 000 nodes takes ~25 s.
//! * `gpu x50` — 50 iterations of the same force model through the wgpu compute
//! kernel, on an already-created device (`force_layout_gpu_on`, so
//! the one-time adapter init is not charged per layout). Only built
//! with `--features gpu`, and only run when an adapter exists.
use std::time::Instant;
use facett_graphview::{
clip::{self, WidgetRect},
cpu, gpu_layout,
legible::{self, PickIndex, ViewOpts},
world::{self, Lod, WorldGraph},
Camera, Color, Decorations, GraphEdge, GraphModel, GraphNode, Pos,
};
const W: u32 = 1920;
const H: u32 = 1080;
/// A deterministic grid graph: `n` nodes on a near-square lattice, each linked to its
/// right and lower neighbour (~2n edges), which is a realistic sparse degree for a
/// crate/symbol dependency graph.
fn build(n: usize) -> GraphModel {
let cols = (n as f64).sqrt().ceil() as usize;
let mut nodes = Vec::with_capacity(n);
for i in 0..n {
let (c, r) = (i % cols, i / cols);
nodes.push(GraphNode {
id: format!("n{i}"),
label: format!("node-{i}"),
fill: Color::rgb((i % 251) as u8, 120, 200),
stroke: Color::WHITE,
pos: Pos::new(c as f32 * 200.0, r as f32 * 50.0),
});
}
let mut edges = Vec::with_capacity(n * 2);
for i in 0..n {
if i % cols + 1 < cols && i + 1 < n {
edges.push(edge(i, i + 1));
}
if i + cols < n {
edges.push(edge(i, i + cols));
}
}
GraphModel { nodes, edges }
}
fn edge(a: usize, b: usize) -> GraphEdge {
GraphEdge {
from: format!("n{a}"),
to: format!("n{b}"),
color: Color::rgb(200, 200, 220),
dashed: false,
label: None,
}
}
fn ms(t: Instant) -> f64 {
t.elapsed().as_secs_f64() * 1000.0
}
fn main() {
let args: Vec<String> = std::env::args().skip(1).collect();
let mut sizes: Vec<usize> = Vec::new();
let mut max_layout = 30_000usize;
let mut world_mode = false;
let mut it = args.iter();
while let Some(a) = it.next() {
if a == "--max-layout" {
max_layout = it.next().and_then(|v| v.parse().ok()).unwrap_or(max_layout);
} else if a == "--world" {
// WORLD GRAPH lane probe: skip the O(n²) base table entirely and measure the
// scale-aware world layout (Barnes–Hut O(n log n) + O(n) hierarchical
// placement) at large N. `cargo run --release … -- --world 100000 1000000 10000000`.
world_mode = true;
} else if let Ok(v) = a.parse() {
sizes.push(v);
}
}
if world_mode {
if sizes.is_empty() {
sizes = vec![100_000, 1_000_000, 10_000_000];
}
world_probe(&sizes);
return;
}
if sizes.is_empty() {
sizes = vec![1_000, 10_000, 100_000];
}
println!(
"{:>8} {:>8} {:>9} {:>9} {:>9} {:>9} {:>9} {:>9} {:>9} {:>9} {:>12}",
"nodes",
"edges",
"build",
"fit",
"cpu",
"clipped",
"plan",
"pick1k",
"idx+1k",
"csr",
"step_cpu x1"
);
println!("{:->8} {:->8} {:->9} {:->9} {:->9} {:->9} {:->9} {:->9} {:->9} {:->9} {:->12}", "", "", "", "", "", "", "", "", "", "", "");
// One device for the whole sweep — the realistic host case (egui-wgpu/vello
// already holds one), so per-size numbers are layout cost, not device init.
#[cfg(feature = "gpu")]
let gpu_dev = gpu_layout::compute_device();
#[cfg(feature = "gpu")]
if gpu_dev.is_none() {
eprintln!(" [gpu] no compute adapter — the GPU layout column is skipped");
}
for &n in &sizes {
let t = Instant::now();
let model = build(n);
let t_build = ms(t);
let deco = Decorations::default();
let t = Instant::now();
let cam = Camera::fit(&model, W as f32, H as f32, 24.0);
let t_fit = ms(t);
let t = Instant::now();
let frame = cpu::render(&model, &deco, &cam, W, H, Color::rgb(16, 16, 20));
let t_cpu = ms(t);
std::hint::black_box(&frame.rgba);
let rect = WidgetRect::new(0.0, 0.0, W as f32, H as f32);
let t = Instant::now();
let (_f, report) =
clip::render_graph_clipped(&model, &deco, &cam, W, H, rect, Color::rgb(16, 16, 20), true);
let t_clip = ms(t);
let visible: std::collections::BTreeSet<String> =
model.nodes.iter().map(|x| x.id.clone()).collect();
let lit = std::collections::BTreeSet::new();
let viewport = egui::Rect::from_min_size(egui::pos2(0.0, 0.0), egui::vec2(W as f32, H as f32));
let t = Instant::now();
let plan = legible::plan_view(
&model,
egui::pos2(cam.pan_x, cam.pan_y),
cam.zoom,
viewport,
&visible,
&lit,
None,
ViewOpts { gpu_cloud: false, thin_labels: true, thin_edges: true },
);
let t_plan = ms(t);
// 1000 probes spread across the viewport, through the linear picker...
let probes: Vec<(f32, f32)> = (0..1000)
.map(|i| {
let f = i as f32 / 1000.0;
(f * W as f32, (f * 7.0).fract() * H as f32)
})
.collect();
let t = Instant::now();
let mut hits = 0usize;
for &(x, y) in &probes {
if clip::pick(&model, &cam, rect, x, y).is_some() {
hits += 1;
}
}
let t_pick = ms(t);
// ...and the same 1000 through the grid index (rebuild included).
let t = Instant::now();
let mut idx = PickIndex::default();
idx.ensure(&model, &cam);
let mut ihits = 0usize;
for &(x, y) in &probes {
if idx.pick(&cam, viewport, egui::pos2(x, y)).is_some() {
ihits += 1;
}
}
let t_idx = ms(t);
let pairs: Vec<(u32, u32)> = (0..model.edges.len())
.map(|i| {
let e = &model.edges[i];
(e.from[1..].parse().unwrap(), e.to[1..].parse().unwrap())
})
.collect();
let t = Instant::now();
let csr = gpu_layout::GraphCsr::from_edges(n, &pairs, None);
let t_csr = ms(t);
let step = if n <= max_layout {
let seed = gpu_layout::LayoutState::seed(csr.n, (csr.n as f32).sqrt());
let p = gpu_layout::LayoutParams::default();
let t = Instant::now();
let s = gpu_layout::step_cpu(&seed, &csr, &p);
let d = ms(t);
std::hint::black_box(&s.pos);
format!("{d:.1}")
} else {
"skipped".to_string()
};
println!(
"{:>8} {:>8} {:>9.1} {:>9.1} {:>9.1} {:>9.1} {:>9.1} {:>9.1} {:>9.1} {:>9.1} {:>12}",
n,
model.edges.len(),
t_build,
t_fit,
t_cpu,
t_clip,
t_plan,
t_pick,
t_idx,
t_csr,
step
);
#[cfg(feature = "gpu")]
if let Some((dev, q)) = gpu_dev.as_ref() {
let usz: Vec<(usize, usize)> =
pairs.iter().map(|&(a, b)| (a as usize, b as usize)).collect();
let t = Instant::now();
let pos = gpu_layout::force_layout_gpu_on(dev, q, n, &usz, 50);
let d = ms(t);
let finite = pos.iter().all(|p| p[0].is_finite() && p[1].is_finite());
println!("{:>8} {:>8} gpu x50 iters (warm device): {d:.1} ms, {} positions, finite={finite}", n, "", pos.len());
}
eprintln!(
" n={n}: clipped drew {}/{} nodes, {}/{} edges | plan kept {} labels, {} edges | picks {hits} linear / {ihits} indexed, last_candidates={}",
report.nodes_drawn,
report.nodes_in,
report.edges_drawn,
report.edges_drawn + report.edges_culled,
plan.report.labels_placed,
plan.report.edges_drawn,
idx.last_candidates,
);
}
println!("\nall times are milliseconds, single deterministic run, release profile.");
}
/// **WORLD GRAPH lane probe** — how far does the *scale-aware* layout actually go?
///
/// For each target size it builds a faithful synthetic repos→crates→functions world
/// ([`WorldGraph::synthetic`], flagged SYNTHETIC) and times:
///
/// * `build` — materialising the hierarchy (+ the sparse call/containment edges, up
/// to `EDGE_CAP`; above it edges are skipped so the O(n) placement lane
/// can be measured without a 10M×3-edge allocation storm).
/// * `place` — [`world::hier_placement`], the O(n) space-filling placement (no force
/// pass) — the massive lane and the Barnes–Hut seed.
/// * `bh_step` — ONE Barnes–Hut O(n log n) parallel FR step (`facett_core::barnes_hut::
/// fr_step`), the real n-body lane; a converge is ~80 of these.
/// * `layout` — the full [`world::layout_world`] (BH converge below the budget, or the
/// O(n) placement above it) + which lane ran.
///
/// This is the direct answer to "the layout wall at 100k": the base table's O(n²)
/// `step_cpu` is ~24 s per step at 100k, whereas one Barnes–Hut step here is milliseconds,
/// and the placement lane is O(n) to 10M.
fn world_probe(sizes: &[usize]) {
// Cap edge materialisation so the placement-only lane can be measured at 10M without
// allocating ~30M edges (the force lane never runs there anyway).
const EDGE_CAP: usize = 2_000_000;
let budget = world::LayoutBudget::default();
println!(
"WORLD GRAPH scale-aware layout — synthetic repos→crates→functions (SYNTHETIC data)\n"
);
println!(" bh_max (force budget) = {}, bh iters = {}", budget.bh_max, budget.iters);
println!(
"{:>10} {:>8} {:>7} {:>10} {:>10} {:>10} {:>12} {:>12}",
"target", "n", "repos", "build", "place", "bh_step", "layout", "lane"
);
println!("{:->10} {:->8} {:->7} {:->10} {:->10} {:->10} {:->12} {:->12}", "", "", "", "", "", "", "", "");
for &target in sizes {
let with_edges = target <= EDGE_CAP;
let t = Instant::now();
let w = WorldGraph::synthetic(target, Lod::Functions, with_edges);
let t_build = ms(t);
let t = Instant::now();
let base = world::hier_placement(&w);
let t_place = ms(t);
std::hint::black_box(&base);
// ONE Barnes–Hut step (skip when edges weren't materialised — the force lane is
// not the massive lane).
let bh_step = if with_edges && !w.edges.is_empty() {
let edges: Vec<(usize, usize)> =
w.edges.iter().map(|&(a, b)| (a as usize, b as usize)).collect();
let adj = facett_core::barnes_hut::adjacency(w.n, &edges);
let k = (4.0 / w.n as f32).sqrt();
let seed = base.clone();
let t = Instant::now();
let s = facett_core::barnes_hut::fr_step::<2>(&seed, &adj, k, facett_core::barnes_hut::BH_THETA, 0.05);
let d = ms(t);
std::hint::black_box(&s);
format!("{d:.1}")
} else {
"skipped".to_string()
};
let t = Instant::now();
let (pos, lane) = world::layout_world(&w, &budget);
let t_layout = ms(t);
let finite = pos.iter().all(|p| p[0].is_finite() && p[1].is_finite());
println!(
"{:>10} {:>8} {:>7} {:>10.1} {:>10.1} {:>10} {:>12.1} {:>12}",
target,
w.n,
w.repo_count(),
t_build,
t_place,
bh_step,
t_layout,
lane.key(),
);
eprintln!(
" target={target}: n={} edges={} synthetic={} finite={finite} lane={}",
w.n,
w.edges.len(),
w.synthetic_flag(),
lane.key(),
);
}
println!("\nall times are milliseconds, single deterministic run, release profile.");
println!("`bh_step` ×{} ≈ a full Barnes–Hut converge; `place` is the whole O(n) massive lane.", budget.iters);
#[cfg(feature = "gpu-cloud")]
render_probe(sizes);
#[cfg(not(feature = "gpu-cloud"))]
println!("\n(render lane not measured: rebuild with `--features gpu-cloud` for the instanced GPU cloud frame numbers)");
}
/// **The RENDER lane at scale** (feature `gpu-cloud`) — proves the instanced GPU cloud
/// draws far past the layout wall. Builds a scene of `n` emissive node instances + a
/// sparse edge batch, uploads them, and times ONE full offscreen frame (scene pass +
/// bright + blur + composite) at 1920×1080 through the SAME renderer every facett graph
/// pane paints with ([`facett_core::render::gpu::graphcloud`]). The whole cloud is TWO
/// instanced draw calls regardless of `n`.
#[cfg(feature = "gpu-cloud")]
fn render_probe(sizes: &[usize]) {
use facett_core::render::gpu::graphcloud::{
render_graph_offscreen, BloomParams, EdgeInstance, GraphScene, NodeInstance,
};
println!("\nINSTANCED GPU CLOUD render — one 1920×1080 offscreen frame (scene+bloom):");
println!("{:>10} {:>10} {:>10} {:>12}", "nodes", "edges", "frame_ms", "node_inst");
println!("{:->10} {:->10} {:->10} {:->12}", "", "", "", "");
for &n in sizes {
// A grid-placed cloud projected into the 1920×1080 viewport (screen px).
let cols = (n as f64).sqrt().ceil() as usize;
let nodes: Vec<NodeInstance> = (0..n)
.map(|i| {
let (c, r) = (i % cols, i / cols);
let x = (c as f32 / cols as f32) * W as f32;
let y = (r as f32 / cols as f32) * H as f32;
NodeInstance { center: [x, y], radius: 1.5, _pad: 0.0, color: [0.2, 0.5, 1.0, 1.0] }
})
.collect();
// A sparse edge batch (cap it so the upload is bounded at 10M).
let edge_n = n.min(2_000_000);
let edges: Vec<EdgeInstance> = (0..edge_n)
.map(|i| {
let a = &nodes[i % n];
let b = &nodes[(i * 7 + 1) % n];
EdgeInstance { a: a.center, b: b.center, width: 0.75, _pad: 0.0, color: [0.1, 0.2, 0.4, 1.0] }
})
.collect();
let scene = GraphScene { background: [0.02, 0.022, 0.03, 1.0], nodes, edges };
let t = Instant::now();
let r = render_graph_offscreen(W, H, &scene, BloomParams::default());
let frame_ms = ms(t);
match r {
Some(gr) => println!("{:>10} {:>10} {:>10.1} {:>12}", n, edge_n, frame_ms, gr.node_instances),
None => {
println!("{:>10} {:>10} {:>10} {:>12}", n, edge_n, "no-adapter", 0);
break;
}
}
}
println!("(includes a cold device+pipeline create per row; a live host reuses the warm device.)");
}