JuliaCollections / OrderedCollections.jl

Julia implementation of associative containers that preserve insertion order
MIT License
92 stars 38 forks source link

Invalidations due to conversion to OrderedDict #90

Open sethaxen opened 2 years ago

sethaxen commented 2 years ago

There are several invalidations in this package that impact downstream dependants:

julia> using SnoopCompileCore

julia> invalidations = @snoopr using OrderedCollections;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations)
3-element Vector{SnoopCompile.MethodInvalidations}:
 inserting in(key, v::Base.KeySet{K, T}) where {K, T<:(OrderedDict{K})} in OrderedCollections at /home/sethaxen/.julia/packages/OrderedCollections/PRayh/src/ordered_dict.jl:394 invalidated:
   backedges: 1: superseding in(k, v::Base.KeySet) in Base at abstractdict.jl:71 with MethodInstance for in(::Char, ::Base.KeySet) (2 children)

 inserting (::Base.var"#sort!##kw")(::Any, ::typeof(sort!), d::OrderedDict) in OrderedCollections at /home/sethaxen/.julia/packages/OrderedCollections/PRayh/src/dict_sorting.jl:4 invalidated:
   mt_backedges: 1: signature Tuple{Base.var"#sort!##kw", NamedTuple{(:by,), Tuple{typeof(identity)}}, typeof(sort!), Any} triggered MethodInstance for TOML.Internals.Printer.var"#_print#10"(::Int64, ::Bool, ::Bool, ::typeof(identity), ::typeof(TOML.Internals.Printer._print), ::Nothing, ::IOStream, ::AbstractDict, ::Vector{String}) (46 children)

 inserting convert(::Type{OrderedDict{K, V}}, d::OrderedDict{K, V}) where {K, V} in OrderedCollections at /home/sethaxen/.julia/packages/OrderedCollections/PRayh/src/ordered_dict.jl:110 invalidated:
   backedges: 1: superseding convert(::Type{T}, x::AbstractDict) where T<:AbstractDict in Base at abstractdict.jl:561 with MethodInstance for convert(::Type, ::AbstractDict) (242 children)
   3 mt_cache

The final one is the most severe with 242 children. This has some effect on load time:

current:

julia> @time using OrderedCollections
  0.011149 seconds (16.78 k allocations: 1.136 MiB)

removing the convert methods:

julia> @time using OrderedCollections
  0.008151 seconds (9.70 k allocations: 771.891 KiB)

The methods in question are: https://github.com/JuliaCollections/OrderedCollections.jl/blob/07ee08e0697f7bd756421c99bf1d9d3f89e6bf56/src/ordered_dict.jl#L95-L110

The default method in Base forwards to the constructor:

function convert(::Type{T}, x::AbstractDict) where T<:AbstractDict
    h = T(x)
    if length(h) != length(x)
        error("key collision during dictionary conversion")
    end
    return h
end

But for OrderedDict, convert and the constructor don't do the same thing. e.g. OrderedDict{K,V}(::OrderedDictr{K,V}) copies the keys and values, while convert does not. Likewise, OrderedDict{K,V}(::AbstractDict) doesn't raise a deprecation warning, but convert(OrderedDict{K,V}, ::AbstractDict) does.

Is it possible to remove both of these methods? If they are removed, the test suite still passes.