Method invalidation on loading Polynomials

[jishnub]

julia> using SnoopCompileCore

julia> invalidations = @snoopr using Polynomials;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> length(trees)
6

julia> trees[end].method
convert(::Type{T}, p::P) where {T, P<:(AbstractPolynomial{T})} in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/common.jl:433

julia> trees[end-1].method
promote_rule(::Type{<:SparsePolynomial{var"#336#T", var"#338#X"}}, ::Type{var"#337#S"}) where {var"#336#T", var"#337#S"<:Number, var"#338#X"} in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/abstract.jl:90

julia> trees[end-3].method
any(pred, p::AbstractPolynomial) in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/common.jl:493

These three methods introduced here cause a lot of invalidation, leading to slow package load times. Maybe we can think about ways in which this may be remedied.

[jverzani]

Thanks, I haven't used this tool before. I get only length(trees) being 4, the first method shows up only. Is that machine dependent? (This is with your freshly merged PR.)

[jverzani]

I have a fix for the first, but I don't have the second two showing up when I follow your report. If you have time, could you check? (If the tests pass I'll merge it in and tag, so this would be easier for you.)

[jishnub]

Yes, I can confirm that the invalidation of convert doesn't show up anymore. The ones that remain are any and promote_rule

[jverzani]

I'm on v1.7.2. How about you? (I wasn't seeing the latter 2 and am guessing it is version dependent.)

[jishnub]

I'm on 1.7.3. It might be version-dependent

[jverzani]

THanks, good reason to upgrade.

[jverzani]

Okay, see them now. Will try and address.

[jverzani]

Oddly, in #412 I only addressed the issue with any, but I have no clue why the promote_rule one doesn't seem present anymore.

[jverzani]

I found a new invalidation under the 1.8 release candidate. If you have a chance, can you test on your end if the promote_rule is still present, and perhaps if there are others?

[jishnub]

This is what I find.

julia> using SnoopCompileCore

julia> invalidations = @snoopr using Polynomials;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> trees |> length
5

julia> trees[end]
inserting convert(P::Type{<:Polynomials.PnPolynomial}, p::Polynomials.PnPolynomial{var"#484#T", var"#485#X"}) where {var"#484#T", var"#485#X"} in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/abstract.jl:84 invalidated:
   backedges: 1: superseding convert(::Type{Union{}}, x) in Base at essentials.jl:213 with MethodInstance for convert(::Core.TypeofBottom, ::Any) (7 children)
   39 mt_cache

julia> trees[end-3]
inserting any(pred::Function, p::AbstractPolynomial) in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/common.jl:488 invalidated:
   backedges: 1: superseding any(f, itr) in Base at reduce.jl:1191 with MethodInstance for any(::typeof(ismissing), ::Any) (1 children)

julia> VERSION
v"1.8.0-rc1"

There are two methods invalidated, and promote_rule doesn't appear to be one of them.

[jverzani]

Thank you! I'll see if I can guess what might make these go away. (Annoyingly, they all seem to be addressed by tightening signatures making code presumably less generic, though I could just be misunderstanding the root cause.)

[jishnub]

Fixing some invalidations has improved the package load time already! On ddb9e57fd6085c1a061ae0be1b273d3416e2cc67:

julia> @time using Polynomials
  1.670978 seconds (1.90 M allocations: 139.036 MiB, 2.05% gc time, 55.59% compilation time)

On master

julia> @time using Polynomials
  1.099670 seconds (1.32 M allocations: 109.952 MiB, 34.30% compilation time)

[jverzani]

Maybe #421 will address this... If you get a chance to try, I'd be curious to hear.

[jishnub]

I've got some insights into what's leading to invalidation here. It's often a relation like the following:

julia> Union{} <: Polynomial{Int,Vector{Int}}
true

which implies

julia> @which promote_rule(Polynomial{Int}, Union{})
promote_rule(::Type{<:AbstractPolynomial{T}}, ::Type{<:AbstractPolynomial{S}}) where {T, S}
     @ Polynomials ~/Dropbox/JuliaPackages/Polynomials.jl/src/common.jl:436

I'm certain that we didn't mean to define this method here. I think there should be a solution to this in Base, similar to https://github.com/JuliaLang/julia/pull/46000

[jverzani]

Thanks again! In #440 I removed this definition of promote_rule, as it was unnecessary, and fixed an issue with any and all. Testing under 1.7, I have 3 invalidations related to MutableArithmetics, under 1.8rc4 there are now none. Hopefully that is the same (or better) for your setup.

[jishnub]

This is what I see currently on v1.8.0-rc4

julia> trees = invalidation_trees(invalidations)
6-element Vector{SnoopCompile.MethodInvalidations}:
 inserting *(::Any, z::MutableArithmetics.Zero) in MutableArithmetics at /home/jishnu/.julia/packages/MutableArithmetics/Lnlkl/src/rewrite.jl:59 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 any(pred, p::AbstractPolynomial{T, X}) where {T, X} in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/common.jl:485 invalidated:
   backedges: 1: superseding any(f, itr) in Base at reduce.jl:1191 with MethodInstance for any(::typeof(ismissing), ::Any) (1 children)

 inserting iszerodefined(::Type{<:MutableArithmetics.AbstractMutable}) in MutableArithmetics at /home/jishnu/.julia/packages/MutableArithmetics/Lnlkl/src/dispatch.jl:764 invalidated:
   backedges: 1: superseding iszerodefined(::Type{<:Number}) in LinearAlgebra at /home/jishnu/packages/julias/julia-1.8/share/julia/stdlib/v1.8/LinearAlgebra/src/structuredbroadcast.jl:128 with MethodInstance for LinearAlgebra.iszerodefined(::Type{<:Number}) (1 children)
              2: superseding iszerodefined(::Type) in LinearAlgebra at /home/jishnu/packages/julias/julia-1.8/share/julia/stdlib/v1.8/LinearAlgebra/src/structuredbroadcast.jl:127 with MethodInstance for LinearAlgebra.iszerodefined(::DataType) (1 children)

 inserting step(r::MutableArithmetics.MutatingStepRange) in MutableArithmetics at /home/jishnu/.julia/packages/MutableArithmetics/Lnlkl/src/implementations/MutatingStepRange.jl:25 invalidated:
   mt_backedges: 1: signature Tuple{typeof(step), OrdinalRange{Int64, Int64}} triggered MethodInstance for (::Base.IteratorsMD.var"#21#23")(::OrdinalRange{Int64, Int64}) (3 children)

 inserting convert(P::Type{<:Polynomials.PolyCompat.Poly}, p::Polynomials.PolyCompat.Poly{T, X}) where {T<:Number, X} in Polynomials.PolyCompat at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/polynomials/Poly.jl:44 invalidated:
   backedges: 1: superseding convert(::Type{Union{}}, x) in Base at essentials.jl:213 with MethodInstance for convert(::Core.TypeofBottom, ::Any) (38 children)

 inserting promote_rule(::Type{<:FactoredPolynomial{T, X}}, ::Type{S}) where {T, S<:Number, X} in Polynomials at /home/jishnu/Dropbox/JuliaPackages/Polynomials.jl/src/polynomials/factored_polynomial.jl:104 invalidated:
   backedges: 1: superseding promote_rule(::Type{<:AbstractIrrational}, ::Type{T}) where T<:Real in Base at irrationals.jl:44 with MethodInstance for promote_rule(::Core.TypeofBottom, ::Type{UInt64}) (1 children)
              2: superseding promote_rule(::Type, ::Type) in Base at promotion.jl:310 with MethodInstance for promote_rule(::Type{T} where T<:Unsigned, ::Type{UInt64}) (60 children)
   36 mt_cache

The situation is better on v1.9 though, as some of these issues have been resolved:

julia> trees = invalidation_trees(invalidations)
4-element Vector{SnoopCompile.MethodInvalidations}:
 inserting *(::Any, z::MutableArithmetics.Zero) @ MutableArithmetics ~/.julia/packages/MutableArithmetics/Lnlkl/src/rewrite.jl:59 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 iszerodefined(::Type{<:MutableArithmetics.AbstractMutable}) @ MutableArithmetics ~/.julia/packages/MutableArithmetics/Lnlkl/src/dispatch.jl:764 invalidated:
   backedges: 1: superseding iszerodefined(::Type{<:Number}) @ LinearAlgebra ~/packages/julias/julia-latest/share/julia/stdlib/v1.9/LinearAlgebra/src/structuredbroadcast.jl:128 with MethodInstance for LinearAlgebra.iszerodefined(::Type{<:Number}) (1 children)
              2: superseding iszerodefined(::Type) @ LinearAlgebra ~/packages/julias/julia-latest/share/julia/stdlib/v1.9/LinearAlgebra/src/structuredbroadcast.jl:127 with MethodInstance for LinearAlgebra.iszerodefined(::DataType) (1 children)

 inserting promote_rule(::Type{<:ArnoldiFit{var"#82#T", var"#84#X"}}, ::Type{var"#83#S"}) where {var"#82#T", var"#83#S"<:Number, var"#84#X"} @ Polynomials ~/Dropbox/JuliaPackages/Polynomials.jl/src/abstract.jl:90 invalidated:
   backedges: 1: superseding promote_rule(::Type{<:AbstractIrrational}, ::Type{T}) where T<:Real @ Base irrationals.jl:44 with MethodInstance for promote_rule(::Core.TypeofBottom, ::Type{UInt64}) (1 children)
              2: superseding promote_rule(::Type, ::Type) @ Base promotion.jl:319 with MethodInstance for promote_rule(::Type{T} where T<:Unsigned, ::Type{UInt64}) (5 children)
   43 mt_cache

 inserting step(r::MutableArithmetics.MutatingStepRange) @ MutableArithmetics ~/.julia/packages/MutableArithmetics/Lnlkl/src/implementations/MutatingStepRange.jl:25 invalidated:
   mt_backedges: 1: signature Tuple{typeof(step), OrdinalRange{Int64, Int64}} triggered MethodInstance for (::Base.IteratorsMD.var"#19#21")(::OrdinalRange{Int64, Int64}) (12 children)

There still seems to be one promote_rule invalidation, but that's about it.

(Polynomials) pkg> st
Project Polynomials v3.1.7
Status `~/Dropbox/JuliaPackages/Polynomials.jl/Project.toml`
  [d8a4904e] MutableArithmetics v1.0.4
  [3cdcf5f2] RecipesBase v1.2.1
  [37e2e46d] LinearAlgebra

julia> versioninfo()
Julia Version 1.9.0-DEV.1120
Commit 95cbb9f6184 (2022-08-12 00:44 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.5 (ORCJIT, tigerlake)
  Threads: 1 on 8 virtual cores
Environment:
  LD_LIBRARY_PATH = :/usr/lib/x86_64-linux-gnu/gtk-3.0/modules
  JULIA_EDITOR = subl

[jverzani]

Thanks so much for this. Hopefully, that last one can be tracked down.

I also noticed that timing the load with 1.8 that MutableArithmetics is half the load time and, I believe, a fairly niche usage. I might try to spin that off into a separate package for interested users.

[jishnub]

Current status on Julia nightly:

julia> VERSION
v"1.9.0-DEV.1575"

julia> trees = invalidation_trees(invalidations)
1-element Vector{SnoopCompile.MethodInvalidations}:
 inserting promote_rule(::Type{<:Polynomial{var"#169#T", var"#171#X"}}, ::Type{var"#170#S"}) where {var"#169#T", var"#170#S"<:Number, var"#171#X"} @ Polynomials ~/Dropbox/JuliaPackages/Polynomials.jl/src/abstract.jl:90 invalidated:
   backedges: 1: superseding promote_rule(::Type{<:AbstractIrrational}, ::Type{T}) where T<:Real @ Base irrationals.jl:44 with MethodInstance for promote_rule(::Type{Union{}}, ::Type{UInt64}) (1 children)
              2: superseding promote_rule(::Type, ::Type) @ Base promotion.jl:319 with MethodInstance for promote_rule(::Type{T} where T<:Unsigned, ::Type{UInt64}) (5 children)
   42 mt_cache

Thanks for the efforts to resolve this, package load time has improved significantly.

[jverzani]

Thanks. Still don't understand why I can't replicate these things. I get the following:

julia> trees
1-element Vector{SnoopCompile.MethodInvalidations}:
 inserting promote_rule(::Type{<:ChebyshevT{var"#633#T", var"#635#X"}}, ::Type{var"#634#S"}) where {var"#633#T", var"#634#S"<:Number, var"#635#X"} @ Polynomials ~/julia/Polynomials/src/abstract.jl:90 invalidated:
   backedges: 1: superseding promote_rule(::Type, ::Type) @ Base promotion.jl:319 with MethodInstance for promote_rule(::Type{T} where T<:Unsigned, ::Type{UInt64}) (1 children)
              2: superseding promote_rule(::Type{<:AbstractIrrational}, ::Type{T}) where T<:Real @ Base irrationals.jl:44 with MethodInstance for promote_rule(::Type{Union{}}, ::Type{UInt64}) (5 children)
   49 mt_cache

They are the same line in the file, so hopefully both can be addressed.

[jverzani]

And now I can't even get what I had before:

 | | |_| | | | (_| |  |  Version 1.9.0-DEV.1575 (2022-10-12)
 _/ |\__'_|_|_|\__'_|  |  Commit 015874c6181 (0 days old master)
|__/                   |

(@v1.9) pkg> st
Status `~/.julia/environments/v1.9/Project.toml`
  [f27b6e38] Polynomials v3.2.0 `~/julia/Polynomials`
  [295af30f] Revise v3.4.0
  [aa65fe97] SnoopCompile v2.9.4
  [e2b509da] SnoopCompileCore v2.9.0

julia> using SnoopCompile, SnoopCompileCore

julia> invalidations = @snoopr using Polynomials; typeof(invalidations)
Vector{Any} (alias for Array{Any, 1})

julia> trees = invalidation_trees(invalidations)
ERROR: MethodError: Cannot `convert` an object of type Vector{Any} to an object of type UInt64

Sorry, this one might sit for a bit until I can get something working.

[jishnub]

No worries, we might need some help here. I've faced this issue with SnoopCompile elsewhere as well.

[jishnub]

On Julia v1.9.0-beta2, I obtain

julia> using SnoopCompileCore

julia> invalidations = @snoopr using Polynomials;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> trees
SnoopCompile.MethodInvalidations[]

So, yay! Looks like this is fully solved now, at least on my system