Closed devmotion closed 11 months ago
Can you use FillArrays.jl
to avoid the allocations?
That is, return a Cholesky(Diagonal(Fill(sqrt(sm.value), sm.dim)), :U, 0)
?
cholesky(::ScalMat)
should really be O(1) in runtime cost.
Since PDMats is used by so mamy packages, I wanted to avoid introducing new dependencies and thereby increasing loading and compilation times. But maybe we should add FillArrays at least - I'm already convinced that it should definitely become a weak dependency and I'm actually preparing a PR right now 😅
I think the compilation time increase would be fairly negligible, other than load times.
> julia -e '@time using FillArrays'
0.084586 seconds (114.33 k allocations: 7.589 MiB, 4.38% compilation time)
> julia -e '@time using PDMats'
0.023690 seconds (34.43 k allocations: 2.185 MiB)
> julia --startup=no -e '@time using PDMats, FillArrays'
0.100786 seconds (132.25 k allocations: 8.625 MiB, 3.80% compilation time)
FillArrays.jl only has stdlib dependencies, so it's a bit surprising that its load time is approaching 4x that of PDMats' on my computer.
This might be related to the fact that using PDMats
has 0 invalidations, while using FillArrays
results in many.
I couldn't find an open issue regarding the invalidations of FillArrays, maybe it would be worthwhile to open an issue and try to reduce them? Generally, I would feel much better about adding a FillArrays dependency if it would at most double the loading time.
Based on the timings in https://github.com/JuliaStats/PDMats.jl/pull/182/#issuecomment-1736061820, I think we shouldn't switch to FillArrays in this PR. The PR is already an improvement over the status quo, and we could track the remaining possible optimizations and discussion about FillArrays in a separate issue. What do you think @chriselrod?
All modified lines are covered by tests :white_check_mark:
Files | Coverage Δ | |
---|---|---|
src/pdiagmat.jl | 97.39% <100.00%> (ø) |
|
src/scalmat.jl | 97.33% <100.00%> (ø) |
:loudspeaker: Thoughts on this report? Let us know!.
We don't have to go through
cholesky(::Diagonal)
in LinearAlgebra (e.g. https://github.com/JuliaLang/julia/blob/28d9f730c1927297fc0cfc415c842968aa1a3a71/stdlib/LinearAlgebra/src/diagonal.jl#L868) when computingcholesky(::ScalMat)
orcholesky(::PDiagMat)
but we can construct theCholesky
object directly without any intermediate steps.This improves performance significantly:
master
Note also that
cholesky(::PDiagMat)
is faster thancholesky(::ScalMat)
due to the reduced number of allocations - the only difference between both code paths is that for theScalMat
the diagonalfill(a.value, a.dim)
is only constructed inside of thecholesky
call whereas it already exists for thePDiagMat
.This PR
Note that with this change, as expected,
cholesky(::ScalMat)
will be faster than the correspondingcholesky(::PDiagMat)
since it only requires a singlesqrt
computation.