search

timholy / SnoopCompile.jl

Provide insights about latency (TTFX) for Julia packages
https://timholy.github.io/SnoopCompile.jl/dev/
Other
309 stars 48 forks source link

Loading ReverseDiff and UnicodePlots together and looking at their invalidations prints tens of thousands of lines #362

Open KristofferC opened 1 year ago

KristofferC commented 1 year ago 
invalidations = @snoopr ReverseDiff, UnicodePlots
tree = invalidation_trees(invalidations);
...
  inserting materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s32"} where var"#s32"<:Tuple{AbstractArray{<:Number}, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:282 invalidated:
   backedges:     1: superseding materialize(bc::Base.Broadcast.Broadcasted) @ Base.Broadcast broadcast.jl:873 with MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted) (1 children)
                  2: superseding materialize(bc::Base.Broadcast.Broadcasted) @ Base.Broadcast broadcast.jl:873 with MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted) (1 children)
                ..
...
children)
              59669: superseding materialize(bc::Base.Broadcast.Broadcasted) @ Base.Broadcast broadcast.jl:873 with MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle}) (1 children)
              59670: superseding materialize(bc::Base.Broadcast.Broadcasted) @ Base.Broadcast broadcast.jl:873 with MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle}) (1 children)
              59671: superseding materialize(bc::Base.Broadcast.Broadcasted) @ Base.Broadcast broadcast.jl:873 with MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle}) (1 children)
...

should probably be collapsed somehow. Also I don't really understand where this many methods can come from:

julia> length(uinvalidated(invalidations))
582
KristofferC commented 1 year ago

I have another case where it prints

              232: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              233: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              234: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              235: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              236: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              237: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              238: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              239: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              240: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              241: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              242: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              243: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              244: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              245: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              246: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              247: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              248: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              249: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              250: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              251: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              252: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              253: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              254: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              255: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              256: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)
              257: superseding ndims(::AbstractArray{T, N}) where {T, N} @ Base abstractarray.jl:269 with MethodInstance for ndims(::AbstractArray) (1 children)

maybe these should be collapsed somehow since they are identical?

timholy commented 1 year ago

This is a tough case. First, I clearly have somewhat different data from you, not sure the reason, but don't expect an exact match to the specific numbers you show above.

I've only made partial progress. For me, bad things start to happen at

julia> invalidations[8041:8044]
4-element Vector{Any}:
    MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle})
    "insert_backedges_callee"
 730
    Any[materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s32"} where var"#s32"<:Tuple{Rational, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s31"} where var"#s31"<:Tuple{ReverseDiff.TrackedArray, Rational}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:291, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s32"} where var"#s32"<:Tuple{BigFloat, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s31"} where var"#s31"<:Tuple{ReverseDiff.TrackedArray, BigFloat}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:291, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s32"} where var"#s32"<:Tuple{BigInt, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s31"} where var"#s31"<:Tuple{ReverseDiff.TrackedArray, BigInt}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:291, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s32"} where var"#s32"<:Tuple{AbstractFloat, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s31"} where var"#s31"<:Tuple{ReverseDiff.TrackedArray, AbstractFloat}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:291, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s32"} where var"#s32"<:Tuple{ForwardDiff.Dual, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(SpecialFunctions.bessely), var"#s31"} where var"#s31"<:Tuple{ReverseDiff.TrackedArray, ForwardDiff.Dual}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:291  …  materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s28"} where var"#s28"<:Tuple{AbstractVector{<:Number}, ReverseDiff.TrackedReal}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:284, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s30"} where var"#s30"<:Tuple{ReverseDiff.TrackedReal, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:278, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s32"} where var"#s32"<:Tuple{Real, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:290, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s26"} where var"#s26"<:Tuple{ReverseDiff.TrackedReal, AbstractMatrix{<:Number}}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:285, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s26"} where var"#s26"<:Tuple{ReverseDiff.TrackedReal, AbstractVector{<:Number}}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:285, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s30"} where var"#s30"<:Tuple{ReverseDiff.TrackedArray, AbstractArray{<:Number}}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:283, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s28"} where var"#s28"<:Tuple{AbstractArray{<:Number}, ReverseDiff.TrackedReal}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:284, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s26"} where var"#s26"<:Tuple{ReverseDiff.TrackedReal, AbstractArray{<:Number}}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:285, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s32"} where var"#s32"<:Tuple{AbstractVector{<:Number}, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:282, materialize(bc::Base.Broadcast.Broadcasted{<:Any, <:Any, typeof(min), var"#s32"} where var"#s32"<:Tuple{AbstractArray{<:Number}, ReverseDiff.TrackedArray}) @ ReverseDiff ~/.julia/packages/ReverseDiff/Zu4v6/src/derivatives/broadcast.jl:282]

That list of causes (in SnoopCompile parlance)/matches (in staticdata_utils.c parlance) on the last line (index 8044) is 2037 methods long! https://github.com/JuliaDiff/ReverseDiff.jl/blob/f1f3d1f932981f9b5fe9fdbfdc8676056587ea3e/src/derivatives/broadcast.jl#L290-L291

Interpretation: starting at the top (i.e., index 8041 in invalidations), this means that

MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle})

was the signature we had been compiled to call, and that signature now matches 2037 Methods. The 730 is an "edge index", among a list of all the external calls needed by compiled package code; it's there because jl_verify_edges runs first and then later jl_verify_methods checks all the dependents of the edges. In other words, the index 730 allows you to identify a dependency on a particular edge. So

julia> sum((==).(invalidations, 730))
16

means that there were 15 dependents.

So the reason you get so much output is that any of those 2037 Methods could have invalidated the same 15 dependents. Thus you get >2037 separate trees, each with a different method, but the same list of dependents. All this happens here: https://github.com/timholy/SnoopCompile.jl/blob/0d84aed1c40c670806768b3d53004e5bb397ba62/src/invalidations.jl#L482-L484

The design of SnoopCompile, where each inserted method is the root of a tree of invalidations, is not well-suited to the case where there are large numbers of effectively-identical causes for the same set of invalidations.

timholy commented 1 year ago

For reference, here are the number of "excess" (unexpected) matching methods for each case of edge-validation failure:

9-element Vector{Int64}:
    2
    2
   47
    2
    2
 2037
 2037
    2
    8

So most are quite short. The one with 47 is also materialize at the same lines, but with

MethodInstance for Base.Broadcast.materialize(::Base.Broadcast.Broadcasted{_A, Nothing, typeof(/)} where _A<:Union{Nothing, Base.Broadcast.BroadcastStyle})

as the intended signature. The rest are all convert and eltype signatures.