You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
perf: linalg SVD, Pinv, Lstsq, Eigh, QR, Eig allocate 90-276 times per 64x64 call #104
The linalg decompositions allocate hundreds of times per call on a 64 x 64 matrix, where LAPACK through NumPy allocates a handful of workspaces. The count grows with the matrix side, so the cost is per column or per row, not per call.
Witness (allocation counts, exact under any load; clone at c7b9263, bench/ of the W3 refbench PR)
go test -run TestPerf -perf.record -cpu 1 (GOMAXPROCS=1), 64 x 64 float64:
row
allocs per call
linalg.Lstsq / LstsqRcond (64 x 8 right-hand side)
276
linalg.SVD (full_matrices=False)
265
linalg.Pinv / PinvRcond
255
linalg.Eigh
166
linalg.QR
93
linalg.Eig
89
for comparison: linalg.Det / Eigvals / Cholesky
25 / 25 / 20
Pinv and Lstsq rest on SVD (linalg/lstsq.go:35,146, linalg/svd.go:693), so the SVD path is the first place to look. The next measurement should repeat the table at 128 x 128 to confirm the count scales with the side (not run here: only the 64 x 64 counts are recorded).
To do
Find the per-column / per-row allocations in the SVD, Eigh, QR and Eig paths and hoist them out of the loops (one workspace per call).
Timing is deferred (1-minute load was 8 to 80 when this was filed); this issue is filed on the allocation witness alone.
Status after #116 (first step, merged), from a memory profile at 64×64 with GOMAXPROCS=1:
dcMerge (linalg/dc.go:44, used by Eigh through stedc) makes about 22 allocations per merge: qt, z, idx and its sort.SliceStable, ds/zs, the keep/defl appends, dk/zk, lam, delta, zhat, u, gath, out, vals, ord, res. At n = 64 with dcLeaf = 25 there are 3 merges, so about 66 of Eigh's 154 allocations.
bdMerge (linalg/bdc.go:78, used by SVD, Pinv and Lstsq through bdsdc) is the same shape, with about 12 buffers per merge.
The count is O(n / leaf) merges × a constant. Each merge does O(n²)–O(n³) work, so these allocations are a small share of the time.
A single bump arena per call is the wrong fix: summed over the recursion it needs about 12·n² floats (96 MB at n = 1024), where today the halves' buffers are freed as the recursion climbs. The fix that keeps peak memory where it is is LAPACK's: dstedc/dbdsdc take one workspace sized for the top merge and every level reuses it. That means each merge writes into caller-provided slices, a rewrite of both merge routines rather than a hoist.
Note for go-embedded-ruby/ruby#918: if linalg moves to a neutral library, this rewrite belongs there, so it should wait for the move.
Remaining smaller sites: newBlockReflector / applyLeft per panel, and wrap's copy through ndarray.FromSlice (a zero-copy constructor: #76).
Activity
perf(linalg): fewer allocations per factorization (first step of #104) (
tannevaled commentedon Nov 12, 2026
Status after #116 (first step, merged), from a memory profile at 64×64 with GOMAXPROCS=1:
dcMerge(linalg/dc.go:44, used by Eigh throughstedc) makes about 22 allocations per merge:qt,z,idxand itssort.SliceStable,ds/zs, thekeep/deflappends,dk/zk,lam,delta,zhat,u,gath,out,vals,ord,res. At n = 64 withdcLeaf= 25 there are 3 merges, so about 66 of Eigh's 154 allocations.bdMerge(linalg/bdc.go:78, used by SVD, Pinv and Lstsq throughbdsdc) is the same shape, with about 12 buffers per merge.A single bump arena per call is the wrong fix: summed over the recursion it needs about 12·n² floats (96 MB at n = 1024), where today the halves' buffers are freed as the recursion climbs. The fix that keeps peak memory where it is is LAPACK's: dstedc/dbdsdc take one workspace sized for the top merge and every level reuses it. That means each merge writes into caller-provided slices, a rewrite of both merge routines rather than a hoist.
Note for go-embedded-ruby/ruby#918: if linalg moves to a neutral library, this rewrite belongs there, so it should wait for the move.
Remaining smaller sites:
newBlockReflector/applyLeftper panel, andwrap's copy throughndarray.FromSlice(a zero-copy constructor: #76).