Numba: compile small, statically shaped linear algebra (e.g. Scan steps) into one kernel
I maintainer di solito rispondono entro 1 giorno
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 5/100
Direzione di ricerca
This is a design proposal for a new op (ScalarizedBlock), a rewrite (scalarize_blocks) and a Numba lowering, with a seven-PR split and open maintainer questions about the default switch and size caps. Start from the Numba backend's existing FusedElemwise handling and the optdb pass ordering the issue mentions, and wait for maintainer direction before picking up any layer. Done means a maintainer decides the shape, after which a single PR (for example the cache-wrapping fix, PR 1) can be tested with tests/link/numba.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Summary
In the Numba backend, a Scan over small fixed-size linear algebra, such as a Kalman filter with a 3×3 state, spends most of its time on per-Op overhead, not arithmetic. Every Dot, Cholesky or solve in the step allocates its output and calls BLAS/LAPACK on a 3×3 matrix. This is the slowdown that keeps pymc-extras' statespace models on JAX (pymc-devs/pymc-extras#552).
I have a prototype that compiles such a step into a single straight-line Numba function. It is 8–12× faster on a 3×3 Kalman filter (forward and gradient) and about 10× faster to sample a real model with nutpie. Before opening PRs, I'd like your view on whether you want this in PyTensor, and in what shape.
The problem
Minimal example: P_{t+1} = A P_t Aᵀ + Q with 3×3 matrices, 200 steps, compiled with mode="NUMBA".
| ns per step, forward | forward + gradient | |
|---|---|---|
main |
191 | 918 |
| the same recursion written as one Numba loop | 22 | 110 |
For a 3×3 Kalman filter (Cholesky of the innovation covariance, two cho_solves, a few Dots, log-determinant from the diagonal), main runs 21 Ops per step at 669 ns per step forward and 3,078 ns with the gradient.
Profiling a hand-written version of the same filter puts the overhead at about 40% allocation of intermediate arrays and 60% BLAS/LAPACK dispatch:
| Version (hand-written Numba, 3×3, 182 steps) | ns per step |
|---|---|
| one loop, preallocated | ~85 |
| the same loops, a fresh array per operation | ~460 |
np.linalg / @ (BLAS/LAPACK calls, allocating) |
~970 |
The Scan machinery itself is not the problem: an empty-body scan over the same 182 steps costs 6 µs forward and 13 µs with the gradient (35–70 ns per step).
What I tried before this, on the Kalman example above (main: ~650 ns per step forward, ~3,100 with the gradient):
- Small-matrix branches in
_gemm,_choleskyand the solves (loop kernels instead of BLAS/LAPACK below 8×8): no measurable gain (≤2%). Each Op still allocates its output and is a separate call. - A rewrite expanding small
Dots into broadcast-multiply-and-sum: −20 to −30% (forward and gradient). Expanding them into explicit scalar sums instead gives nothing (114 Ops per step). Elemwise fusion can't go further, because a chained matrix product (A @ P @ Aᵀ) needs the first product complete before the second can start, and Cholesky and the solves stay separate Ops. - Fusing the whole step: this is what removes the overhead.
Proposal: ScalarizedBlock
This follows the same pattern as FusedElemwise and #2310's ScalarizeRewriter.
- The op.
ScalarizedBlockis aFinalizedOpFromGraphwrapping a small, statically shaped subgraph. Backends other than Numba evaluate it as a regularOpFromGraph. - The Numba lowering. It generates one straight-line function for the whole block:
- each element of each value becomes a local scalar, and each Op becomes the scalar arithmetic for its output elements;
- only the block's outputs are allocated, and there are no BLAS/LAPACK calls;
- constants are typed, so float32 stays float32, and int8/int16/int32 arithmetic wraps around as in PyTensor;
- division and powers use NumPy functions, so
x / 0gives inf/nan rather than raising, even once the kernel is inlined into its caller; - failures match the LAPACK lowerings (a non-PD Cholesky or singular triangular solve gives all-NaN);
- the cache key is a hash of the generated source;
- a block containing an Op without a handler falls back to the regular
OpFromGraphlowering, with its outputs copied so they never alias its inputs.
- The rewrite (
scalarize_blocks, optdb 49.4: after elemwise fusion, before the in-place passes):- It wraps a convex region of nodes whose values are boolean, integer or float, with at most 64 elements (8×8) each.
- A region only becomes a block if it contains an Op whose regular lowering calls BLAS/LAPACK (
Dot,Cholesky,SolveTriangular,CholeskySolve). Elementwise ops and indexing join a block but never cause one. - It applies to Scan inner graphs, which is where the gain is.
Supported Ops:
- elementwise ops: arithmetic, comparisons, boolean logic,
switch,isnan, casts andComposites; DimShuffle, sum/product reductions;Dot, unbatchedBlockwise;Cholesky,SolveTriangular,CholeskySolve,ExtractDiag;Alloc,Eye,AllocDiag;- basic and advanced (Inc)Subtensor with constant indices.
That is enough for a Kalman filter's forward and backward (gradient) steps to each become one block.
Results
ns per scan step, 3×3 matrices, 200 steps, float64:
| Matrix recursion, fwd | fwd + grad | Kalman, fwd | fwd + grad | |
|---|---|---|---|---|
main |
191 | 918 | 669 | 3,078 |
| with blocks | 39 | 98 | 80 | 253 |
| speedup | 4.9× | 9.4× | 8.4× | 12.2× |
| hand-written single Numba loop | 22 | 110 | 95 | – |
mode="JAX", same graph |
34 | 69 | 358 | 1,592 |
All rows ran in one session. With blocks, the gradient of the matrix recursion and the forward Kalman step are both faster than my hand-written loops, since the unrolled code is optimised as a whole.
JAX is about 2× faster than Numba main on the Kalman filter, which is why statespace models currently default to it. With blocks, Numba is 4.5× (forward) to 6.3× (gradient) faster than JAX there. On the pure matrix recursion (only Dots and additions) XLA fuses the step itself and stays slightly ahead; it does not fuse through Cholesky and the solves.
Across state sizes (Kalman filter, forward + gradient, float64, cold-cache compile of both functions):
| k | 2 | 3 | 4 | 6 | 8 |
|---|---|---|---|---|---|
main, µs |
560 | 631 | 644 | 824 | 1,861 |
| with blocks, µs | 54 | 63 | 89 | 173 | 325 |
| speedup | 10.4× | 10.0× | 7.2× | 4.8× | 5.7× |
compile, main → blocks |
13 → 5 s | 13 → 6 s | 14 → 9 s | 14 → 21 s | 14 → 46 s |
| generated lines, gradient step | 307 | 630 | 1,072 | 2,313 | 4,030 |
float32 gives similar speedups (12.6× at k = 2, 4.8× at k = 7).
The binding limit is compile time, not speed. The unrolled code writes out every scalar operation, so a block's arithmetic grows like k³ and its line count like k² (each line of a k×k product sums k terms). Up to k = 8 a block costs at most ~30 s of extra compilation, which a typical sampling run (~10⁵ gradient evaluations) recovers several times over. Beyond that the trade-off turns: at k = 10 the speedup falls to 4.1× while compilation takes 95 s, and at k = 12 to 1.9× at 187 s, more than a typical run saves.
Hence the caps: 64 elements (8×8) per value and 5,000 generated lines. Larger graphs keep today's lowering. That covers the common state-space models: local level and trend (k = 1–2), AR/ARMA (k = p), small VARs (k = n·p), and a trend with a few Fourier harmonics (k ≈ 5–9).
What blocks don't help: large state
I also prototyped a lowering that generates loops over fixed-size scratch buffers instead of unrolling, to keep code size flat for larger k. Compile time stayed at ~25 s regardless of k, but it is slower than unrolling wherever both apply, and slower than main beyond k ≈ 12:
| k | 3 | 8 | 12 | 16 | 53 |
|---|---|---|---|---|---|
main, µs |
634 | 1,909 | 2,737 | 3,325 | 19,482 |
| loops, µs | 96 | 523 | 2,236 | 4,564 | 168,300 |
| unrolled, µs | 63 | 325 | 1,324 | – | – |
(Kalman, forward + gradient; the unrolled row is from a separate run.) At k ≈ 15+ the step is dominated by arithmetic, which BLAS does better than naive loops, so per-Op overhead stops mattering. Models with a large state, typically week-of-year or long seasonal components (k ≈ 30–53), need a different approach, such as exploiting the sparse transition matrix or a steady-state filter. That belongs in pymc-extras, not here, so I dropped the loop lowering.
Real model: a joint VAR + marketing-mix model built on pymc-extras' BayesianVARMAX (a 3-dimensional state, 182 steps). Sampled with nutpie, 4 chains × 2,000 draws, all runs in one session. Both scan steps (forward, 41 nodes; gradient, 86 nodes) compile to one block each.
| Model | µs per gradient | sampling time | ESS/s (VAR coefficients) | |
|---|---|---|---|---|
| Kalman filter, surveys exact | main |
1,652 | 74.4 s | 36.8 |
| with blocks | 180 | 8.1 s | 384.9 (10.5×) | |
| Kalman filter, survey noise modelled | main |
1,896 | 86.9 s | 30.0 |
| with blocks | 211 | 9.6 s | 316.6 (10.6×) | |
| Equivalent model in a specialised VAR library (no Scan) | either | 359 | 31.0 s | 62.7 |
Both arms take the same number of gradient evaluations per draw and the same step size, so the gain is all per-gradient speed (about 9×). Across three separate sessions (one with the model's data and dims frozen) the ESS/s speedup ranged from 8.7× to 12.3×. I couldn't sample this model with nutpie's JAX backend: the gradient of the media-adstock Pad slices with bounds taken from a runtime shape, which JAX rejects, so the JAX comparison above is on the 3×3 examples only. The specialised library's model has no Scan, and blocks leave its speed unchanged (repeat runs: 484 µs on main, 478 and 499 µs with blocks). Values and gradients match the current lowering to ~1e-14–1e-12.
How I'd split it
The stack is built locally and passes tests/link/numba, tests/scan, tests/tensor, tests/compile and tests/graph in Numba mode. Every PR is one commit with its own tests:
- Numba: don't wrap inline kernels for caching (+35).
numba_funcify_ensure_cachewraps cached kernels asf(*args). Numba can't inline through that, so an Op kernel jitted withinline="always"fails to compile with the cache on. This PR is independent of the rest. ScalarizedBlockop and Numba lowering (+567, 372 of them code): elementwise (including comparisons and boolean logic),DimShuffle, reductions,Dot,Blockwise. Nothing creates blocks yet.scalarize_blocksrewrite, opt-in (mode.including("scalarize_blocks"), +245/−2).- Cholesky and solves (+154/−2).
- Construction and constant-index indexing (+164/−1). The gradient step needs these.
- Enable by default in Numba mode (+25/−13). This is the switch, kept separate so it can be discussed on its own. It updates 21 existing tests that count
Cholesky/Solve/Dotnodes in compiled graphs, which are now inside blocks. The rewrites those tests check (decomposition reuse, block-diagonal pushdown, in-place solves) run earlier and still apply. - Inline block kernels into their caller (+7/−2, needs 1). This removes a call per scan iteration and gives about a third of the final speedup.
Each layer leaves main working, and nothing changes for users until 6.
Questions for maintainers
-
Do you want this in PyTensor? If yes, is a separate generator (as here) right, or should it be an extension of #2310's
ScalarizeRewriterto small arrays? -
The switch (PR 6). Should it be on by default for every Numba graph, or narrower? Options:
- on by default in Numba mode (PR 6 as written);
- only for Scan inner graphs, where the gain is, by hooking into the Numba Scan inner-graph pass instead of optdb;
- opt-in carried by the graph: a library such as pymc-extras marks its filter's Scan, and only marked Scans get blocks. This matters because samplers like nutpie compile with a fixed
mode="NUMBA", so a user can't passmode.including(...); - opt-in only, for now.
#2585 is a reminder that a code-generating rewrite on by default can hurt unrelated graphs; the caps and the BLAS/LAPACK requirement are meant to prevent that, but the default is your call.
-
Size limits. Are fixed caps (8×8, 5,000 lines) acceptable? The table above shows the trade-off; raising them to 10 or 12 is a one-line change if a cached-refit workflow makes the extra compile time worth it.
-
Anything you'd want tested beyond the above, e.g. specific dtypes,
fastmath, or benchmarks in the benchmark suite.
Known limitations
- Real dtypes only (boolean, integer, float32/float64); no complex.
- Only constant indices.
- No batched
Blockwise. - Fully unrolled, so only small sizes (8×8). Large-state models (e.g. seasonal components) are unchanged; see above.
- One block per graph: every supported node is merged, and if the result exceeds the line cap nothing is converted. Splitting into connected components around each BLAS/LAPACK call would be more robust; it doesn't matter for Kalman steps.
- Elementwise-only graphs are left to the existing fusion. A block might also help graphs whose elementwise chains are broken up by indexing or reductions, but I haven't measured that.
Disclosure
This was developed with an AI coding assistant (Claude): it wrote the code and ran the benchmarks, and I set the scope, the size caps and the split into PRs, and checked the results. The tests and measurements above all ran locally, and I can share the reproducer scripts. Because the change is large, I'm opening an issue first: the PR stack exists locally, and I'd only open it once you've said whether and how you'd want this in PyTensor. I'm happy to walk through any part of it, simplify it, or rework it to fit how you'd prefer this done.
Context
This came from comparing pymc-extras' statespace models with a specialised VAR library for a marketing-mix application. With this change, the Kalman-filter version is both the better model, since it handles measurement noise, and the faster one. A related one-line pymc-extras change (masking missing data with where instead of boolean indexing) keeps the filter step statically shaped so it can fuse. It would be proposed there separately.
Related:
- pymc-devs/pymc-extras#552: statespace models run through JAX because Numba Scan was "much worse", with the suggestion to "bench to see what's slowing down numba". The profiling above is that benchmark; blocks are the "optimizations done by hand inside the filter loop", done by a rewrite.
- #2310 (
ScalarizeRewriter), which this builds on, and #2585, where that rewrite exhausted memory on a large scalar graph. That is why the caps here are hard limits, checked before anything is compiled. - #301 and #1632: Scans of scalar or elementwise work lowered as plain loops, and Numba Scan benchmarked against hand-written loops.
- #2649, #2608: the broader question of which abstraction level such graphs should live at without losing the final lowered form.
- Lingua principale
- Python
- Stelle
- 654
- Fork
- 258
- Merge medio
- 2g 7h
- PR unite (30g)
- 39
Preparare l'ambiente
- Nessun Dockerfile né file Docker Compose
- Ha un modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di pymc-devs/pytensor
-
Docs of mode still mentions C/CVM as the default with FAST_RUNForse già presa @ADITYASINGH1206 l’ha presa 8 giorni fa. Apertadocs
Difficoltà 2/5 1-3 ore Idoneità per principianti 62/100
pymc-devs/pytensor#2641 · 1 commento ·
I maintainer di solito rispondono entro 1 giorno
-
docs
Difficoltà 2/5 1-3 ore Idoneità per principianti 62/100
I maintainer di solito rispondono entro 1 giorno
-
BUG: geomspace returns wrong sign for the endpoints when start and stop are negativeForse già presa @mayuriphad l’ha presa 27 giorni fa. Aperta
Difficoltà 2/5 Meno di un'ora Idoneità per principianti 85/100
I maintainer di solito rispondono entro 1 giorno
-
Reciprocal.impl computes np.float32(1.0) / x: float32 precision for float64 scalars under NEP 50 (Python linker)Forse di nuovo libera Una pull request per questa issue è stata chiusa senza essere unita. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 70/100
pymc-devs/pytensor#2430 · 1 commento ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
pymc-devs/pytensor#2428 · 5 commenti ·
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di pymc-devs/pytensor
Issue simili
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 62/100
I maintainer di solito rispondono entro 1 giorno
-
enhancement
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
dgunning/edgartools#2019 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 62/100
topoteretes/cognee#6818 · 1 commento ·
I maintainer di solito rispondono entro 1 giorno
-
source_verification_agent: no outcome when the publisher confirms a work but its DOI resolves to a different recordForse già presa @pinjun99 l’ha presa oggi. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
Imbad0202/academic-research-skills#1159 · 1 commento ·
I maintainer di solito rispondono entro 1 giorno
-
[Bug]: DoubleMLData.from_arrays checks the treatment d with force_all_x_finite instead of force_all_d_finiteForse già presa @leninworld l’ha presa oggi. Aperta
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 88/100
DoubleML/doubleml-for-py#471 ·
I maintainer di solito rispondono entro 1 giorno