Julia: Summary of non-ambiguous patterns of invalidation

[timholy]

I've looked at a enough cases, and developed enough tooling, to start getting a better sense for patterns. Here are some tests that load a few packages (just to get away from looking only at Base+stdlibs) and then load a new package (or execute a new command) while capturing invalidations.

| Package or command | Invalidated sig | # children | Explanation |
|:-------------------------- |:---------------- | -----------:|:------------------|
| FixedPointNumbers | reduce_empty(::Function, ::Type{T} where T) | 200 | Compiler chooses not to specialize this method. Many signatures don't actually intersect with the new method, but lack of specialization makes that hard to detect. A solution: add an init argument to maximum so compiler knows what to do if container is empty. |
| New ! method | !=(::Any, ::Any) & similar | 383 | Union-splitting for noninferred types. Called by, e.g., convert(::Type{T}, x::AbstractDict) where T<:AbstractDict, cmp(::AbstractString, ::String) ultimately from #15276, handling Expr args, ... |
| StaticArrays | unsafe_convert(::Type{Ptr{Nothing}}, b::Base.RefValue{T}) | 290 + tons in other packages | Overwhelmingly show_default (primarily show(::IO, ::RawFD) and show_function) |
| | cconvert(::Type{Ptr{Nothing}}, ::Any) | 88 | REPL.raw! not knowing the handle is Ptr{Cint} (true?) |
| | to_indices(to_indices(A, I::Tuple) | 80 | inference failures in concatenation |
| | all, any specializations | collectively hundreds | typically #15276 |
| OffsetArrays | axes(::AbstractArray) | 240 | JuliaInterpreter access to CodeInfo.linetable and CodeInfo.codelocs (both Any) |
| ColorTypes | promote_rule(::Type{<:Any}, ::Type{<:Any}) = Bottom | 35 | +(::Int, ::Integer) with no backedges |
| ImageCore | convert(::Type{Array{C,N}}, ::Array{C,N} where {C<:Colorant,N} | 80 | type-piracy, this should be defined in ColorTypes to head off any other packages implementing it |
| Interpolations | Base._getindex(::IndexLinear, A::AbstractVector, i::Int) | 44 | type-piracy (was defined to resolve an ambiguity) |
| GeometryTypes (used by Plots) | to_index(::Integer) | 190 | comes from the OffsetInteger type |
| | promote_rule(::Type{Int64}, ::Type{T} where T) | 104 | again the promote_rule(::Type{<:Any}, ::Type{<:Any}) = Bottom fallback |

If one discounts ambiguities, here's a summary:

• incomplete inference seems by far the most common. None of these are particularly surprising, but for the record:
  
  
  
  • deliberate decisions to avoid specialization may be the single most common source (obviously these are really good for compile times in their own way, but there's a dark side)
  
  
  • inference failures, like #15276, are also very common
  
  
  • in some cases non-specialized struct fields trigger problems; in many cases these have an obvious solution, but sometimes this conflicts with the merits of avoiding unnecessary specialization
  
  
• adding methods to intercept default pathways can help (e.g., show methods)
• type-piracy

Takeaways for the compiler:

• union-splitting is a big deal for a few cases but it's not actually that common a source
• perhaps in cases of @nospecialize annotations or where the compiler deliberately chooses not to specialize on an argument type, all calls with non-concrete types should be made by runtime dispatch? EDIT: the reduce_empty case might even need more, if you're calling a method that hasn't been specialized, do it by runtime dispatch?

Something I noticed and perhaps should mention: some MethodInstances appear to have no callers, e.g.,

julia> using MethodAnalysis

julia> mi = instance(Base.require_one_based_indexing, (AbstractArray{Float32,2}, AbstractArray{Float32,1}))
MethodInstance for require_one_based_indexing(::AbstractArray{Float32,2}, ::AbstractArray{Float32,1})

julia> mi.backedges
ERROR: UndefRefError: access to undefined reference
Stacktrace:
 [1] getproperty(::Core.MethodInstance, ::Symbol) at ./Base.jl:33
 [2] top-level scope at REPL[8]:1

I don't understand why this would be compiled if it doesn't have callers. Maybe they already got invalidated? There are quite a lot of these for require_one_based_indexing, to_indices, and things like +(::Int, ::Integer).

[timholy]

A good number of these are fixed in #35928 and various package PRs.

[JeffBezanson]

• perhaps in cases of @nospecialize annotations or where the compiler deliberately chooses not to specialize on an argument type, all calls with non-concrete types should be made by runtime dispatch

Sounds like a good idea; I'll try it.

[timholy]

I suspect that in combination with a slightly-enhanced #35877, if successful it would get rid of the large majority (80%? maybe even higher?) of the total invalidations for most packages I've tested.

(Assuming that SnoopCompile is correctly categorizing ambiguity, which is not at all a given.)

[JeffBezanson]

I gave that a quick try and so far it seems to make the compiler significantly slower. Apparently the extra type info is helpful. @nospecialize is used pretty heavily in the compiler. But what I tried is a very blunt instrument: for any method with any @nospecialize, skip inferring abstract call sites. Maybe some variation of that would work.

[timholy]

Bummer. I was so hopeful. Is there any useful profiling information about the source of the differential? I ask if it's specific because so much of the compiler is pretty well annotated with if isa(..., but I think I've seen a couple of invalidations and so there may be some places that could still use an annotation or two. (EDIT: hmmm, not sure how those invalidations would happen since it's isolated. Probably in show_ir or something.)

[timholy]

Maybe we could also introduce some function barriers manually?

[c42f]

It's disturbing that StaticArrays features prominently here. I'm happy to take some concrete actions in the package if that can help things?

[timholy]

Thanks for the offer! I think StaticArrays is mostly done, though, with a customized build (you need all my remaining latency-related PRs, here and in Pkg, plus #35877 including my tweak).

That said, if you want to poke at this stuff, there should be pretty good docs available in SnoopCompile, and you'll get the hang of it very quickly. See brief extra note in https://github.com/JuliaLang/julia/pull/36018#issuecomment-653211909.

[c42f]

Thanks! If there's a "proper fix" in the pipeline I'll leave off tweaking StaticArrays for now :-)

[timholy]

Good plan.

For the record, most invalidations from PkgA require a fix in Base, and most invalidations in PkgB require a fix in Base or PkgA. Only rarely have I found the right fix to be to delete or modify a method in the package that triggers the invalidation. And of course you see it only if you've already compiled or run the code in PkgA that gets invalidated by the methods defined in PkgB.

So when I say that StaticArrays seems mostly done, I should clarify that (1) I mean the number of invalidations that it triggers in Base/Pkg/REPL is down by at least an order of magnitude if not more (there could still be a few that need fixing), and (2) I've not deliberately compiled a lot of the code in StaticArrays and seen whether it needs protection from invalidation by other packages. I don't expect that to be a big problem; I think most well-written packages probably won't need many changes, because most packages probably live in a world where inference works. A subset of packages are doomed to work with inherently non-inferrable objects, so those might require a round of attention at some point. (JuliaInterpreter and Revise are examples, but they have already gotten a fair bit of attention since they were loaded during my investigations.)