haskey(Dict) allocates when key is a struct

General Usage Performance
1

Hi!

I’ve noticed that if a key in a Dict is a structure, the haskey function allocates memory:

d = Dict{Int64, Int64}()
@allocated haskey(d, 0)  # 0 when key is an Int

struct Key
    value :: Int64
end

d  = Dict{Key, Int64}()
@allocated haskey(d, Key(0)) # 16 bytes!

I’m using Julia 1.1

Is there anything I can do to avoid those allocations while still using structures as the key?
Thanks,
Kuba

2

I think this is an artifact of how @allocated works. The same with BenchmarkTools shows no allocations:

julia> using BenchmarkTools

julia> @btime haskey($d, Key(0))
  27.902 ns (0 allocations: 0 bytes)
false

julia> @btime haskey($d, 0)
  4.485 ns (0 allocations: 0 bytes)
false

(but it is a lot slower, although down at ns scale number may not mean that much).

3

Note that the worse performance has to do with how hashing is done for user-defined structs. You can define a custom hash function with

Base.hash(x::Key) = hash(x.value)

and get the same performance for haskey as integer keys.

1 Like
4

The allocations actually don’t happen in haskey at all, but because of the call to Key(0) instead. This can be safely ignored, because this will pretty much always just be on the stack.

julia> @allocated k=Key(0)
0

julia> @allocated haskey(d, k)
0
5

Yeah, that makes sense.
Thank guys!