Polynomials.jl
Polynomials.jl copied to clipboard
Method invalidation on loading Polynomials
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.
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.)
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.)
Yes, I can confirm that the invalidation of convert
doesn't show up anymore. The ones that remain are any
and promote_rule
I'm on v1.7.2. How about you? (I wasn't seeing the latter 2 and am guessing it is version dependent.)
I'm on 1.7.3. It might be version-dependent
THanks, good reason to upgrade.
Okay, see them now. Will try and address.
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.
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?
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.
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.)
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)
Maybe #421 will address this... If you get a chance to try, I'd be curious to hear.
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
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.
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
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.
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.
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.
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.
No worries, we might need some help here. I've faced this issue with SnoopCompile
elsewhere as well.
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