Why don't Julia dictionaries preserve order?

dictionary

#1

Hey all, I have been working on a project and it is the first time I have used Dictionaries heavily. I noticed that Julia dictionaries do not preserve order of insertion and that it was causing problems in my code. I am now using OrderedDict from DataStructures, but I am curious as to why it does not? I see that in Python, they changed it so that the standard Dictionary also preserves order. Is it a performance issue?

Maybe it is not optimal to use Dictionaries in projects that are order sensitive, but still, it begs the question as to why.

Thanks!


#2

That’s a long story.

TL/DR: performance/tradeoffs/interfaces/deciding if we want to allow folks to depend upon the iteration order/and finally, developer resources/priorities.


#3

Just to add to @mbauman

An unordered large dict of bitstype will typically need one round-trip to main memory per access. If it were ordered you wait for two round-trips. If your code is nice for the branch-predictor then your CPU can speculatively trigger the next lookups while waiting for the last element.

Languages like python have an extra indirection anyway, so this does not matter as much.

Otoh, you can save a lot of memory if your keys or values are large bitstypes; and if your dict is small enough to maybe fit into L3 then the ordered dict might even be faster.


#4

If you want a dict that is order-preserving, consider OrderedCollections.


#5

Thanks a lot for this info! I was going to complain that it is annoying to have to depend on DataStructures just to have an OrderedDict (like Interact currently does) when actually that’s not needed at all and OrderedCollections is a tiny dependency.