facett-graphview/examples/layout_matrix.rs
//! **The layout / FDEB / point-cloud bench matrix**, native, one device.
//!
//! ```text
//! cargo run --release -p facett-graphview --features gpu --example layout_matrix -- \
//! [--sizes 1000,10000,100000] [--steps 80] [--cpu-budget-s 20] \
//! [--fdeb 500,2000] [--cloud 100000,1000000]
//! ```
//!
//! Prints one markdown row per (lane, size) — the rows `.nornir/facett-benchmarks.md`
//! quotes — with the adapter and the load average in every row, because the box is
//! shared and a number without its load is not a number.
//!
//! Lanes for the force layout (the same community graph the browser bench uses):
//!
//! * `gpu` — the all-pairs kernel (`cs_layout`, O(n²) per step), [`GpuLayout::new`];
//! * `gpu-grid` — the grid-pyramid kernel (`layout_grid.wgsl`, O(n log n) per step),
//! forced at every size with [`GpuLayout::new_grid`] (the shipped selector
//! [`GpuLayout::new_for`] only takes it at `GRID_MIN_NODES` and above);
//! * `cpu-1` — ONE core: `facett_core::barnes_hut::fr_step_serial`, the single-core
//! lane graphnav's CPU fallback and its benchmark baseline run (exact all-pairs below
//! `BH_THRESHOLD`, serial Barnes–Hut above);
//! * `cpu-all` — the same step fanned over every core by gatling
//! (`facett_core::barnes_hut::fr_step`), the CPU lane graphnav ships at scale.
//!
//! GPU rows time `steps` steps plus the readback (the whole converge a caller pays);
//! CPU rows time as many steps as fit in `--cpu-budget-s` (at least one) and report
//! ms/step, with the converge extrapolated to `steps`. `ms/step` is the comparable column.
use std::time::Instant;
use facett_core::barnes_hut;
use facett_core::render::gpu::{BloomParams, CloudCamera, CloudPoint, GraphGpu};
use facett_graphview::fdeb::{self, BundleParams};
use facett_graphview::{fdeb_gpu, gpu_layout};
fn graph(n: usize) -> Vec<(usize, usize)> {
// Communities of sqrt(n) nodes: a ring with a local chord each, plus one
// long-range edge per 16 nodes — the shape `browser_bench::graph_fixture` uses.
let c = (n as f64).sqrt().ceil() as usize;
let per = n.div_ceil(c).max(1);
let mut e = Vec::with_capacity(n * 2 + n / 16);
let mut r: u64 = 7;
let mut next = || {
r = r
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
(r >> 33) as usize
};
for k in 0..c {
let lo = k * per;
let hi = ((k + 1) * per).min(n);
if hi <= lo {
break;
}
let len = hi - lo;
for i in lo..hi {
e.push((i, lo + (i - lo + 1) % len));
if len > 3 {
e.push((i, lo + (i - lo + 2 + next() % (len - 2)) % len));
}
}
}
for i in (0..n).step_by(16) {
let j = next() % n;
if j != i {
e.push((i, j));
}
}
e
}
fn load() -> String {
std::fs::read_to_string("/proc/loadavg")
.map(|s| s.split_whitespace().take(3).collect::<Vec<_>>().join(" "))
.unwrap_or_default()
}
fn list(s: &str) -> Vec<usize> {
s.split(',')
.filter(|x| !x.trim().is_empty())
.map(|x| x.trim().parse().expect("comma-separated integers"))
.collect()
}
struct Row<'a> {
bench: &'a str,
lane: &'a str,
n: usize,
ms_per_step: Option<f64>,
total_ms: f64,
detail: String,
}
fn print_row(adapter: &str, r: &Row<'_>) {
let per = r
.ms_per_step
.map_or_else(|| "-".to_string(), |v| format!("{v:.3}"));
println!(
"| {} | {} | {} | {per} | {:.1} | {} · {adapter} · load {} |",
r.bench,
r.lane,
r.n,
r.total_ms,
r.detail,
load()
);
}
fn main() {
let mut sizes = vec![1_000, 10_000, 100_000];
let mut steps = 80usize;
let mut cpu_budget_s = 20.0f64;
let mut fdeb_sizes = vec![500, 2_000];
let mut cloud_sizes = vec![100_000, 1_000_000];
let mut cpu_only = false;
let mut a = std::env::args().skip(1);
while let Some(k) = a.next() {
let mut v = || a.next().unwrap_or_else(|| panic!("{k} needs a value"));
match k.as_str() {
"--sizes" => sizes = list(&v()),
"--steps" => steps = v().parse().expect("--steps N"),
"--cpu-budget-s" => cpu_budget_s = v().parse().expect("--cpu-budget-s S"),
"--fdeb" => fdeb_sizes = list(&v()),
"--cloud" => cloud_sizes = list(&v()),
// The CPU rows alone, on a box with no GPU (the build container): the GPU rows
// are then printed as NOT MEASURED, never replaced by anything else.
"--cpu-only" => cpu_only = true,
other => panic!("unknown argument {other}"),
}
}
// ONE device for every GPU row: the shipped probe (high-performance, compute,
// storage-buffer floor), so the rows run on the adapter a caller gets.
let (gpu, adapter_tag) = if cpu_only {
(None, "no GPU (--cpu-only)".to_string())
} else {
let instance = wgpu::Instance::default();
let adapter = pollster::block_on(instance.request_adapter(&wgpu::RequestAdapterOptions {
power_preference: wgpu::PowerPreference::HighPerformance,
force_fallback_adapter: false,
compatible_surface: None,
apply_limit_buckets: false,
}))
.expect("no GPU adapter — run with --cpu-only for the CPU rows alone");
let info = adapter.get_info();
assert_ne!(
info.device_type,
wgpu::DeviceType::Cpu,
"{} is a CPU rasteriser, not a GPU",
info.name
);
let dq = pollster::block_on(adapter.request_device(&wgpu::DeviceDescriptor {
label: Some("layout_matrix"),
required_features: wgpu::Features::empty(),
required_limits: adapter.limits(),
memory_hints: wgpu::MemoryHints::Performance,
experimental_features: wgpu::ExperimentalFeatures::disabled(),
trace: wgpu::Trace::Off,
}))
.expect("request_device");
(
Some(dq),
format!("{} ({:?}, {:?})", info.name, info.device_type, info.backend),
)
};
let not_measured = |bench: &str, lane: &str, n: usize| {
println!(
"| {bench} | {lane} | {n} | - | - | NOT MEASURED: no GPU on this box · load {} |",
load()
);
};
let cores = std::thread::available_parallelism().map_or(1, usize::from);
println!(
"# layout_matrix — {adapter_tag}, {cores} cores, steps={steps}, load at start {}",
load()
);
println!("| bench | lane | n | ms/step | total ms | detail |");
println!("|---|---|---|---|---|---|");
// Warm both kernels once so shader compile is not billed to the first row.
if let Some((device, queue)) = &gpu {
let w = graph(2_000);
let w32: Vec<(u32, u32)> = w.iter().map(|&(x, y)| (x as u32, y as u32)).collect();
let g = gpu_layout::GraphCsr::from_edges(2_000, &w32, None);
let s = gpu_layout::LayoutState::seed(2_000, 10.0);
let p = gpu_layout::LayoutParams::default();
gpu_layout::GpuLayout::new(device, &g, &s).iterate(device, queue, &g, &p, 2);
if let Some(mut gl) = gpu_layout::GpuLayout::new_grid(device, &g, &s) {
gl.iterate(device, queue, &g, &p, 2);
}
}
for &n in &sizes {
let edges = graph(n);
let e32: Vec<(u32, u32)> = edges.iter().map(|&(x, y)| (x as u32, y as u32)).collect();
let g = gpu_layout::GraphCsr::from_edges(n, &e32, None);
let p = gpu_layout::LayoutParams::default();
let seed = gpu_layout::LayoutState::seed(n, p.ideal_len * (n as f32).sqrt());
for lane in ["gpu", "gpu-grid"] {
let Some((device, queue)) = &gpu else {
not_measured("layout", lane, n);
continue;
};
// All pairs at grid scale on an integrated GPU is one submit of n² work per
// step that outlives the driver's ring timeout: MEASURED t14s (Radeon 890M,
// 2026-09-29) — 80 steps at 100 000 nodes → `ring gfx_0.0.0 timeout`, a GPU
// ring reset and a lost device. The shipped selector never runs it there
// (`new_for` takes the grid at >= GRID_MIN_NODES), so neither does the bench.
if lane == "gpu"
&& n >= gpu_layout::GRID_MIN_NODES
&& !adapter_tag.contains("DiscreteGpu")
{
println!(
"| layout | gpu | {n} | - | - | not run: all-pairs at {n} on an integrated GPU exceeds the driver's ring timeout (ring reset measured t14s 2026-09-29); the shipped lane here is gpu-grid · {adapter_tag} · load {} |",
load()
);
continue;
}
let t = Instant::now();
let gl = if lane == "gpu" {
Some(gpu_layout::GpuLayout::new(device, &g, &seed))
} else {
gpu_layout::GpuLayout::new_grid(device, &g, &seed)
};
let Some(mut gl) = gl else {
println!("| layout | {lane} | {n} | - | - | not run: the device binds < 7 storage buffers · {adapter_tag} · load {} |", load());
continue;
};
let upload = t.elapsed().as_secs_f64() * 1e3;
let t = Instant::now();
gl.iterate(device, queue, &g, &p, steps);
let pos = gl.read_positions(device, queue);
let ms = t.elapsed().as_secs_f64() * 1e3;
assert!(
pos.iter().all(|q| q[0].is_finite() && q[1].is_finite()),
"{lane} n={n}: non-finite position"
);
print_row(
&adapter_tag,
&Row {
bench: "layout",
lane,
n,
ms_per_step: Some(ms / steps as f64),
total_ms: ms,
detail: format!("{steps} steps + readback, edges {}, upload+compile {upload:.1} ms, kernel {}", edges.len(), gl.kernel()),
},
);
}
// The CPU lanes — graphnav's FR step (same k / theta / cooling as
// `facett_graphnav::layout::force_directed`).
let adj = barnes_hut::adjacency(n, &edges);
let k = (4.0 / n as f32).sqrt();
let theta = barnes_hut::BH_THETA;
for lane in ["cpu-1", "cpu-all"] {
let mut pos: Vec<[f32; 2]> = (0..n)
.map(|i| {
let a = std::f32::consts::TAU * i as f32 / n as f32;
[0.85 * a.cos(), 0.85 * a.sin()]
})
.collect();
let t = Instant::now();
let mut done = 0usize;
while done < steps && (done == 0 || t.elapsed().as_secs_f64() < cpu_budget_s) {
let temp = 0.1 * (1.0 - done as f32 / steps as f32);
pos = if lane == "cpu-1" {
barnes_hut::fr_step_serial::<2>(&pos, &adj, k, theta, temp)
} else {
barnes_hut::fr_step::<2>(&pos, &adj, k, theta, temp)
};
done += 1;
}
let ms = t.elapsed().as_secs_f64() * 1e3;
let per = ms / done as f64;
print_row(
&adapter_tag,
&Row {
bench: "layout",
lane,
n,
ms_per_step: Some(per),
total_ms: per * steps as f64,
detail: format!(
"{done} of {steps} steps timed ({ms:.0} ms), total extrapolated, {} (BH above {}), {} worker(s)",
if n >= barnes_hut::BH_THRESHOLD { "Barnes-Hut" } else { "exact all-pairs" },
barnes_hut::BH_THRESHOLD,
if lane == "cpu-1" { 1 } else { cores }
),
},
);
}
}
// FDEB: the GPU bundler against the CPU one on the same laid-out graph.
for &m in &fdeb_sizes {
// m edges over ~m/2 nodes on a circle: every chord crosses many others.
let nn = (m / 2).max(4);
let nodes: Vec<fdeb::P2> = (0..nn)
.map(|i| {
let a = std::f32::consts::TAU * i as f32 / nn as f32;
[a.cos(), a.sin()]
})
.collect();
let edges: Vec<(usize, usize)> = graph(nn).into_iter().take(m).collect();
let bp = BundleParams::default();
let t = Instant::now();
let bundled = gpu
.as_ref()
.map(|(device, queue)| fdeb_gpu::bundle_gpu_on(device, queue, &nodes, &edges, &bp));
let gpu_ms = t.elapsed().as_secs_f64() * 1e3;
let t = Instant::now();
let cpu = fdeb::bundle(&nodes, &edges, &bp);
let cpu_ms = t.elapsed().as_secs_f64() * 1e3;
let len = |b: &[fdeb::BundledEdge]| fdeb::total_length(b);
match &bundled {
None => not_measured("fdeb", "gpu", edges.len()),
Some(gpu) => print_row(
&adapter_tag,
&Row {
bench: "fdeb",
lane: "gpu",
n: edges.len(),
ms_per_step: Some(gpu_ms / bp.iterations as f64),
total_ms: gpu_ms,
detail: match &gpu {
Some(b) => format!(
"{} iterations, {} subdivisions, ink {:.1}",
bp.iterations,
bp.subdivisions,
len(b)
),
None => "the device refused the buffers".into(),
},
},
),
}
print_row(
&adapter_tag,
&Row {
bench: "fdeb",
lane: "cpu-1",
n: edges.len(),
ms_per_step: Some(cpu_ms / bp.iterations as f64),
total_ms: cpu_ms,
detail: format!(
"{} iterations, {} subdivisions, ink {:.1}",
bp.iterations,
bp.subdivisions,
len(&cpu)
),
},
);
}
// Point cloud: upload once, render (instanced points + bloom + RGBA readback).
let (w, h) = (1600u32, 1000u32);
for &n in &cloud_sizes {
let Some((device, queue)) = &gpu else {
not_measured("cloud", "gpu", n);
continue;
};
let mut gg = GraphGpu::new(device, wgpu::TextureFormat::Rgba8Unorm);
let pts: Vec<CloudPoint> = (0..n)
.map(|i| {
const GOLDEN: f32 = 2.399_963_2;
let r = ((i as f32 + 0.5) / n as f32).sqrt();
let a = i as f32 * GOLDEN;
CloudPoint::new(
[r * a.cos(), r * a.sin(), 0.0],
egui::Color32::from_rgb(90 + (i % 160) as u8, 140, 220),
)
})
.collect();
let t = Instant::now();
let cloud = gg.upload_cloud(device, queue, &pts, &[], 0).expect("the cloud fits this device");
let cam = CloudCamera::frame(w as f32, h as f32, 0.0, 1.0, 1.0);
gg.write_cloud_camera(queue, &cam);
let upload = t.elapsed().as_secs_f64() * 1e3;
let t = Instant::now();
let first = gg.render_cloud(
device,
queue,
w,
h,
&cloud,
[0.04, 0.05, 0.06, 1.0],
BloomParams::default(),
);
let first_ms = t.elapsed().as_secs_f64() * 1e3;
let frames = 10usize;
let t = Instant::now();
let mut drawn = 0u32;
for f in 0..frames {
gg.write_cloud_camera(
queue,
&CloudCamera::frame(w as f32, h as f32, f as f32 * 0.05, 1.0, 1.0),
);
drawn = gg
.render_cloud(
device,
queue,
w,
h,
&cloud,
[0.04, 0.05, 0.06, 1.0],
BloomParams::default(),
)
.node_instances;
}
let steady = t.elapsed().as_secs_f64() * 1e3 / frames as f64;
print_row(
&adapter_tag,
&Row {
bench: "cloud",
lane: "gpu",
n,
ms_per_step: Some(steady),
total_ms: upload + first_ms,
detail: format!(
"{w}×{h}, ms/step = steady frame incl. RGBA readback ({frames} frames), total = upload {upload:.1} + first frame {first_ms:.1}, instances {} / {drawn}",
first.node_instances
),
},
);
}
}