search

JuliaLinearAlgebra / LinearMaps.jl

A Julia package for defining and working with linear maps, also known as linear transformations or linear operators acting on vectors. The only requirement for a LinearMap is that it can act on a vector (by multiplication) efficiently.
Other
303 stars 42 forks source link

Further reducing load time? #207

Closed oschulz closed 1 year ago

oschulz commented 1 year ago

I recently created a very lightweight LinearMap-like type MatrixLikeOperator for AutoDiffOperators.jl. AutoDiffOperators supports LinearMaps as an extension (and that's what I'll use in most "serious" use cases), but I wanted to keep load-time down and have a lightweight simple default linear map type.

While optimizing load time I noticed that many method invalidations originated from using LinearAlgebra.Adjoint{<:MatrixLikeOperator} to represent and dispatch on adjoints of the maps. So I added a custom adjoint type (like LinearMaps) and use a two-stage dispatch for * and mul!. In the end the load time went from over 30 ms down to 10 ms.

LinearMaps is probably pretty optimized already, but I wonder I we can bring load time down a bit more still, based on that? In the end, the number of * and mul! invalidations should be constant if we re-route to internal versions for different map types. Though LinearMaps does support a 5-arg mul! and my lightweight maps only do 3-arg mul! - not sure ...

dkarrasch commented 1 year ago

Hi @oschulz! What you describe is exactly the state of LinearMaps.jl. We do have very few * methods, which call mul!, which checks for compatible sizes and then dispatches to _unsafe_mul! for the different map types. Adjoints and transposes have their own LinearMap-wrapper type, so they don't interfere with AbstractMatrix. I can do some profiling, but from what I heard the only potential load time issues arise from our slightly weird diagonal concatenation functions:

https://github.com/JuliaLinearAlgebra/LinearMaps.jl/blob/f522a8f8b4f050f90639f8ab68344259ee392963/src/blockmap.jl#L500-L525

One proposal was to remove them and instead export a proper constructor. But that would be breaking, and I'm currently hesitant, though not completely against it.

I'll report back when I have some profiling results.

dkarrasch commented 1 year ago

It turns out the package load time is mostly dominated by SparseArrays.jl. There are some changes in SparseArrays.jl in the pipeline that will reduce its package load time significantly, but it's still factor 10 slower than LinearMaps.jl on its own. Given that SparseArrays.jl will be no longer in the sysimage in v1.10, I think it might be fair to make SparseArrays.jl an optional dependency (I forgot the official terminology), as you did with the differentiation stuff. After that, we can check how "bad" the above quoted diagonal concatenation methods are.

oschulz commented 1 year ago

Thanks @dkarrasch ! Then we're probably at the limit of what can be done load-time wise at the moment - but then, current load time isn't so bad at all :-).

oschulz commented 1 year ago

One proposal was to remove them and instead export a proper constructor. But that would be breaking, and I'm currently hesitant, though not completely against it.

Might be nice, longer term.

oschulz commented 1 year ago

Off topic, what's your current view of making LinearOperator LinearMap an AbstractArray, now that we have getindex? With my simple MatrixLikeOperator subtying AbstractArray didn't seem to introduce too many method invalidations.

JeffFessler commented 1 year ago

What do you mean by LinearOperator here? I don't see that type in this package. BTW, You asked before about AbstractMatrix in #180.

oschulz commented 1 year ago

What do you mean by LinearOperator here? I don't see that type in this package.

Sorry, my mistake - I meant LinearMap. :-)

BTW, You asked before about AbstractMatrix in #180.

I know - sorry should have posted that part there, was just wondering what @dkarrasch 's take on it was. But you're right, I think the discussion was converging more in the direction of an AbstractLinearMap supertype.