# Performance issues when working with dict

**URL:** <https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565>\
**Category:** Performance\
**Tags:** dictionary\
**Created:** [January 13, 2022, 4:49pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565 "2022-01-13T16:49:58Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Deoch](https://avatars.discourse-cdn.com/v4/letter/d/e274bd/32.png) [@Deoch](https://discourse.julialang.org/u/Deoch)\
**Post date:** [January 13, 2022, 4:49pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/1 "2022-01-13T16:49:59Z")

</div>

Hello,

I have some performance issues with dictionnaries, and I’m unsure about how to approach this problem. I profiled my code the other day, and I found that it spent a fair amount of time (that I wasn’t expecting) on the “getindex” function when fetching values with Dict.

The dictionary have around 100 keys (of custom immutable struct), each pointing to an array of custom immutable struct. The size of these arrays vary between themselves, and during run time, with a maximum of around 1000 elements.

I don’t really know how to approach the problem. Are dict intrinsically slow, and I should use another data structure ? Or is there maybe some implementation issues on my end ? Some workaround ?

Thanks for your help

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [January 13, 2022, 4:52pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/2 "2022-01-13T16:52:59Z")

</div>

Welcome! A few more details are needed here: what are the type parameters of your dict? Is it a `Dict{Any,Any}` or a `Dict{YourCustomImmutableStruct, #= something =#}`? Have you customized hashing for your immutable struct? What are its fields?

---

<div class="post-metadata">

**Author:** ![Deoch](https://avatars.discourse-cdn.com/v4/letter/d/e274bd/32.png) [@Deoch](https://discourse.julialang.org/u/Deoch)\
**Post date:** [January 13, 2022, 5:02pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/3 "2022-01-13T17:02:28Z")

</div>

Thanks for your reply, it is a Dict{order, Array{route,1}}, with order and routes being immutable struct. The dict is created with empty arrays, that are filled during run time. The order objects have two fields: an id, and an array (less than 10 elements) of other simple immutable struct.

I don’t understand the part about customized hashing, so I guess not.

---

<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:** [January 14, 2022, 7:32am UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/4 "2022-01-14T07:32:07Z")

</div>

Are `order` and `route` concrete types, i.e. `isconcretetype(order)==true`? If not that might be part of the problem.

Concerning the hashing, see [Collections and Data Structures · The Julia Language](https://docs.julialang.org/en/v1/base/collections/#Dictionaries) and

```julia
help?> hash
search: hash hasmethod haskey hasfield hasproperty skipchars Threads MathConstants searchsortedlast

  hash(x[, h::UInt])

  Compute an integer hash code such that isequal(x,y) implies hash(x)==hash(y). The optional second argument h is a hash code to be mixed with the result.

  New types should implement the 2-argument form, typically by calling the 2-argument hash method recursively in order to mix hashes of the contents with each other (and with h). Typically,
  any type that implements hash should also implement its own == (hence isequal) to guarantee the property mentioned above. Types supporting subtraction (operator -) should also implement
  widen, which is required to hash values inside heterogeneous arrays.

```

If you implement custom hashing, consider using:  
[https://github.com/andrewcooke/AutoHashEquals.jl](https://github.com/andrewcooke/AutoHashEquals.jl)

---

<div class="post-metadata">

**Author:** ![Deoch](https://avatars.discourse-cdn.com/v4/letter/d/e274bd/32.png) [@Deoch](https://discourse.julialang.org/u/Deoch)\
**Post date:** [January 14, 2022, 3:43pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/5 "2022-01-14T15:43:06Z")

</div>

Thanks for your answers!

So I had already implemented custom methods for == and isequal with my structures, but not for hash. I did it, and the performances improved significantly.

---

<div class="post-metadata">

**Author:** ![cosmia](https://avatars.discourse-cdn.com/v4/letter/c/9de0a6/32.png) [@cosmia](https://discourse.julialang.org/u/cosmia)\
**Post date:** [November 11, 2022, 12:19am UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/6 "2022-11-11T00:19:07Z")

</div>

I’m facing a similar problem where I create a `Dict{MyType, Float64}` and fill it during runtime. Then I access this Dict many times in a loop using `MyType`.  
When I run the profiler in this loop, I see that most of the time is spent in `getindex`.

Before, my type definition was (and I had a custom hash definiton)

```julia
struct MyType{S}
    x::Vector{S}
    y::S
end

```

I followed your suggestion and made it into a concrete type and used AutoHashEquals.jl so that

```julia
@auto_hash_equals struct MyType
    x::Vector{Int64}
    x::Int64
end

```

but performance has barely changed and the output from the profiler looks basically the same.

I know it is very difficult to troubleshoot without a MWE, but is there any other reason this could be happening?

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [November 11, 2022, 3:44pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/7 "2022-11-11T15:44:09Z")

</div>

> [@cosmia](#):
>
> Dict{MyType, Float64}

According to your description, `MyType` in `Dict{MyType, Float64}` is incompletely specified and will result in a performance penalty. Try `Dict{MyType{Float64}, Float64}` (or whatever type you’re using for `S`). For maximum performance, you’ll also likely need to define `Base.hash(::MyType,::UInt)` as discussed in the earlier replies.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [November 11, 2022, 4:39pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/8 "2022-11-11T16:39:39Z")

</div>

I think the issue you’re seeing is that hashing `MyType` (with auto\_hash\_equals too) involves hashing each of its individual fields. That, in turn, means hashing the `Vector{Int64}` field, and hashing a vector requires iterating over the vector and hashing all of the elements (for very long vectors it doesn’t hash _all_ the elements, but it still does a lot of hashing). That’s a lot of work that has to be done every time you check any key in the dictionary.

I haven’t found a really satisfying answer to this. For keys you don’t plan to mutate, I’ve found it convenient to make the hash a field of the type (constructed automatically in the inner constructor) and then do `Base.hash(x::MyType, y::UInt) = x.hash`

---

<div class="post-metadata">

**Author:** ![cosmia](https://avatars.discourse-cdn.com/v4/letter/c/9de0a6/32.png) [@cosmia](https://discourse.julialang.org/u/cosmia)\
**Post date:** [November 11, 2022, 8:34pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/9 "2022-11-11T20:34:56Z")

</div>

Thank you for your answer! My `Vector{Int64}` is actually just a 3-element vector, so I think I might as well just separate it into individual elements and see if performance improves.

However, if you have the time, could you elaborate a little bit on your partial solution? What do you mean exactly by making the hash a field of the type?

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [November 11, 2022, 8:43pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/10 "2022-11-11T20:43:34Z")

</div>

> [@cosmia](#):
>
> My `Vector{Int64}` is actually just a 3-element vector

Consider `using StaticArrays` and then the `SVector{3,Int64}` type instead of `Vector{Int64}`. `SVector`s provide really exceptional performance for small fixed-size arrays and won’t require you to re-implement any array logic or math with your custom type. If you don’t need it to have linear algebraic behavior, you could also just use a `NTuple{3,Int64}` to avoid the dependency on `StaticArrays` while achieving this performance. Either of these should save you from needing to implement your own hashing or other stuff.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [November 15, 2022, 6:00pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/11 "2022-11-15T18:00:50Z")

</div>

> [@cosmia](#):
>
> However, if you have the time, could you elaborate a little bit on your partial solution? What do you mean exactly by making the hash a field of the type?

Oh, the idea was basically to add a `hash::UInt` field to the `struct` itself. I then compute that value (by hashing the other fields as usual) inside the inner constructor, and then I make `Base.hash(x::MyType, seed::UInt) = hash(x.hash, seed)`. Something like:

```julia
julia> struct MyType
         x::NTuple{3, Int}
         hash::UInt
         
         MyType(x) = new(x, hash(x))
       end

julia> Base.hash(m::MyType, seed::UInt) = hash(m.hash, seed)

```

The key being that you now only call `hash(x)` once at construction time, rather than every time you hash the struct.

This only works if you _actually_ avoid mutating the contents of the struct after construction time and if you also define `==` to be consistent with `hash`, so I’m not convinced it’s a great idea.

---

<div class="post-metadata">

**Author:** ![Deoch](https://avatars.discourse-cdn.com/v4/letter/d/e274bd/32.png) [@Deoch](https://discourse.julialang.org/u/Deoch)\
**Post date:** [November 16, 2022, 2:05pm UTC](https://discourse.julialang.org/t/performance-issues-when-working-with-dict/74565/12 "2022-11-16T14:05:02Z")

</div>

(OP here) what I did to solve my problem was to define custom functions for ==, isequal and hash. The getindex was still a bit slow, but it wasn’t the bottleneck anymore. Since my structures are immutable, I can just give them a unique ID, as a field of the structure. For a structure called loc (used as keys of my dict) I just added this piece of code:

`Base.:(==)(a::loc,b::loc) = (a.id == b.id)`  
`Base.isequal(a::loc,b::loc) = isequal(a.id, b.id)`  
`Base.hash(a::loc, h::UInt) = hash(a.id, hash(:loc,h))`

I hope it works for you.