LinearAlgebra excision from sysimg.

[vchuravy]

I was thinking about JuliaLang/julia#51432 this morning and I was curious how bad it would be for LinearAlgebra.

Using:

import LinearAlgebra

function allinbase(T)
    T = Base.unwrap_unionall(T)
    if T isa Union
        return allinbase(T.a) && allinbase(T.b)
    end
    return T.name.module == Base || T.name.module == Core
end

for name in names(Base)
    obj = getglobal(Base, name)
    if obj isa Function
        candidates = methods(obj, LinearAlgebra)
        for candidate in candidates
            sig = Base.tuple_type_tail(candidate.sig)
            allInBase = true
            while sig !== Tuple{}
                T = Base.tuple_type_head(sig)
                sig = Base.tuple_type_tail(sig)
                allInBase &= allinbase(T)
                allInBase || break 
            end
            if allInBase
                println(candidate)
            end
        end
    end
end

In 1.10-beta.2 we have the following candidates:

adjoint(B::Union{BitMatrix, BitVector}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:237
adjoint(a::AbstractArray) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/transpose.jl:3
*(A::AbstractMatrix, B::AbstractMatrix, C::AbstractMatrix, D::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:1229
*(A::AbstractMatrix, B::AbstractMatrix, C::AbstractMatrix, x::AbstractVector) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:1221
*(A::AbstractMatrix, B::AbstractMatrix, x::AbstractVector) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:1144
*(A::AbstractMatrix, B::AbstractMatrix, C::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:1160
*(a::AbstractVector, B::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:63
*(A::AbstractMatrix{T}, x::AbstractVector{S}) where {T, S} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:55
*(A::AbstractMatrix, B::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/matmul.jl:104
\(a::AbstractVector, b::AbstractArray) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/generic.jl:1129
^(::Irrational{:ℯ}, A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:645
acos(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1135
acosh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1215
acot(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1289
acoth(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1292
acsc(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1289
acsch(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1292
adjoint(B::Union{BitMatrix, BitVector}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:237
adjoint(a::AbstractArray) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/transpose.jl:3
asec(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1289
asech(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1292
asin(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1166
asinh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1234
atan(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1197
atanh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1252
cis(A::AbstractMatrix{<:Union{Float32, Float64, Int16, Int32, Int64, Int8, UInt16, UInt32, UInt64, UInt8, Complex{<:Union{Float32, Float64, Int16, Int32, Int64, Int8, UInt16, UInt32, UInt64, UInt8}}, Rational{<:Union{Float32, Float64, Int16, Int32, Int64, Int8, UInt16, UInt32, UInt64, UInt8}}}}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:616
cis(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:615
convert(::Type{T}, A::AbstractMatrix) where T<:Diagonal @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/diagonal.jl:100
convert(::Type{T}, m::AbstractMatrix) where T<:Bidiagonal @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bidiag.jl:220
copyto!(dest::Array{T}, rdest::AbstractRange{Ti}, src::Array{T}, rsrc::AbstractRange{Ti}) where {T<:Union{Float32, Float64, ComplexF64, ComplexF32}, Ti<:Integer} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/blas.jl:2121
cos(A::AbstractMatrix{<:Complex}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:946
cos(A::AbstractMatrix{<:Real}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:939
cosh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1072
cot(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1272
coth(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1277
csc(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1272
csch(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1277
eltype(::Type{<:LinearAlgebra.AbstractQ{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/abstractq.jl:10
eltype(::Type{<:LinearAlgebra.Factorization{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/factorization.jl:40
eltype(::Type{LinearAlgebra.UniformScaling{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/uniformscaling.jl:86
exp(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:594
inv(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/generic.jl:1048
isapprox(x::AbstractArray, y::AbstractArray; atol, rtol, nans, norm) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/generic.jl:1785
isone(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:16
kron(a::BitMatrix, b::BitMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:131
kron(a::BitVector, b::BitVector) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:107
kron(a::AbstractVector{T}, b::AbstractVector{S}) where {T, S} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:469
kron!(R::BitMatrix, a::BitMatrix, b::BitMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:114
kron!(R::BitVector, a::BitVector, b::BitVector) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:95
kron!(c::AbstractVector, a::AbstractVector, b::AbstractVector) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:370
log(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:798
one(::Type{LinearAlgebra.UniformScaling{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/uniformscaling.jl:130
oneunit(::Type{LinearAlgebra.UniformScaling{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/uniformscaling.jl:132
promote_rule(::Type{Matrix{T}}, ::Type{<:LinearAlgebra.Bidiagonal{S, V} where V<:AbstractVector{S}}) where {T, S} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bidiag.jl:202
promote_rule(::Type{<:AbstractMatrix{T}}, ::Type{<:LinearAlgebra.AbstractQ{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/abstractq.jl:21
promote_rule(A::Type{<:LinearAlgebra.Diagonal{<:Any, V}}, B::Type{<:LinearAlgebra.Diagonal{<:Any, W}}) where {V, W} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/diagonal.jl:17
promote_rule(::Type{<:LinearAlgebra.Tridiagonal}, ::Type{<:LinearAlgebra.Bidiagonal}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bidiag.jl:215
promote_rule(::Type{<:LinearAlgebra.Tridiagonal{T, V} where V<:AbstractVector{T}}, ::Type{<:LinearAlgebra.Bidiagonal{S, V} where V<:AbstractVector{S}}) where {T, S} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bidiag.jl:213
sec(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1272
sech(A::AbstractMatrix{T}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1277
sin(A::AbstractMatrix{<:Complex}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:979
sin(A::AbstractMatrix{<:Real}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:972
sincos(A::AbstractMatrix{<:Real}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1013
sincos(A::AbstractMatrix{<:Complex}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1024
sinh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1086
sqrt(A::AbstractMatrix{T}) where T<:Union{Real, Complex} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:877
tan(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1058
tanh(A::AbstractMatrix) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:1100
transpose(B::Union{BitMatrix, BitVector}) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/bitarray.jl:238
transpose(a::AbstractArray) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/transpose.jl:4
zero(::Type{LinearAlgebra.UniformScaling{T}}) where T @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/uniformscaling.jl:134
sqrt(A::AbstractMatrix{T}) where T<:Union{Real, Complex} @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/dense.jl:877
isapprox(x::AbstractArray, y::AbstractArray; atol, rtol, nans, norm) @ LinearAlgebra ~/.julia/juliaup/julia-1.10.0-beta2+0.x64.linux.gnu/share/julia/stdlib/v1.10/LinearAlgebra/src/generic.jl:1785

This is surprisingly managable and even include's some false-positives. E.g. promote_rule/convert.

[ViralBShah]

How likely are we to be able to pull this off in 1.13?

[vchuravy]

It needs someone to take ownership of this and drive it forwards. I am sadly unable to commit to that currently.

My last attempt was JuliaLang/julia#51432 which has the same problem, but on a smaller API surface, the way it solves the piracy issue is by doing a lazy delayed loading strategy, which no one really likes.

More importantly would be to actually unlock the promise of upgradeable standard libraries, instead of just performing excision. Excision on its own only has limited benefits

[MilesCranmer]

For whoever decides to take this on:

What about splitting it up into LinearAlgebraBase.jl that gets included in the sysimage and an excised LinearAlgebra.jl for everything else? And put everything that relies on piracy or otherwise cannot be split up in the Base version, while non essential stuff (e.g., UpperHessenberg, ...) can be moved out of the sysimage.

[ViralBShah]

@KristofferC was suggesting somewhere that the savings may not be as substantial as we may think. My thought was we basically need the relevant methods and their underlying BLAS and LAPACK methods for *, \ and / in the system image (probably a dozen ccalls), which can actually be even moved out into LinearAlgebraBase. The rest of all the different matrix types and factorizations etc. can live outside the system image.

That would make it easier to land larger PRs like low-level BLAS and LAPACK wrappers which several folks are requesting: #1403

[ViralBShah]

Doesn't feel too bad: JuliaLang/julia#59855