Big invalidation method: iterate(v::Union{Base.KeySet{<:Any, <:DataStructures.SwissDict}, Base.ValueIterator{<:DataStructures.SwissDict}}, state)

[ChrisRackauckas]

inserting iterate(v::Union{Base.KeySet{<:Any, <:DataStructures.SwissDict}, Base.ValueIterator{<:DataStructures.SwissDict}}, state) in DataStructures at C:\Users\accou\.julia\packages\DataStructures\59MD0\src\swiss_dict.jl:646 invalidated:
   backedges: 1: superseding iterate(v::Union{Base.KeySet, Base.ValueIterator}, state...) in Base at abstractdict.jl:63 with MethodInstance for iterate(::Base.KeySet, ::Any) (1 children)
              2: superseding iterate(v::T, i::Int64) where T<:Union{Base.KeySet{<:Any, <:Dict}, Base.ValueIterator{<:Dict}} in Base at dict.jl:712 with MethodInstance for iterate(::Base.KeySet{var"#s82", T} where {var"#s82", T<:(Dict{var"#s82"})}, ::Int64) (7 children)
              3: superseding iterate(v::Union{Base.KeySet, Base.ValueIterator}, state...) in Base at abstractdict.jl:63 with MethodInstance for iterate(::Base.KeySet{String, _A} where _A<:(AbstractDict{String}), ::Any) (8 children)
              4: superseding iterate(v::T, i::Int64) where T<:Union{Base.KeySet{<:Any, <:Dict}, Base.ValueIterator{<:Dict}} in Base at dict.jl:712 with MethodInstance for iterate(::Base.KeySet{String, _A} where _A<:(Dict{String}), ::Int64) (145 children)

Found with:

using SnoopCompile
invalidations = @snoopr begin
    using OrdinaryDiffEq

    function lorenz(du, u, p, t)
        du[1] = 10.0(u[2] - u[1])
        du[2] = u[1] * (28.0 - u[3]) - u[2]
        du[3] = u[1] * u[2] - (8 / 3) * u[3]
    end
    u0 = [1.0; 0.0; 0.0]
    tspan = (0.0, 100.0)
    prob = ODEProblem{true,false}(lorenz, u0, tspan)
    alg = Rodas5()
    tinf = solve(prob, alg)
end;

trees = SnoopCompile.invalidation_trees(invalidations);

@show length(SnoopCompile.uinvalidated(invalidations)) # show total invalidations

show(trees[end-2]) # show the most invalidated method

# Count number of children (number of invalidations per invalidated method)
n_invalidations = map(trees) do methinvs
    SnoopCompile.countchildren(methinvs)
end

import Plots
Plots.plot(
    1:length(trees),
    n_invalidations;
    markershape=:circle,
    xlabel="i-th method invalidation",
    label="Number of children per method invalidations"
)

Third largest invalidation.

[StephenVavasis]

I suspect the problem is caused by this line:

Base.@propagate_inbounds function Base.iterate(v::Union{KeySet{<:Any, <:SwissDict}, Base.ValueIterator{<:SwissDict}}, state=v.dict.idxfloor)

which appears on l. 647 of swiss_dict.jl. There is a similar line on l. 537 of the same file. This use of KeySet is incompatible with Base because, in Base, the first type parameter is the key type of the second type parameter. So the above declaration may create some potential ambiguities (first type parameter is too generic), which could then possibly lead to invalidations. The above line should probably be changed to

Base.@propagate_inbounds function Base.iterate(v::Union{KeySet{K, SwissDict{K,V}}, Base.ValueIterator{SwissDict{K,V}}, state=v.dict.idxfloor)  where {K,V}

A similar change should be made to l. 537. However, I do not maintain swiss_dict.jl (it has a block of LLVM in the middle which is outside the scope of my understanding), and I also lack expertise in invalidation, so I am not brave enough to try this.

[ranocha]

Related to JuliaLang/julia#47089 and JuliaLang/julia#47136

[timholy]

With JuliaDiff/ForwardDiff.jl#620 (comment) I get no invalidations at all from DataStructures:

julia> for tree in trees
           println(tree.method.module)
       end
StaticArrays
Static
StaticArrays
ForwardDiff
Static
Static
CloseOpenIntervals
CPUSummary
StaticArrays
StaticArrays
OffsetArrays
VectorizationBase
LoopVectorization
ForwardDiff
RecursiveArrayTools
Static
Tables
CloseOpenIntervals
StaticArrays
Static
VectorizationBase
FillArrays
ForwardDiff
ForwardDiff
Static
Graphs.SimpleGraphs
FillArrays
VectorizationBase
SciMLBase
LoopVectorization
CPUSummary
StaticArrays
JuliaInterpreter
StaticArrays

What loads JuliaInterpreter, any idea? JuliaInterpreter defines an eltype method that turns out to do a heck of a number on build_jac_config.

[ChrisRackauckas]

https://juliahub.com/ui/Packages/JuliaInterpreter/PliIn/0.9.20?page=2

Looks like we are getting it through https://github.com/PetrKryslUCSD/Sparspak.jl, but only on older versions?

Unless it's through JET through Base somehow?

[timholy]

Seems like Revise is loaded by its docs: https://github.com/PetrKryslUCSD/Sparspak.jl/blob/a51282433d70634ba47075b665c7cb2deab0114f/docs/Project.toml#L3. I presume that Project.toml never gets used though?

Revise has an insane number of direct dependents: https://juliahub.com/ui/Packages/Revise/M1Qoh/3.4.0?page=2. Unless people are using it for some really wild metaprogramming, I'd naively think that number should be <10.

[ChrisRackauckas]

Seems like Revise is loaded by its docs: https://github.com/PetrKryslUCSD/Sparspak.jl/blob/a51282433d70634ba47075b665c7cb2deab0114f/docs/Project.toml#L3. I presume that Project.toml never gets used though?

It shouldn't.

Revise has an insane number of direct dependents: https://juliahub.com/ui/Packages/Revise/M1Qoh/3.4.0?page=2. Unless people are using it for some really wild metaprogramming, I'd naively think that number should be <10.

That's wild. Maybe you need to put a PSA out on that. That's just unnecessary 😅. https://github.com/thautwarm/DevOnly.jl could be helpful to solve people.

[timholy]

I'm wondering if it might be better to file issues with all of those packages? Seems more targeted.

[ChrisRackauckas]

PSA, issue, and a note on the README/docs of Revise not to add it as a dependency? Since it got that far around, something went wrong and a lot of people need to hear it 😅

[timholy]

Turns out in this case JuliaInterpreter was there simply because I forgot --startup=no. 🤦 But I probably will do something about that dependency list for Revise.

But of course since people are likely to load Revise, it's not irrelevant to fix that build_jac_config if possible.

[timholy]

Presumably this too can be closed?