nordisk/nornir

mimir-graph bench — 2026-10-12

Runner: cargo run --release -p nornir-mimir-graph --example graph_bench -- [--nodes N --edges M] (an example, not nornir's register_bench! registry — that registry compiles into the nornir lib and would make every nornir build link libgraphblas).

Box: dwarf — AMD Ryzen 5 7535HS, 6 cores / 12 threads, no AVX-512, 61 GB. Ubuntu libgraphblas7 7.4.0 (OpenMP), GraphBLAS threads = 12.

Caveat: the box was shared and heavily oversubscribed (other agents' cargo builds and mimir-driver runs; load average 33–41 on 12 threads during these runs). Wall times swing 1.5–3× between runs; min is the better estimate of the op's own cost. An idle-box rerun is still owed.

Graph: random power-law, from = π(⌊n·u^1.5⌋), to = π(⌊n·u^2⌋), π a fixed bijection of the ids; sorted by (from, to) and de-duplicated (the shape of a sorted code_edges scan). Being random, it has one giant strongly connected part, so unbounded walks touch ~every node — the worst case for reach. similarity runs on a separate 10⁵-node / 10⁶-edge graph from the same generator. "10 000 seeds" are random node ids.

10⁶ nodes / 10⁷ edges (load average 36 at start)

peak RSS (VmHWM): 1565 MB

Earlier runs the same evening (load 15–33) for scale: sorted Arrow pack 85–203 ms, reach 1 seed 120–380 ms, reach 10 000 seeds 125–331 ms, transpose 357–510 ms, components 1.5–3.1 s.

10⁷ nodes / 10⁸ edges (load average 38 at start; queries median of 3)

peak RSS (VmHWM): 9390 MB

(mask_by and similarity keep their 10⁵-node sizes in this run; the 1e5-node scope on the 10⁷-node graph keeps only ~10⁴ edges, hence the small time.)

Reading

• Import: a sorted edge scan → CSR is ~0.1 s per 10⁷ edges and ~1.1 s per 10⁸ (single-threaded Rust scan + cumsum + one memcpy, then a zero-copy GxB_Matrix_pack_CSR). Unsorted input through GraphBLAS' own build is 4.5–13× slower — keep code_edges sorted by (from, to) as §11 says. GrB_Matrix_import (GraphBLAS copies) is 2–4× slower than pack at 10⁷.
• Peak RSS: 1.6 GB at 10⁷ edges, 9.4 GB at 10⁸ — the bench holds several copies on purpose (generator edges, two Arrow batches, CSR arrays, A, Aᵀ, a second snapshot). One resident 10⁸-edge boolean matrix is ~0.8 GB (64-bit Aj) + 80 MB offsets.
• Reverse walks: reverse_reach (mxv on A) is 2–10× slower (typically ~5×) than reach on a cached Aᵀ; transposing once costs about one walk at 10⁷ (0.4 s) and ~2 walks at 10⁸ (4.7 s). Lenses doing dependents walks should keep Aᵀ.
• Bounded walks (≤ 2 hops) are 3–5× cheaper than full ones.
• max_on_path and components are fixpoint loops over dense vectors and are the slowest ops (1.5–12 s); fine for a per-snapshot job, not for an interactive query on 10⁸ edges without a smarter algorithm (frontier-based max propagation, FastSV).