Invalidations from ChainRulesCore Tangent overload on Tail

[ChrisRackauckas]

Found in SciML/DifferentialEquations.jl#786

julia> show(trees[end-3])
inserting tail(t::ChainRulesCore.Tangent{<:NamedTuple{<:Any, <:Tuple{}}}) in ChainRulesCore at C:\Users\accou\.julia\packages\ChainRulesCore\ctmSK\src\tangent_types\tangent.jl:110 invalidated:
   mt_backedges:  1: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Int64}, ::Any) (0 children)
                  2: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Any, Vararg{Any}}, ::Any) (0 children)
                  3: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_isdone(::Tuple, ::Any) (0 children)
                  4: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Missing, Vararg{Any}}, ::Missing) (0 children)
                  5: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Missing) (0 children)
                  6: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Bool, Vararg{Any}}, ::Bool) (0 children)
                  7: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Bool) (0 children)
                  8: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for iterate(::Base.Iterators.Enumerate{Vector{VersionNumber}}, ::Any) (0 children)
                  9: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for VSCodeServer.JuliaInterpreter.optimize!(::Core.CodeInfo, ::Method) (0 children)
                 10: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for JuliaInterpreter.optimize!(::Core.CodeInfo, ::Method) (0 children)
                 11: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for LoweredCodeUtils.step_through_methoddef(::Any, ::JuliaInterpreter.Frame, ::Any) (0 children)
                 12: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.tail(::NamedTuple{names}) where names (450 children)
false

[oxinabox]

Hmm is this a weird kind of invalidation not because we are defining a more specific method,
but because we define the only method that doesn't error?

I think it would probably be fine for us to error in this case too.
It's a weird corner case: https://github.com/JuliaDiff/ChainRulesCore.jl/blob/main/src/tangent_types/tangent.jl#L110

[sethaxen]

This one has a lot of children and will hit a lot of packages, so it would be nice to fix it if possible. @oxinabox are you suggesting deleting the method?

[ranocha]

Current version:

julia> import Pkg; Pkg.activate(temp=true); Pkg.add("ChainRulesCore")

julia> using SnoopCompileCore; invalidations = @snoopr(using ChainRulesCore); using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> length(uinvalidated(invalidations))
267

julia> trees
3-element Vector{SnoopCompile.MethodInvalidations}:
 inserting *(::Any, ::ZeroTangent) in ChainRulesCore at /home/hendrik/.julia/packages/ChainRulesCore/6Sl9y/src/tangent_arithmetic.jl:105 invalidated:
   mt_backedges: 1: signature Tuple{typeof(*), String, Any} triggered MethodInstance for (::Test.var"#7#9")(::Any) (0 children)
                 2: signature Tuple{typeof(*), String, Any} triggered MethodInstance for (::Test.var"#8#10")(::Any) (0 children)

 inserting convert(::Type{<:Number}, x::ChainRulesCore.NotImplemented) in ChainRulesCore at /home/hendrik/.julia/packages/ChainRulesCore/6Sl9y/src/tangent_types/notimplemented.jl:63 invalidated:
   backedges: 1: superseding convert(::Type{Union{}}, x) in Base at essentials.jl:213 with MethodInstance for convert(::Core.TypeofBottom, ::Any) (13 children)

 inserting tail(t::Tangent{<:NamedTuple{<:Any, <:Tuple{}}}) in ChainRulesCore at /home/hendrik/.julia/packages/ChainRulesCore/6Sl9y/src/tangent_types/tangent.jl:110 invalidated:
   mt_backedges: 1: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Int64}, ::Any) (0 children)
                 2: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Any, Vararg{Any}}, ::Any) (0 children)
                 3: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_isdone(::Tuple, ::Any) (0 children)
                 4: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Missing, Vararg{Any}}, ::Missing) (0 children)
                 5: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Missing) (0 children)
                 6: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Bool, Vararg{Any}}, ::Bool) (0 children)
                 7: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Bool) (0 children)
                 8: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for iterate(::Base.Iterators.Enumerate{Vector{VersionNumber}}, ::Any) (0 children)
                 9: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.tail(::NamedTuple{names}) where names (335 children)
   24 mt_cache

Removing https://github.com/JuliaDiff/ChainRulesCore.jl/blob/main/src/tangent_types/tangent.jl#L110:

julia> import Pkg; Pkg.activate(temp=true); Pkg.develop("ChainRulesCore")

julia> using SnoopCompileCore; invalidations = @snoopr(using ChainRulesCore); using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> length(uinvalidated(invalidations))
271

julia> trees
3-element Vector{SnoopCompile.MethodInvalidations}:
 inserting *(::Any, ::ZeroTangent) in ChainRulesCore at /home/hendrik/.julia/dev/ChainRulesCore/src/tangent_arithmetic.jl:105 invalidated:
   mt_backedges: 1: signature Tuple{typeof(*), String, Any} triggered MethodInstance for (::Test.var"#7#9")(::Any) (0 children)
                 2: signature Tuple{typeof(*), String, Any} triggered MethodInstance for (::Test.var"#8#10")(::Any) (0 children)
   18 mt_cache

 inserting convert(::Type{<:Number}, x::ChainRulesCore.NotImplemented) in ChainRulesCore at /home/hendrik/.julia/dev/ChainRulesCore/src/tangent_types/notimplemented.jl:63 invalidated:
   backedges: 1: superseding convert(::Type{Union{}}, x) in Base at essentials.jl:213 with MethodInstance for convert(::Core.TypeofBottom, ::Any) (168 children)
   9 mt_cache

 inserting tail(t::Tangent{<:NamedTuple{<:Any, <:Tuple{Any}}}) in ChainRulesCore at /home/hendrik/.julia/dev/ChainRulesCore/src/tangent_types/tangent.jl:109 invalidated:
   mt_backedges: 1: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Int64}, ::Any) (0 children)
                 2: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base._cshp(::Int64, ::Tuple{Bool}, ::Tuple{Any, Vararg{Any}}, ::Any) (0 children)
                 3: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_isdone(::Tuple, ::Any) (0 children)
                 4: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Missing, Vararg{Any}}, ::Missing) (0 children)
                 5: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Missing) (0 children)
                 6: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Bool, Vararg{Any}}, ::Bool) (0 children)
                 7: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.Iterators._zip_iterate_some(::Tuple, ::Any, ::Tuple{Any, Vararg{Any}}, ::Bool) (0 children)
                 8: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for iterate(::Base.Iterators.Enumerate{Vector{VersionNumber}}, ::Any) (0 children)
                 9: signature Tuple{typeof(Base.tail), Any} triggered MethodInstance for Base.tail(::NamedTuple{names}) where names (184 children)

So there are still many invalidations left...

The code removing https://github.com/JuliaDiff/ChainRulesCore.jl/blob/main/src/tangent_types/tangent.jl#L110 lives in https://github.com/ranocha/ChainRulesCore.jl/tree/hr/fix_invalidations. Shall I make a PR? Or does anybody have time to hunt these invalidations?

[oxinabox]

The ones on * are not a concern.
They aren't affecting anything real that will ever matter. Though it might be nice to find out what actually causes them.

The one on convert is a bit of a worry, I would like to know where it came from. I.e. what changed in Base (I guess?), as that wasn't there before.
Or did SnoopCompile get smarter.

Re:tail. We should also be able to delete
So the remaining ones are on line 109.
I guess this is because now there exist multiple possible return types for Base.tail(::Any) still.
Rather than just Tuple/NamedTuple? Which I guess it was relying on via world splitting.

Since Base.tail isn't part of the exported API, maybe we shouldn't have overloaded it in the first place.
@mcabbott you added that in #567
is it actually being used anywhere?

[mcabbott]

Base has these methods for tail:

julia> methods(Base.tail)
# 3 methods for generic function "tail" from Base:
 [1] tail(t::NamedTuple{names}) where names
     @ namedtuple.jl:321
 [2] tail(::Tuple{})
     @ essentials.jl:330
 [3] tail(x::Tuple)
     @ essentials.jl:329

There's no overlap with Tangent. Why exactly is anything invalidated?

[mcabbott]

IIRC the rule which uses it is https://github.com/JuliaDiff/ChainRules.jl/blob/39c2d17df672836659493d6adb7d4ad8593250a5/src/rulesets/Base/indexing.jl#L175-L178 , obviously that could be re-written if someone wants to.

[oxinabox]

There's no overlap with Tangent. Why exactly is anything invalidated?

I believe it is a so called "world splitting" optimization.
Where even if we can't infer which method of Base.tail is going to be hit,
if we know that all methods of Base.tail return one of a small number of types,
then we can generate the code for all of them and just put in a if
(It's like the small union's optimization)

[mcabbott]

Ah ok.

So every week the mental model you need grows more complex. I guess this is a strong argument against defining your own types, when you can avoid it. "Your struct is as good as Base's" isn't quite true, it seems.

[oxinabox]

So every week the mental model you need grows more complex.

Yeah, I miss the days before julia had an optimizer. It used to be easier to reason about.
Julia is IMO a very hard language to reason about these days, luckily we have good tools now; and this stuff only matters right at the pointy-end of micro-optimizations which is done by experts.
Apparently world-splitting was introduced at the same time as small-union splitting.
But possibly SnoopCompile couldn't recognize it til recently.
idk

[ranocha]

I think it can also be totally independent of any of these optimizations. If anything is inferred only as Any in some code in base or the stdlibs before calling tail on it, the methods in question need to be re-inferred and re-compiled when loading this package introducing a new method for tail. So the best fix would be to hunt the type instabilities in Julia base/stdlibs and fix them there. But someone needs to spend some time on this.

[oxinabox]

I think it can also be totally independent of any of these optimizations. If anything is inferred only as Any in some code in base or the stdlibs before calling tail on it, the methods in question need to be re-inferred and re-compiled when loading this package introducing a new method for tail.

No, I don't think so.
Without this optimization that should result in a dynamic dispatch, whcih would avoid need to recompilation.

[mcabbott]

I wonder how much we'd have to change in Base to delete Tangent entirely. Being able to add them is the big virtue, what chance we could get these methods accepted?

Base.:+(x::NamedTuple{s}, y::NamedTuple{s}) where {s} = map(+, x, y)
Base.:+(x::Tuple{Vararg{Any,N}}, y::Tuple{Vararg{Any,N}}) where {N} = map(+, x, y)

[ranocha]

JuliaLang/julia#46762 helps a bit but does not fix all invalidations.