Summary
Add a benchmark group to benches/exact.rs that runs N random matrices per dimension and reports median/p95/p99 timings, capturing variance that fixed single-input benchmarks miss.
Originally proposed as item #3 in #80 and explicitly scoped out of that PR; tracking here for a future release.
Current State
benches/exact.rs measures exact-arithmetic performance on fixed inputs only:
- Per-dimension well-conditioned matrices (
exact_d{2..5})
- Four adversarial groups (
exact_near_singular_3x3, exact_large_entries_3x3, exact_hilbert_4x4, exact_hilbert_5x5)
Each bench measures a single input, so reported times only characterise that specific matrix. Branch misprediction, allocation patterns, and intermediate BigInt sizes vary with input structure in ways a single fixed input cannot capture.
Proposed Changes
Add a new bench group (e.g. exact_random_percentile_d{2..5}) that:
- Generates N (e.g. 50 or 100) random matrices per dimension with a seeded RNG for reproducibility
- Runs
det_exact, det_sign_exact, solve_exact, solve_exact_f64 on each
- Reports median, p95, and p99 timings per bench using Criterion's custom measurement /
iter_batched APIs
Design considerations:
- Use a fixed seed (e.g.
[0u8; 32]) so CI and local runs agree
- Matrix generation must avoid singularity — use a diagonally-dominant construction (same shape as
make_diagonally_dominant in tests/proptest_exact.rs) rather than reject-retry, which is harder to reproduce
- RHS generation should match — small integers keep construction simple and exact
- Budget bench runtime: consider limiting N per dimension, restricting to D=3..=5, or gating behind a separate recipe (
just bench-exact-random) given the higher runtime cost
Benefits
- Captures variance that fixed single-input benches miss (branch misprediction, allocation patterns, intermediate
BigInt sizes)
- Detects tail-case regressions where the median is unchanged but p99 worsens
- Provides stronger empirical grounding for
docs/PERFORMANCE.md claims
Implementation Notes
Related: #80
Summary
Add a benchmark group to
benches/exact.rsthat runs N random matrices per dimension and reports median/p95/p99 timings, capturing variance that fixed single-input benchmarks miss.Originally proposed as item #3 in #80 and explicitly scoped out of that PR; tracking here for a future release.
Current State
benches/exact.rsmeasures exact-arithmetic performance on fixed inputs only:exact_d{2..5})exact_near_singular_3x3,exact_large_entries_3x3,exact_hilbert_4x4,exact_hilbert_5x5)Each bench measures a single input, so reported times only characterise that specific matrix. Branch misprediction, allocation patterns, and intermediate
BigIntsizes vary with input structure in ways a single fixed input cannot capture.Proposed Changes
Add a new bench group (e.g.
exact_random_percentile_d{2..5}) that:det_exact,det_sign_exact,solve_exact,solve_exact_f64on eachiter_batchedAPIsDesign considerations:
[0u8; 32]) so CI and local runs agreemake_diagonally_dominantintests/proptest_exact.rs) rather than reject-retry, which is harder to reproducejust bench-exact-random) given the higher runtime costBenefits
BigIntsizes)docs/PERFORMANCE.mdclaimsImplementation Notes
EXACT_GROUPSinscripts/bench_compare.py(and a corresponding_group_headingbranch)Related: #80