# haskey(Dict) allocates when key is a struct

**URL:** <https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093>\
**Category:** Performance\
**Created:** [December 10, 2019, 11:17am UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093 "2019-12-10T11:17:07Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![kuba](https://avatars.discourse-cdn.com/v4/letter/k/a587f6/32.png) [@kuba](https://discourse.julialang.org/u/kuba)\
**Post date:** [December 10, 2019, 11:17am UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093/1 "2019-12-10T11:17:07Z")

</div>

Hi!

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

```julia
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

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [December 10, 2019, 11:21am UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093/2 "2019-12-10T11:21:44Z")

</div>

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

```julia
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).

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [December 10, 2019, 11:38am UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093/3 "2019-12-10T11:38:27Z")

</div>

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

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

```

and get the same performance for `haskey` as integer keys.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [December 10, 2019, 12:01pm UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093/4 "2019-12-10T12:01:35Z")

</div>

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
julia> @allocated k=Key(0)
0

julia> @allocated haskey(d, k)
0

```

---

<div class="post-metadata">

**Author:** ![kuba](https://avatars.discourse-cdn.com/v4/letter/k/a587f6/32.png) [@kuba](https://discourse.julialang.org/u/kuba)\
**Post date:** [December 10, 2019, 12:52pm UTC](https://discourse.julialang.org/t/haskey-dict-allocates-when-key-is-a-struct/32093/5 "2019-12-10T12:52:30Z")

</div>

Yeah, that makes sense.  
Thank guys!