InsightSoftwareConsortium / InsightSoftwareConsortium/ITK

PERF: Benchmark and tune the hard-coded `itk::Math::SVD` algorithm-selection thresholds

Open
#6,741 0 comments 0 reactions 0 assignees View on GitHub
area:Numerics type:Enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.