How to avoid full specialization of `haskey(::Dict, key)` on the caller side

New to Julia
,
1

I don’t understand the details of the implementation of Dict, but I don’t think the V in Dict{K,V} is involved in the “essential functionality” in haskey.
For example, when I start a REPL session, there are method instances such as haskey(::Dict{String, ::Any}, ::String). However, within ordinary call of haskey, full specialization will be done. Is there an easy way to avoid the full specialization on the caller side?

julia> dict = Dict("key" => (1, 2))
Dict{String, Tuple{Int64, Int64}} with 1 entry:
  "key" => (1, 2)

julia> using MethodAnalysis

julia> methodinstance(Tuple{typeof(haskey), Dict{String, Any}, String}) # just for example
MethodInstance for haskey(::Dict{String, Any}, ::String)

julia> methodinstance(Tuple{typeof(haskey), Dict{String, Tuple{Int, Int}}, String})

julia> haskey(dict, "key")
true

julia> methodinstance(Tuple{typeof(haskey), Dict{String, Tuple{Int, Int}}, String})
MethodInstance for haskey(::Dict{String, Tuple{Int64, Int64}}, ::String)

julia> versioninfo()
Julia Version 1.8.0-DEV.442
Commit 897c8e607f (2021-08-29 18:44 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, tigerlake)

Of course, I know that:

julia> Dict{String, Tuple{Int, Int}} <: Dict{String, Any} 
false

julia> Dict{String, Tuple{Int, Int}} <: Dict{String}
true

So, I thought the following method would be helpful, but in reality it was not.

_haskey(@nospecialize(dict::Dict{String}), key::String) = haskey(dict, key)

I picked up the example of haskey as a simple case, and “I” don’t have any performance troubles with haskey itself. I am more interested in more general solutions than the Dict specific techniques.

1 Like
2

Dict{K,V} is essentially a Vector{Tuple{Int,K,V}}, where Int is the hash value of K. So to get the value from the vector, you must know the size of V, which requires the specialization of V.

1 Like
3

That’s a good point. However, I think it’s about the internal implementation and not the interface.

Can’t we be a little more flexible in our use of dynamic dispatching?

(As an aside, I am skeptical about the hash, key, and value being tightly coupled.)

4

I mistake the implementation of Dict. It actually stores values and keys separately (so it’s Vector{K} and Vector{V}). I have another fast implementation which stores them together. So you are right. It doesn’t depend on V.

But at least in my case, V is implicitly used, so we have to specialize on V.

5

Can you try _haskey(@nospecialize(dict::Dict{String,T} where T), key::String) = haskey(dict, key), it seems this is not specialized over different T.

6

Unfortunately, it doesn’t work, as the last three lines show. :confused:

julia> dict = Dict("key" => (1, 2))
Dict{String, Tuple{Int64, Int64}} with 1 entry:
  "key" => (1, 2)

julia> using MethodAnalysis

julia> _haskey(@nospecialize(dict::Dict{String,T} where T), key::String) = haskey(dict, key)
_haskey (generic function with 1 method)

julia> _haskey(dict, "key")
true

julia> foreach(x->occursin("(::Dict{String", string(x)) && println(x), methodinstances(haskey))
MethodInstance for haskey(::Dict{String, Base.CachedTOMLDict}, ::String)
MethodInstance for haskey(::Dict{String, Nothing}, ::String)
MethodInstance for haskey(::Dict{String, Any}, ::String)
MethodInstance for haskey(::Dict{String, Pkg.REPLMode.OptionSpec}, ::String)
MethodInstance for haskey(::Dict{String, Pkg.REPLMode.CommandSpec}, ::String)
MethodInstance for haskey(::Dict{String, Dict{String, Pkg.REPLMode.CommandSpec}}, ::String)
MethodInstance for haskey(::Dict{String, String}, ::String)
MethodInstance for haskey(::Dict{String, Function}, ::String)
MethodInstance for haskey(::Dict{String, LibGit2.AbstractCredential}, ::String)
MethodInstance for haskey(::Dict{String, Pkg.Types.Compat}, ::String)
MethodInstance for haskey(::Dict{String, Pkg.Versions.VersionSpec}, ::String)
MethodInstance for haskey(::Dict{String, Base.UUID}, ::String)
MethodInstance for haskey(::Dict{String, Bool}, ::Nothing)
MethodInstance for haskey(::Dict{String, Bool}, ::String)
MethodInstance for haskey(::Dict{String, Tuple{Int64, Int64}}, ::String)
MethodInstance for haskey(::Dict{String}, ::String)
MethodInstance for haskey(::Dict{String, <:Function}, ::String)
7

I think it’s impossible to do this using ordinary Julia (I suspect that even you break into Julia’s internal, you still can’t do it). The basic idea here is to invoke a specific method instance of haskey (namely haskey(::{Dict{String,T} where T, ::String}) and that specific method instance requires special compilation (to avoid specialization over different input types, otherwise it will still call JIT at runtime).

It’s strange that this feature doesn’t get implemented in Julia, since Julia can already infer type of haskey when input type is abstract. I always thought Julia can do this before, but it seems that this is not the case.

1 Like