StaticArrays forces recompilation of JLLs on Windows with Julia 1.8.1

Eric Davies, @longemen3000, I and others encountered an unexpected result after looking at @time_imports and discussed it on Slack. Something was forcing JLL packages to recompile a lot of code. We narrowed it down to this minimum working example.

julia> @time_imports using StaticArrays, Rmath_jll
      5.4 ms  StaticArraysCore
    714.3 ms  StaticArrays
     44.7 ms  Preferences
      1.2 ms  JLLWrappers
    391.5 ms  Rmath_jll 89.76% compilation time (98% recompilation)

Normally, Rmath_jll only takes a few milliseconds to compile:

julia> @time_imports using Rmath_jll
     31.4 ms  Preferences
      0.5 ms  JLLWrappers
      3.7 ms  Rmath_jll 73.39% compilation time

The import times are still short if we use StaticArraysCore.jl instead of StaticArrays.jl:

julia> @time_imports using StaticArraysCore, Rmath_jll
      5.5 ms  StaticArraysCore
     31.1 ms  Preferences
      0.6 ms  JLLWrappers
      5.0 ms  Rmath_jll 77.12% compilation time

Here’s an extended example:

To investigate further we used SnoopCompile.jl:

# Setup analysis enviornment
using Pkg
Pkg.activate(; temp = true);
Pkg.add(["StaticArrays", "Rmath_jll", "SnoopCompileCore", "SnoopCompile"])

# Capture method cache invalidation
using SnoopCompileCore
tinf = @snoopr using StaticArrays, Rmath_jll;
using SnoopCompile

The invalidation results are as follows.

julia> length(uinvalidated(tinf))
807

julia> trees = invalidation_trees(tinf)
7-element Vector{SnoopCompile.MethodInvalidations}:
 inserting any(f::Function, a::StaticArray; dims) in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\mapreduce.jl:265 invalidated:
   backedges: 1: superseding any(f, itr) in Base at reduce.jl:1191 with MethodInstance for any(::typeof(ismissing), ::Any) (1 children)
              2: superseding any(f::Function, a::AbstractArray; dims) in Base at reducedim.jl:1004 with MethodInstance for any(::typeof(ismissing), ::AbstractArray) (1 children)

 inserting getproperty(::SOneTo{n}, s::Symbol) where n in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\SOneTo.jl:57 invalidated:
   backedges: 1: superseding getproperty(x, f::Symbol) in Base at Base.jl:38 with MethodInstance for getproperty(::AbstractUnitRange, ::Symbol) (3 children)

 inserting instantiate(B::Base.Broadcast.Broadcasted{StaticArraysCore.StaticArrayStyle{M}}) where M in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\broadcast.jl:30 invalidated:
   backedges: 1: superseding instantiate(bc::Base.Broadcast.Broadcasted{Style}) where Style in Base.Broadcast at broadcast.jl:279 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}}) in Base.Broadcast at broadcast.jl:288 with MethodInstance for Base.Broadcast.instantiate(::Base.Broadcast.Broadcasted{Style, Nothing, typeof(Base.wrap_string)} where Style<:Base.Broadcast.AbstractArrayStyle{0}) (4 children)

 inserting isassigned(a::StaticArray, i::Int64...) in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\abstractarray.jl:31 invalidated:
   backedges: 1: superseding isassigned(a::AbstractArray, i::Integer...) in Base at abstractarray.jl:563 with MethodInstance for isassigned(::AbstractMatrix, ::Int64, ::Int64) (4 children)
              2: superseding isassigned(a::AbstractArray, i::Integer...) in Base at abstractarray.jl:563 with MethodInstance for isassigned(::AbstractVecOrMat, ::Int64, ::Int64) (4 children)
   1 mt_cache

 inserting (::Base.var"#foldl##kw")(::Any, ::typeof(foldl), op::R, a::StaticArray) where R in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\mapreduce.jl:222 invalidated:
   backedges: 1: superseding (::Base.var"#foldl##kw")(::Any, ::typeof(foldl), op, itr) in Base at reduce.jl:185 with MethodInstance for (::Base.var"#foldl##kw")(::NamedTuple{(:init,), _A} where _A<:Tuple{IOContext}, ::typeof(foldl), ::Type{IOContext}, ::Any) (8 children)

 inserting convert(::Type{Array{T, N}}, sa::SizedArray{S, T, N, N, Array{T, N}}) where {S, T, N} in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\SizedArray.jl:88 invalidated:
   mt_backedges: 1: signature Tuple{typeof(convert), Type{Vector{Any}}, Any} triggered MethodInstance for setindex!(::Vector{Vector{Any}}, ::Any, ::Int64) (14 children)
   backedges: 1: superseding convert(::Type{T}, a::AbstractArray) where T<:Array in Base at array.jl:617 with MethodInstance for convert(::Type, ::AbstractArray) (1 children)
   23 mt_cache

 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 in StaticArrays at C:\Users\mkitti\.julia\packages\StaticArrays\NOLon\src\abstractarray.jl:156 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{Union{Int64, Symbol}, _A}} where _A, Any} triggered MethodInstance for Base._array_for(::Type{Union{Int64, Symbol}}, ::Base.HasShape, ::Any) (0 children)
                  3: signature Tuple{typeof(similar), Type{BitArray}, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{BitArray}, ::Union{Integer, AbstractUnitRange}) (0 children)
                  4: signature Tuple{typeof(similar), Type{BitArray}, Any} triggered MethodInstance for similar(::Base.Broadcast.Broadcasted{Base.Broadcast.DefaultArrayStyle{1}, _A, typeof(parse)} where _A, ::Type{Bool}, ::Any) (0 children)
                  5: 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)
                  6: signature Tuple{typeof(similar), Type{Array{Any, _A}} where _A, Any} triggered MethodInstance for Base._array_for(::Type{Any}, ::Base.HasShape, ::Any) (0 children)
                  7: 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)
                  8: signature Tuple{typeof(similar), Type{Array{Base.PkgId, _A}} where _A, Any} triggered MethodInstance for Base._array_for(::Type{Base.PkgId}, ::Base.HasShape, ::Any) (0 children)
                  9: 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 (9 children)
                 10: 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 (9 children)
                 11: 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 (10 children)
                 12: signature Tuple{typeof(similar), Type{BitArray}, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{BitArray}, ::Tuple{Union{Integer, Base.OneTo}}) (1250 children)
   3 mt_cache

In case, it gets lost I would like to highlight that last signature that has 1250 children:

                 12: signature Tuple{typeof(similar), Type{BitArray}, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{BitArray}, ::Tuple{Union{Integer, Base.OneTo}}) (1250 children)

This issue was recently discussed by @ChrisRackauckas in his recent blog post involving package splitting. This also drove the creation of StaticArraysCore.jl by @oschulz and @mateuszbaran.

While using StaticArraysCore.jl in most packages seems like a temporary solution, the larger issue seems to be that StaticArrays.jl is able to invalidate so much.

I tried further analysis but got lost in the large tree.

julia> method_invalidations = trees[end];

julia> root = method_invalidations.mt_backedges[end].second
MethodInstance for similar(::Type{BitArray}, ::Tuple{Union{Integer, Base.OneTo}}) at depth 0 with 1250 children

julia> ascend(root)

@tim.holy Is there a way to contain the invalidations?

5 Likes

Without any intervention we start with the following situation.


julia> @time_imports using FFTW_jll
    257.5 ms  Preferences
      1.3 ms  JLLWrappers
     12.7 ms  FFTW_jll 62.41% compilation time

julia> @time_imports using StaticArrays
      4.8 ms  StaticArraysCore
    726.8 ms  StaticArrays

julia> @time_imports using Rmath_jll
    360.9 ms  Rmath_jll 99.71% compilation time (100% recompilation)

If we define a few more methods for signature, then this changes:

julia> import Base: similar, DimOrInd, to_shape, OneTo
       similar(::Type{T}, shape::Tuple{Union{Integer, OneTo}, Vararg{Union{Integer, OneTo}}}) where {T<:BitArray} = similar(T, to_shape(shape))
       similar(::Type{T}, shape::Dims) where T <: BitArray = T(undef, to_shape(shape))
       similar(BitArray, (Base.OneTo(5),))
       similar(BitArray, (5,))
       similar(BitVector, (Base.OneTo(5),))
       similar(BitArray, (5,))
5-element BitVector:
 0
 0
 0
 0
 0

julia> @time_imports using FFTW_jll
     29.6 ms  Preferences
      1.3 ms  JLLWrappers
    331.1 ms  FFTW_jll 99.17% compilation time (99% recompilation)

julia> @time_imports using StaticArrays
      5.3 ms  StaticArraysCore
    683.3 ms  StaticArrays

julia> @time_imports using Rmath_jll
      1.3 ms  Rmath_jll

After some further analysis using SnoopCompile.@snoopi_deep to determine precompilation statements, it appears we can prevent StaticArrays from forcing recompilation of JLLs.

julia> import Base: similar, DimOrInd, to_shape, OneTo, require
       import Artifacts: _artifact_str, SHA1, Platform
       similar(::Type{T}, shape::Tuple{Union{Integer, OneTo}, Vararg{Union{Integer, OneTo}}}) where {T<:BitArray} = similar(T, to_shape(shape))
       similar(::Type{T}, shape::Dims) where T <: BitArray = T(undef, to_shape(shape))
       Base.precompile(Tuple{typeof(_artifact_str),Module,String,SubString{String},String,Dict{String, Any},SHA1,Platform,Any})
       Base.precompile(Tuple{typeof(require),Module,Symbol})
true

julia> @time_imports using FFTW_jll
     40.0 ms  Preferences
      0.5 ms  JLLWrappers
      4.6 ms  FFTW_jll 59.18% compilation time

julia> @time_imports using StaticArrays
      5.2 ms  StaticArraysCore
    678.5 ms  StaticArrays

julia> @time_imports using Rmath_jll
      1.3 ms  Rmath_jll
1 Like

the first two are apt to a PR to julia, but, the last one seems weird?

I’m guessing that the precompile statements would be superfluous due to how the system image is normally created.

Can you clarify which Julia version you’re using for these investigations? I’m not finding one that shows lots of similar invalidations.

This should be Julia 1.8.0.

Admittedly, the issue does not seem to occur on master.

julia> versioninfo()
Julia Version 1.9.0-DEV.1433
Commit e6d99792e6* (2022-09-24 14:32 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD FX(tm)-8350 Eight-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, bdver1)
  Threads: 1 on 8 virtual cores
Environment:
  JULIA_CPU_TARGET = generic;native

julia> @time_imports using StaticArrays, Rmath_jll
      1.6 ms  Statistics
      6.7 ms  StaticArraysCore
   1066.4 ms  StaticArrays
     39.1 ms  Preferences
      0.5 ms  JLLWrappers
      6.8 ms  Rmath_jll 65.79% compilation time

The issue actually only seems to occur on Windows!

Windows Julia 1.8.1

Here it is with Julia 1.8.1 on Windows

julia> @time_imports using FFTW_jll, StaticArrays, Rmath_jll
     37.7 ms  Preferences
      1.1 ms  JLLWrappers
     13.9 ms  FFTW_jll 53.87% compilation time
      3.4 ms  StaticArraysCore
    688.9 ms  StaticArrays
    305.6 ms  Rmath_jll 99.63% compilation time (100% recompilation)

julia> versioninfo()
Julia Version 1.8.1
Commit afb6c60d69 (2022-09-06 15:09 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 48 × Intel(R) Xeon(R) Gold 5220R CPU @ 2.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, cascadelake)
  Threads: 1 on 96 virtual cores

Linux Julia 1.8.1

On Linux with Julia 1.8.1:

julia> @time_imports using FFTW_jll, StaticArrays, Rmath_jll
     73.7 ms  Preferences
      0.5 ms  JLLWrappers
      4.1 ms  FFTW_jll 71.85% compilation time
      4.0 ms  StaticArraysCore
   1065.9 ms  StaticArrays
      0.5 ms  Rmath_jll

julia> versioninfo()
Julia Version 1.8.1
Commit afb6c60d69a (2022-09-06 15:09 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD FX(tm)-8350 Eight-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, bdver1)
  Threads: 1 on 8 virtual cores
1 Like

On the Julia nightly, everything seems fine.

Windows Julia 1.9.0-DEV.1433

julia> @time_imports using FFTW_jll, StaticArrays, Rmath_jll
     64.8 ms  Preferences
      0.5 ms  JLLWrappers
      5.7 ms  FFTW_jll 61.81% compilation time
      1.0 ms  Statistics
      3.7 ms  StaticArraysCore
    721.1 ms  StaticArrays
      2.3 ms  Rmath_jll

julia> versioninfo()
Julia Version 1.9.0-DEV.1433
Commit e6d99792e6 (2022-09-24 14:32 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 48 × Intel(R) Xeon(R) Gold 5220R CPU @ 2.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, cascadelake)
  Threads: 1 on 96 virtual cores

Linux 1.9.0-DEV.1433

julia> @time_imports using FFTW_jll, StaticArrays, Rmath_jll
     80.4 ms  Preferences
      0.5 ms  JLLWrappers
      5.3 ms  FFTW_jll 79.68% compilation time
      1.0 ms  Statistics
      3.9 ms  StaticArraysCore
   1056.1 ms  StaticArrays
      0.5 ms  Rmath_jll

julia> versioninfo()
Julia Version 1.9.0-DEV.1433
Commit e6d99792e6* (2022-09-24 14:32 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD FX(tm)-8350 Eight-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, bdver1)
  Threads: 1 on 8 virtual cores
1 Like

It might be the invoke issue. invoke is not used in very much code, but because invalidation affects all callees, a single point of failure can lead to the fall of an entire tree. And since Julia 1.8 is much better than previous versions about “growing trees” (i.e., caching and linking precompiled code to its callers and callees), an unfortunate side-effect is that because we now have much taller trees than in previous versions, some that would not previously have collapsed now hit this invoke issue and collapse.

Unfortunately, the proper fix for the invoke issue is pretty complicated: it involves changes to our representation of call graphs and ends up touching a lot of code spanning both the Julia and C sides of the compiler. We’re still discovering more “interesting” implications to handling invoke properly (I’m working on yet another corner case now…), so it’s not currently a good candidate for backporting. The answer will most likely be to simply wait for 1.9.

2 Likes

I’m also now tracking down some invalidations coming from CategoricalArrays that I found when using Gadfly:

What has me a bit concerned is that some of these methods in Base seem easy to accidentally invalidate.

Now that we’re getting better at precompilation, more and more people seem to be noticing the significance of invalidations. And wait until it’s possible to cache native code: say Makie’s TTFP gets down to 0.5s, unless you load certain other packages, in which case it goes back to being 50s. Suddenly invalidations become concern #1 for basically anyone who uses Julia. They’ve been a significant concern for me since we started working on what became Julia 1.6, but now the issue is much more visible.

My guess is that if anything forces Julia 2.0, robustness to invalidation may be the most likely candidate. We may have to impose some rules about constructors at the very least (Require constructors and `convert` to return objects of stated type? · Issue #42372 · JuliaLang/julia · GitHub), and possibly more generally as well. There’s a proposal to allow one to declare that certain functions must return certain types, and we could add an optional feature that would allow packages to adopt it, but we can’t impose that on any Base functions without going to Julia 2.0.

16 Likes