Performance issues when working with dict

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

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?

1 Like

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.

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 and

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:

1 Like

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.

4 Likes