Performance and scaling¶
SpatialDeform keeps a pure NumPy/SciPy solver and offers an optional parallel
Rust kernel through spatialdeform[rust]. backend="auto" selects Rust when
installed.
Measured performance¶
These measurements used an Apple M1 Max with 10 cores and 32 GB RAM, eight SMACOF iterations, single-threaded BLAS, and eight Rayon threads. Values are medians of repeated runs; other machines will differ.
For Gaussian spatial weights:
| Landmarks | Python | Rust | Speedup |
|---|---|---|---|
| 100 | 0.0010 s | 0.0010 s | 1.02× |
| 200 | 0.0026 s | 0.0017 s | 1.53× |
| 500 | 0.0156 s | 0.0048 s | 3.23× |
| 1,000 | 0.0626 s | 0.0167 s | 3.75× |
| 2,000 | 0.2689 s | 0.0839 s | 3.20× |
The street-network pipeline uses uniform pair weights. SpatialDeform recognizes that case, avoids allocating the weight matrix, and replaces the dense Cholesky factorization with an exact diagonal-minus-rank-one solve:
| Landmarks | Python | Rust | Speedup |
|---|---|---|---|
| 1,000 | 0.0447 s | 0.0043 s | 10.50× |
| 2,000 | 0.1824 s | 0.0149 s | 12.27× |
| 3,000 | 0.4082 s | 0.0332 s | 12.31× |
| 5,000 | 1.1394 s | 0.1015 s | 11.23× |
At 5,000 landmarks, peak resident memory in the benchmark fell from about
1.66 GiB to 1.28 GiB. The maximum Python/Rust coordinate difference across the
size sweep stayed below 1e-10.
Thread scaling¶
At 1,000 Gaussian-weighted landmarks, Rust improved from 0.0309 s with one
Rayon thread to 0.0170 s with eight threads. Gains flattened after four to
eight threads because array preparation and the linear solve are not part of
the parallel pair kernel. Set RAYON_NUM_THREADS before Python starts when a
deployment needs an explicit limit.
Complexity boundary¶
- The dissimilarity matrix remains dense and requires \(O(n^2)\) storage.
- Rust parallelizes the \(O(n^2)\) majorization and stress calculations.
- Uniform weights use an \(O(n)\) rank-one linear solve per iteration.
- Non-uniform weights still require one dense \(O(n^3)\) Cholesky factorization, followed by \(O(n^2)\) work per iteration.
For a 19,000-node street network, continue using landmark MDS rather than a full all-pairs embedding. Rust allows a larger landmark set and faster scenario iteration; it does not make a 19,000 × 19,000 dense matrix free.