Numba: compile small, statically shaped linear algebra (e.g. Scan steps) into one kernel

Abierto
#2,670 4 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
5/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
python
Área
compilers

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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, _cholesky and 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. ScalarizedBlock is a FinalizedOpFromGraph wrapping a small, statically shaped subgraph. Backends other than Numba evaluate it as a regular OpFromGraph.
  • 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 / 0 gives 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 OpFromGraph lowering, 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 and Composites;
  • DimShuffle, sum/product reductions;
  • Dot, unbatched Blockwise;
  • 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:

  1. Numba: don't wrap inline kernels for caching (+35). numba_funcify_ensure_cache wraps cached kernels as f(*args). Numba can't inline through that, so an Op kernel jitted with inline="always" fails to compile with the cache on. This PR is independent of the rest.
  2. ScalarizedBlock op and Numba lowering (+567, 372 of them code): elementwise (including comparisons and boolean logic), DimShuffle, reductions, Dot, Blockwise. Nothing creates blocks yet.
  3. scalarize_blocks rewrite, opt-in (mode.including("scalarize_blocks"), +245/−2).
  4. Cholesky and solves (+154/−2).
  5. Construction and constant-index indexing (+164/−1). The gradient step needs these.
  6. 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/Dot nodes 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.
  7. 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

  1. Do you want this in PyTensor? If yes, is a separate generator (as here) right, or should it be an extension of #2310's ScalarizeRewriter to small arrays?

  2. 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 pass mode.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.

  3. 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.

  4. 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.
Lenguaje dominante
Python
Estrellas
654
Forks
258
Merge medio
3 d 41 min
PR fusionados (30 d)
42

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de pymc-devs/pytensor

Todos los issues de pymc-devs/pytensor

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.