Performance Benchmarks

The matrix layer is optimized for dense, read-heavy workloads. To validate that assumption we ship hardened Vitest benches under test/benchmarks/. The most important suites are:

• matrix-vs-sets.benchmark.ts: runs BFS, Dijkstra, and SCC on 1 024 and 4 096 vertex graphs. Each vertex creates 8 outgoing edges. SCC is measured on a dedicated 256 vertex fixture that is reused for every round, otherwise the runtime would explode.
• bfs.benchmark.ts, dijkstra.benchmark.ts, shortest-path.benchmark.ts, and scc.benchmark.ts: zoom in on individual algorithms.

Running the realistic suite

# Default: 1k / 4k vertices for BFS & Dijkstra, 256 vertices for SCC
pnpm vitest bench test/benchmarks/matrix-vs-sets.benchmark.ts

The shared Tinybench options use a 30 ms measurement window, at least 2 iterations, a 10 ms warmup, and at least 100 samples. Change DEFAULT_SIZES in the benchmark when testing other graph sizes and record the hardware, runtime, and package revision with every result.

Interpreting the numbers

• Compare set and matrix results from the same machine and process.
• Include memory consumption because adjacency matrices grow quadratically with the vertex count.
• Treat results as workload-specific; graph density, degree distribution, weights, and mutation frequency all affect the outcome.

Recommendations

Graph profile	Suggested setting	Notes
Sparse or mutation-heavy	Start with sets	Storage follows existing edges and avoids resizing a V × V grid
Dense and read-heavy	Benchmark the matrix layer	Indexed access may improve traversals at the cost of quadratic memory
Memory-constrained	Prefer sets	Measure peak memory before enabling matrices

Custom scenarios

The shared fixture generator (test/benchmarks/utils.ts) uses deterministic graphs with eight outgoing edges per vertex and positive weights. Clone it if you need domain-specific degree distributions or weight patterns, and contribute back noteworthy results so this guide stays accurate.