InsightSoftwareConsortium / InsightSoftwareConsortium/ITK
PERF: Benchmark and tune the hard-coded `itk::Math::SVD` algorithm-selection thresholds
- Dominant language
- C++
- Stars
- 1.7k
- Forks
- 748
- Avg merge
- 1d 1h
- Merged PRs (30d)
- 64
Description
`itk::Math::SVD` selects its Eigen engine from two hard-coded `constexpr` thresholds in `Modules/Core/Common/include/itkMathSVD.h` — `kFixedSVDMaxDim = 16` (line 390) and `kJacobiMaxDim = 6` (line 394). These steer between genuinely different algorithmic paths but were chosen from a single idle-machine arm64 benchmark pass. They should be re-derived from a proper cross-platform sweep before the SVD whitepaper treats them as settled.
What the constants do (verified on main)
`Modules/Core/Common/include/itkMathSVD.h`:
```cpp
constexpr unsigned int kFixedSVDMaxDim = 16; // :390
constexpr unsigned int kJacobiMaxDim = 6; // :394
...
if (n <= kJacobiMaxDim) // :423 runtime path
...
if constexpr (VDim > kFixedSVDMaxDim) // :439 fixed/compile-time path
```
- **`kFixedSVDMaxDim = 16`** — fixed compile-time SVDs with `VDim > 16` fall back from the stack `JacobiSVD` path to the runtime path, to stay under Eigen's stack-allocation limit. The boundary is **untested by GTest**: the largest fixed-size test is `VDim = 6`.
- **`kJacobiMaxDim = 6`** — runtime square SVDs use `JacobiSVD` + `NoQRPreconditioner` for `n <= 6`, else `BDCSVD`. The crossover came from idle-machine benchmarks only.
The in-source comment at `:445-446` states the rationale for the fixed path: compile-time sizes ≤ `kFixedSVDMaxDim` always take `JacobiSVD` because it stack-allocates, fully unrolls, and beats `BDCSVD`'s dynamic setup at these sizes.
Why the current values are suspect
The ITK 6 migration guide's SVD performance table (`itk_6_migration_guide.md`) shows a non-monotonic picture:
| size | Eigen-backed `itk::Math::SVD` vs `vnl_svd` |
|---|---|
| 3x3, 4x4 | ~2x faster |
| 6x6 | ~parity |
| **7x7** | **not benchmarked** |
| 8x8, 16x16 | ~0.5-0.8x — `vnl_svd`/LINPACK **wins** |
| >=50x50 | ~1.5-2.3x faster (BDCSVD) |
So there is an unmeasured gap right at the `kJacobiMaxDim` boundary (7x7), and a mid-size regression band (8x8-16x16) where the legacy LINPACK path is still faster. Both are exactly where the thresholds live.
Suggested approach
1. Sweep `n = 5, 6, 7, 8, ..., 20` plus the fixed `VDim = 16 / 17` boundary. Single-threaded, median of `N >= 12` runs, on at least two platforms (arm64 + x86_64), under **verified-idle** load.
2. Measure both **time and accuracy** (round-trip residual) per engine per size — a faster engine that loses digits is not a win.
3. Investigate whether LINPACK's mid-size (8x8 / 16x16) advantage is a hardware-alignment effect Eigen could match via alignment hints or fixed-size maps.
4. Re-derive `kJacobiMaxDim` and `kFixedSVDMaxDim` from the data, and consider whether either should be platform-conditional.
5. Add GTest coverage at the `kFixedSVDMaxDim` boundary — currently the largest fixed-size test is `VDim = 6`, so the 16/17 dispatch switch is untested.
6. Fold the results into the SVD whitepaper and update the migration-guide performance table (including the missing 7x7 row).
Related
- PR #6487 — `ENH: Add Eigen-backed itk::Math::SVD` (introduced both constants)
- Review comments by @tuicr on `itkMathSVD.h` (2026-06-21) requesting empirical justification for the two thresholds
- `Documentation/docs/migration_guides/itk_6_migration_guide.md` — the SVD performance table to update
- Issue #6403 — VNL → Eigen numerics migration umbrella (stages the SVD migration; does not cover dispatch tuning)
- PR #6473 — `vnl_svd` retirement track
Contributor guide
Research direction
Start in Modules/Core/Common/include/itkMathSVD.h, tracing the kJacobiMaxDim and kFixedSVDMaxDim dispatches and their rationale. Run the proposed single-threaded sweep for n=5–20 and fixed VDim 16/17 on arm64 and x86_64, recording time and round-trip residuals. Add GTest coverage for the fixed-size boundary, then update Documentation/docs/migration_guides/itk_6_migration_guide.md and the SVD whitepaper with the measured results and final thresholds.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- documentation, performance, testing
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100