Method invalidation on loading Polynomials #403

jishnub · 2022-05-26T08:08:45Z

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 · 2022-05-26T21:03:21Z

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 · 2022-05-26T21:26:06Z

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.)

* fix invalidations; close issue #403 * better fix, but not as general

jishnub · 2022-05-30T10:46:53Z

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

jverzani · 2022-05-30T11:20:03Z

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

jishnub · 2022-05-30T11:21:14Z

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

jverzani · 2022-05-30T12:03:25Z

THanks, good reason to upgrade.

jverzani · 2022-05-31T11:18:51Z

Okay, see them now. Will try and address.

jverzani · 2022-05-31T12:15:29Z

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 · 2022-06-02T14:53:46Z

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 · 2022-06-03T08:12:42Z

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 · 2022-06-03T11:43:00Z

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 · 2022-06-03T12:18:30Z

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

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 · 2022-06-03T17:53:11Z

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

jishnub · 2022-08-11T08:37:55Z

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 JuliaLang/julia#46000

jverzani · 2022-08-11T14:00:47Z

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 · 2022-08-12T05:51:46Z

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 · 2022-08-12T11:26:42Z

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 · 2022-10-12T11:52:04Z

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 · 2022-10-12T15:39:03Z

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 · 2022-10-12T16:12:33Z

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 · 2022-10-12T17:00:09Z

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

jishnub · 2023-01-03T14:15:11Z

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

jverzani closed this as completed May 26, 2022

jverzani reopened this May 26, 2022

jverzani added a commit to jverzani/Polynomials.jl that referenced this issue May 26, 2022

fix invalidations; close issue JuliaMath#403

e4196b1

jverzani added a commit that referenced this issue May 26, 2022

fix invalidations; close issue #403 (#406)

8b1c45a

* fix invalidations; close issue #403 * better fix, but not as general

jverzani mentioned this issue May 31, 2022

fix invalidations #412

Merged

jverzani mentioned this issue Jun 2, 2022

Issue 403c #419

Merged

jverzani mentioned this issue Jun 3, 2022

try to remove invalidations #421

Merged

jverzani mentioned this issue Jul 18, 2022

Some ambiguities found with Aqua #435

Open

jverzani mentioned this issue Aug 11, 2022

remove promote_rule method; add type information to any definition #440

Merged

jverzani mentioned this issue Sep 1, 2022

Create Invalidations.yml #446

Merged

jishnub mentioned this issue Oct 14, 2022

MethodError: Cannot convert an object of type Vector{Any} to an object of type UInt64 on julia nightly timholy/SnoopCompile.jl#305

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Method invalidation on loading Polynomials #403

Method invalidation on loading Polynomials #403

jishnub commented May 26, 2022

jverzani commented May 26, 2022

jverzani commented May 26, 2022

jishnub commented May 30, 2022

jverzani commented May 30, 2022

jishnub commented May 30, 2022

jverzani commented May 30, 2022

jverzani commented May 31, 2022

jverzani commented May 31, 2022

jverzani commented Jun 2, 2022

jishnub commented Jun 3, 2022 •

edited

Loading

jverzani commented Jun 3, 2022

jishnub commented Jun 3, 2022 •

edited

Loading

jverzani commented Jun 3, 2022

jishnub commented Aug 11, 2022 •

edited

Loading

jverzani commented Aug 11, 2022

jishnub commented Aug 12, 2022 •

edited

Loading

jverzani commented Aug 12, 2022

jishnub commented Oct 12, 2022

jverzani commented Oct 12, 2022

jverzani commented Oct 12, 2022

jishnub commented Oct 12, 2022

jishnub commented Jan 3, 2023

Method invalidation on loading Polynomials #403

Method invalidation on loading Polynomials #403

Comments

jishnub commented May 26, 2022

jverzani commented May 26, 2022

jverzani commented May 26, 2022

jishnub commented May 30, 2022

jverzani commented May 30, 2022

jishnub commented May 30, 2022

jverzani commented May 30, 2022

jverzani commented May 31, 2022

jverzani commented May 31, 2022

jverzani commented Jun 2, 2022

jishnub commented Jun 3, 2022 • edited Loading

jverzani commented Jun 3, 2022

jishnub commented Jun 3, 2022 • edited Loading

jverzani commented Jun 3, 2022

jishnub commented Aug 11, 2022 • edited Loading

jverzani commented Aug 11, 2022

jishnub commented Aug 12, 2022 • edited Loading

jverzani commented Aug 12, 2022

jishnub commented Oct 12, 2022

jverzani commented Oct 12, 2022

jverzani commented Oct 12, 2022

jishnub commented Oct 12, 2022

jishnub commented Jan 3, 2023

jishnub commented Jun 3, 2022 •

edited

Loading

jishnub commented Jun 3, 2022 •

edited

Loading

jishnub commented Aug 11, 2022 •

edited

Loading

jishnub commented Aug 12, 2022 •

edited

Loading