JuliaArrays / JuliaArrays/StaticArrays.jl

Invalidation and load time

Open
#1,074 11 comments 3 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Julia
Stars
844
Forks
159
Avg merge
3d 21h
Merged PRs (30d)
3

Description

On julia nightly

julia> @time using StaticArrays
  1.160173 seconds (1.95 M allocations: 142.974 MiB, 34.39% compilation time)
julia> using SnoopCompileCore

julia> invalidations = @snoopr using StaticArrays;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations)
13-element Vector{SnoopCompile.MethodInvalidations}:
 inserting rdims(out::Val{N}, inds::Tuple{SOneTo, Vararg{SOneTo}}) where N @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/abstractarray.jl:209 invalidated:
   mt_backedges: 1: signature Tuple{typeof(Base.rdims), Val{1}, Any} triggered MethodInstance for reshape(::BitArray, ::Val{1}) (0 children)

 inserting to_indices(A, I::Tuple{Vararg{Union{Integer, CartesianIndex, StaticArray{<:Tuple, Int64}}}}) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/indexing.jl:218 invalidated:
   backedges: 1: superseding to_indices(A, I::Tuple) @ Base indices.jl:344 with MethodInstance for to_indices(::AbstractArray, ::Tuple{Any, CartesianIndex{0}}) (1 children)
   36 mt_cache

 inserting getproperty(::SOneTo{n}, s::Symbol) where n @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/SOneTo.jl:57 invalidated:
   backedges: 1: superseding getproperty(x, f::Symbol) @ Base Base.jl:37 with MethodInstance for getproperty(::AbstractUnitRange, ::Symbol) (1 children)

 inserting (::Type{SSC})(a::AbstractVector) where SSC<:SHermitianCompact @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/SHermitianCompact.jl:83 invalidated:
   backedges: 1: superseding Union{}(a...) @ Core boot.jl:263 with MethodInstance for Union{}(::BitArray) (1 children)

 inserting rdims(out::Tuple{Any}, inds::Tuple{SOneTo, Vararg{SOneTo}}) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/abstractarray.jl:210 invalidated:
   backedges: 1: superseding rdims(out::Tuple{Any}, inds::Tuple{Any}) @ Base reshapedarray.jl:156 with MethodInstance for Base.rdims(::Tuple{Base.OneTo{Int64}}, ::Tuple{Any}) (1 children)
              2: superseding rdims(out::Tuple{Any}, inds::Tuple{Vararg{Any, M}}) where M @ Base reshapedarray.jl:157 with MethodInstance for Base.rdims(::Tuple{Base.OneTo{Int64}}, ::Tuple) (2 children)

 inserting instantiate(B::Base.Broadcast.Broadcasted{StaticArrays.StaticArrayStyle{M}}) where M @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/broadcast.jl:33 invalidated:
   backedges: 1: superseding instantiate(bc::Base.Broadcast.Broadcasted{Style}) where Style @ Base.Broadcast broadcast.jl:292 with MethodInstance for Base.Broadcast.instantiate(::Base.Broadcast.Broadcasted{Style, Nothing, typeof(Base.wrap_string)} where Style<:Union{Nothing, Base.Broadcast.BroadcastStyle}) (1 children)
              2: superseding instantiate(bc::Base.Broadcast.Broadcasted{<:Base.Broadcast.AbstractArrayStyle{0}}) @ Base.Broadcast broadcast.jl:301 with MethodInstance for Base.Broadcast.instantiate(::Base.Broadcast.Broadcasted{Style, Nothing, typeof(Base.wrap_string)} where Style<:Base.Broadcast.AbstractArrayStyle{0}) (4 children)
   1 mt_cache

 inserting _axes(bc::Base.Broadcast.Broadcasted{<:StaticArrays.StaticArrayStyle}, ::Nothing) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/broadcast.jl:30 invalidated:
   backedges: 1: superseding _axes(bc::Base.Broadcast.Broadcasted, ::Nothing) @ Base.Broadcast broadcast.jl:224 with MethodInstance for Base.Broadcast._axes(::Base.Broadcast.Broadcasted, ::Nothing) (1 children)
              2: superseding _axes(bc::Base.Broadcast.Broadcasted{<:Base.Broadcast.AbstractArrayStyle{0}}, ::Nothing) @ Base.Broadcast broadcast.jl:225 with MethodInstance for Base.Broadcast._axes(::Base.Broadcast.Broadcasted{<:Base.Broadcast.AbstractArrayStyle{0}}, ::Nothing) (4 children)

 inserting SubArray(A::AbstractArray, indices::Tuple{StaticArrays.StaticIndexing, Vararg{StaticArrays.StaticIndexing}}) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/indexing.jl:379 invalidated:
   mt_backedges: 1: signature Tuple{Type{SubArray}, Any, Any} triggered MethodInstance for Base._maybe_reindex(::SubArray, ::Tuple{Base.LogicalIndex{Int64, A} where A<:(BitArray)}, ::Tuple{}) (4 children)
   backedges: 1: superseding SubArray(parent::AbstractArray, indices::Tuple) @ Base subarray.jl:26 with MethodInstance for SubArray(::AbstractArray, ::Tuple) (1 children)

 inserting similar(::Type{A}, shape::Union{Tuple{SOneTo, Vararg{Union{Integer, Base.OneTo, SOneTo}}}, Tuple{Union{Integer, Base.OneTo}, SOneTo, Vararg{Union{Integer, Base.OneTo, SOneTo}}}, Tuple{Union{Integer, Base.OneTo}, Union{Integer, Base.OneTo}, SOneTo, Vararg{Union{Integer, Base.OneTo, SOneTo}}}}) where A<:AbstractArray @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/abstractarray.jl:178 invalidated:
   mt_backedges: 1: signature Tuple{typeof(similar), Type{Array{Union{Int64, Symbol}, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Union{Int64, Symbol}, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
                 2: signature Tuple{typeof(similar), Type{Array{Any, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Any, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
                 3: signature Tuple{typeof(similar), Type{Array{Base.PkgId, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Base.PkgId, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
                 4: signature Tuple{typeof(similar), Type{Array{Union{Int64, Symbol}, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Union{Int64, Symbol}, _A}}, ::Tuple{Union{Integer, Base.OneTo}}) where _A (2 children)
                 5: signature Tuple{typeof(similar), Type{Array{Any, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Any, _A}}, ::Tuple{Union{Integer, Base.OneTo}}) where _A (2 children)
                 6: signature Tuple{typeof(similar), Type{Array{Base.PkgId, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Base.PkgId, _A}}, ::Tuple{Union{Integer, Base.OneTo}}) where _A (2 children)

 inserting unsafe_view(A::AbstractArray, i1::StaticArrays.StaticIndexing, indices::StaticArrays.StaticIndexing...) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/indexing.jl:370 invalidated:
   mt_backedges: 1: signature Tuple{typeof(Base.unsafe_view), Vector{Pair{DataType, Function}}, Vararg{Any}} triggered MethodInstance for view(::Vector{Pair{DataType, Function}}, ::Any) (0 children)
                 2: signature Tuple{typeof(Base.unsafe_view), Vector{UInt8}, Vararg{Any}} triggered MethodInstance for view(::Vector{UInt8}, ::Any) (0 children)
                 3: signature Tuple{typeof(Base.unsafe_view), Vector{Base.PkgId}, Vararg{Any}} triggered MethodInstance for view(::Vector{Base.PkgId}, ::Any) (0 children)
                 4: signature Tuple{typeof(Base.unsafe_view), BitArray, Vararg{Any}} triggered MethodInstance for view(::BitArray, ::BitArray) (9 children)

 inserting isassigned(a::StaticArray, i::Int64...) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/abstractarray.jl:31 invalidated:
   backedges: 1: superseding isassigned(a::AbstractArray, i::Integer...) @ Base abstractarray.jl:577 with MethodInstance for isassigned(::AbstractMatrix, ::Int64, ::Int64) (4 children)
              2: superseding isassigned(a::AbstractArray, i::Integer...) @ Base abstractarray.jl:577 with MethodInstance for isassigned(::AbstractVecOrMat, ::Int64, ::Int64) (12 children)

 inserting eachindex(::IndexLinear, a::StaticArray) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/abstractarray.jl:19 invalidated:
   backedges: 1: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Union{Missing, Float16}}) (2 children)
              2: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Union{Missing, Float32}}) (2 children)
              3: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Union{Missing, Float64}}) (2 children)
              4: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Missing}) (2 children)
              5: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Float16}) (2 children)
              6: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Float32}) (2 children)
              7: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector{Float64}) (2 children)
              8: superseding eachindex(::IndexLinear, A::AbstractVector) @ Base abstractarray.jl:355 with MethodInstance for eachindex(::IndexLinear, ::AbstractVector) (2 children)

 inserting getindex(sa::Type{SA}, xs...) @ StaticArrays ~/Dropbox/JuliaPackages/StaticArrays.jl/src/initializers.jl:31 invalidated:
   backedges: 1: superseding getindex(::Type{T}, vals...) where T @ Base array.jl:399 with MethodInstance for getindex(::Type, ::Nothing, ::Vararg{String}) (119 children)

I'm not certain how easily these may be addressed, but the SA[1,2,3] constructor, which is the source of the most invalidation, is a bit unfortunate, as it doesn't follow the docstring:

    getindex(type[, elements...])

Construct a 1-d array of the specified type. This is usually called with the syntax
`Type[]`. Element values can be specified using `Type[a,b,c,...]`.

I wonder if this may be deprecated, as the macro version @SArray [1,2,3] seems essentially identical?

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the Julia nightly load-time measurement with SnoopCompile using @snoopr using StaticArrays and invalidation_trees. Read the reported entry points in src/initializers.jl, src/abstractarray.jl, src/indexing.jl, src/broadcast.jl, src/SOneTo.jl, and src/SHermitianCompact.jl, focusing on the SA[1,2,3] constructor and its documented behavior. Done means the invalidation and load-time impact is characterized and an agreed API or implementation direction is documented.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.