# \[ANN\] Dictionaries.jl - Improved productivity and performance of dictionaries in Julia
**URL:** https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074
**Category:** Package Announcements
**Tags:** dictionary, dictionaries
**Created:** [December 9, 2019, 10:42pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074 "2019-12-09T22:42:50Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 9, 2019, 10:42pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/1 "2019-12-09T22:42:50Z")
I am pleased to announce the recent release of [Dictionaries.jl](https://github.com/andyferris/Dictionaries.jl), which provides an alternative interface for dictionaries in Julia, for improved productivity and performance. You can install it with `]add Dictionaries` at the REPL.
The high-level goal of this package is to define a new interface for dictionary and set structures which is convenient and efficient for functional data manipulation - including operations such as non-scalar indexing, broadcasting, mapping, filtering, reducing, grouping, and so-on. While Julia comes with built-in `AbstractDict` and `AbstractSet` supertypes, the interfaces for these are not as well established or generic as for `AbstractArray` , the built-in dictionaries implement less of the common data manipulation operations compared to arrays, and it is difficult to work with them in a performant manner.
In this package we aim to devise a cohesive interface for abstract dictionaries (or associative maps), having the common supertype `AbstractDictionary` . A large part of this is working with indices (of arbitrary type) as well as convenient and efficient iteration of the containers. A second goal is to make dictionary manipulation more closely resemble array manipulation, to make it easier for users. Simultaneously, we are pushing the performance of working with dictionaries to be closer to that of working with arrays.
The largest departure from `Base.AbstractDict` that users should be aware of is that dictionaries here iterate values, not key-value pairs. In return, you get the convenience of using your usual tools for arrays, and some performance gains.
For a very small taste of how the _Dictionaries.jl_ interface can lead to performance improvements during an analytic workflow, consider the following example where we attempt to add `1` to the values of a hash-based dictionary. Not only is this easier for the programmer (using broadcast notation) but is also much more performant than the typical pattern with `Base.Dict`. Of course, `map`, `reduce`, `filter` and friends all work out-of-the-box, too.
```julia
julia> using Dictionaries, BenchmarkTools
julia> dictionary = HashDictionary(rand(Int64, 10_000_000), rand(Int64, 10_000_000));
julia> @btime dictionary .+ 1;
135.975 ms (22 allocations: 256.00 MiB)
julia> dict = Dict(rand(Int64) => rand(Int64) for _ in 1:10_000_000);
julia> @btime Dict(k => v+1 for (k,v) in dict);
10.283 s (73 allocations: 541.17 MiB)
```
(Note - the thing impacting performance most here is that the `Dict` is constructed by inserting the elements and iteratively building a new hashmap, while broadcasting over the `HashDictionary` preserves the keys and hashmap, creating only new values in the valid slots).
This is a young package, and contributions are of course very welcome. I am currently working on integrating this with [SplitApplyCombine.jl](https://github.com/JuliaData/SplitApplyCombine.jl), particularly such that the `group` family of functions return a _Dictionaries.jl_ dictionary.
For Julia `Base` developers, this package combines the ideas discussed during Julia 1.0 development, particulary the Juleps [#24019](https://github.com/JuliaLang/julia/issues/24019) and [#25904](https://github.com/JuliaLang/julia/issues/25904), the (unmerged) PRs [#24508](https://github.com/JuliaLang/julia/pull/24508) and [#25013](https://github.com/JuliaLang/julia/pull/25013), the non-scalar indexing proposal [#30845](https://github.com/JuliaLang/julia/issues/30845) , the discussion of dictionary iteration in [#22194](https://github.com/JuliaLang/julia/pull/22194) and a variety of other work which was merged at that time.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 9, 2019, 11:06pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/2 "2019-12-09T23:06:26Z")
> [@andyferris](#):
>
> dictionary .+ 1
What does that mean?
---
### Author:  [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)
#### Post date: [December 9, 2019, 11:08pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/3 "2019-12-09T23:08:12Z")
Plus one to all values. Did you read the text?
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 9, 2019, 11:09pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/4 "2019-12-09T23:09:30Z")
It broadcasts (maps) over the values but preserves the keys. Like this:
```julia
julia> d = HashDictionary(["a", "b", "c"], [1, 2, 3])
3-element HashDictionary{String,Int64}
"c" │ 3
"b" │ 2
"a" │ 1
julia> d .+ 1
3-element HashDictionary{String,Int64}
"c" │ 4
"b" │ 3
"a" │ 2
```
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [December 9, 2019, 11:09pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/5 "2019-12-09T23:09:47Z")
afaiu it creates a new dictionary that has the same hashmap as the old one, just incremented values
EDIT sorry crosspost, but deleting now is annoying in discourse so just ignore
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 9, 2019, 11:23pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/6 "2019-12-09T23:23:20Z")
> [@carstenbauer](#):
>
> Did you read the text?
missed it while I skimmed it
---
### Author:  [@Ratingulate](https://discourse.julialang.org/u/Ratingulate)
#### Post date: [December 10, 2019, 2:56am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/7 "2019-12-10T02:56:00Z")
Cool. There’s a tension right now between compile cruft and performance (DF vs indexed tables). Do you see this improving on that tradeoff?
How far does the performance go? Can this interface generalize arrays and serve as a named dim array if wrapped in an abstract array struct?
---
### Author:  [@StevenSiew](https://discourse.julialang.org/u/StevenSiew)
#### Post date: [December 10, 2019, 3:11am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/8 "2019-12-10T03:11:03Z")
I have exactly 1.3 questions to ask.
Is this Dictionary Thread Safe?
---
### Author:  [@c42f](https://discourse.julialang.org/u/c42f)
#### Post date: [December 10, 2019, 4:30am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/9 "2019-12-10T04:30:38Z")
Thread safe in what way? If you’re looking for a dictionary which is thread safe for parallel insertions and deletions you won’t find it in Dictionaries.jl for the same reason it’s not in Base — the overhead would be too high for single threaded use (see also [Can dicts be threadsafe? - #6 by StefanKarpinski](https://discourse.julialang.org/t/can-dicts-be-threadsafe/27172/6))
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 10, 2019, 4:41am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/10 "2019-12-10T04:41:09Z")
> Is this Dictionary Thread Safe?
Good question!
The `HashDictionary` is implemented the same as (i.e. the code is copied from) `Base.Dict`, but without the allowances for `WeakKeyDict`. Neither mutating its keys nor reading from it, while some other thread mutates its keys, would be safe at all. (I.e. use the rust rules when sharing it).
It makes me wonder… the `AbstractDictionary` interface is pretty generic, but the token stuff doesn’t necessarily support atomic key-and-value updates - this probably bears some further thought! There’s nothing stopping you creating a non-tokenized dictionary with appropriate safeguards though.
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 10, 2019, 4:50am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/11 "2019-12-10T04:50:30Z")
> How far does the performance go? Can this interface generalize arrays and serve as a named dim array if wrapped in an abstract array struct?
I think so? Thinking about multidimensional dictionaries is something I’d like to do in the future. The interface should be pretty low overhead and ammenable to compiler optimizations/zero-cost abstractions, like `AbstractArray`. It’s possible that inlining immutable references to the heap will help a little bit ([https://github.com/JuliaLang/julia/pull/33886](https://github.com/JuliaLang/julia/pull/33886)).
> Cool. There’s a tension right now between compile cruft and performance (DF vs indexed tables). Do you see this improving on that tradeoff?
So this is about say “strongly typed” tables vs “weakly typed” dataframes? This probably doesn’t contribute a whole lot to that… just like `AbstractArray`, `AbstractDictionary` has a type parameter for a uniform `eltype`. That said, I suspect you could create a “static dictionary” with inference working out fine, which would be an interesting experiment (possibly just need to unroll the loop for `getindex` on `Dictionary` containing tuples, and hope constant propagation works for the keys tuple… unfortunately I’m not sure what “guarantees” the compiler provides for constant propagation).
---
### Author:  [@tim.holy](https://discourse.julialang.org/u/tim.holy)
#### Post date: [December 10, 2019, 1:48pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/12 "2019-12-10T13:48:30Z")
Really nice to see this come to life!
---
### Author:  [@pontus](https://discourse.julialang.org/u/pontus)
#### Post date: [December 10, 2019, 3:10pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/13 "2019-12-10T15:10:29Z")
> [@andyferris](#):
>
> Thinking about multidimensional dictionaries is something I’d like to do in the future.
Not sure if you’ve seen the package `DataCubes.jl`which provides `DictArray`, a multidimensional array whose element type is an ordered dictionary with common keys, and `LabeledArray`, a multidimensional array consisting of base and axes?
It hasn’t been maintained for a couple of years, looks as if last update was for Julia v0.6. It is MIT Licensed, and perhaps will give some ideas for when you’re ready to move in that direction?
> **[GitHub - c-s/DataCubes.jl: Multidimensional table processing tool](https://github.com/c-s/DataCubes.jl)**
>
> Multidimensional table processing tool. Contribute to c-s/DataCubes.jl development by creating an account on GitHub.
also has nice documentation:
[http://c-s.github.io/DataCubes.jl/introduction](http://c-s.github.io/DataCubes.jl/introduction)
Thanks for your efforts with this package!
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [December 11, 2019, 9:44am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/14 "2019-12-11T09:44:50Z")
Thanks, this is a great work on re-designing a coherent interface of dictionary!
I find the design choice that `dict[key] = value` means strict update interesting… in the sense I am so used to it to mean “upsert” it’s a bit hard to imagine how reading/writing code would be like. But I think I get the analogy to arrays and consistency with other parts of the interface.
In [Dictionaries with the same indices](https://github.com/andyferris/Dictionaries.jl#dictionaries-with-the-same-indices), you are mentioning that
> The `similar` function is used to create a dictionary with defined indices, but undefined values that can be set/mutated after the fact. `similar(dict, T)` creates a container with the same indices as `dict` and, optionally, a new element type.
I suppose this is intentionally like this also for broadcasting and mapping?:
```julia
julia> d1 = HashDictionary(["a", "b", "c"], [1, 2, 3])
3-element HashDictionary{String,Int64}
"c" │ 3
"b" │ 2
"a" │ 1
julia> d2 = d1 .+ 1
3-element HashDictionary{String,Int64}
"c" │ 4
"b" │ 3
"a" │ 2
julia> keys(d1) === keys(d2)
true
```
However, it feels undesirable property to me that `insert!`ing one of the dictionary mutates other ones that share the indices:
```julia
julia> insert!(d2, "d", 5)
4-element HashDictionary{String,Int64}
"c" │ 4
"b" │ 3
"a" │ 2
"d" │ 5
julia> d1
4-element HashDictionary{String,Int64}
"c" │ 3
"b" │ 2
"a" │ 1
"d" │ 0
```
Is there a plan to “fix” this (or is this expected)? Maybe using copy-on-write indices? Immutable/persistent data structure?
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 11, 2019, 1:14pm UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/15 "2019-12-11T13:14:35Z")
> I find the design choice that `dict[key] = value` means strict update interesting… in the sense I am so used to it to mean “upsert” it’s a bit hard to imagine how reading/writing code would be like. But I think I get the analogy to arrays and consistency with other parts of the interface.
Yes this one is quite interesting. I fretted over this one for a while, but I did use _Dictionaries.jl_ for a little while for some “real” work before releasing, and honestly I never missed this. On the other hand, the feeling of certainty that the keys aren’t shifting under you while you are mutating values is quite comforting and very much seemed worth it to me (and `set!` is a nice partner to `get!`).
> I suppose this is intentionally like this also for broadcasting and mapping?:
Yeah, generic functions delegate to `similar` and `empty` as factories to materialize new containers, so anything that preserves keys ends up going through `similar`. This is quite nice because I found I frequently ended up using fast co-iteration with the input and output, and also I rarely (if ever?) needed to mutate the keys of the output in practice.
> Is there a plan to “fix” this (or is this expected)? Maybe using copy-on-write indices? Immutable/persistent data structure?
Yes, they are both valid options. My personal favorite is `freeze` from [#31630](https://github.com/JuliaLang/julia/pull/31630) - I’d possibly have a `freezekeys` or `freezeindices` thing that you call first in order to get what is the current behavior, and revert `similar` on mutable keys to making a copy. We _should_ fix this, for sure - but I feel this is the **exact** same problem with `SubArray` (mutating the indexer part can cause segfaults, since the bounds check on the indexer values are done at construction time, and the same goes for resizing the indexee) which we should fix first (and using `freeze` on the indexer and `freezekeys` on the indexee is only the way to achieve that which I have thought of, while I’m hoping the compiler can realize copying is a not needed in the majority of cases via escape analysis/rust-style borrow checker) . Currently as it stands, consider _Dictionaries.jl_ to be a [sharp tool](https://schneems.com/2016/08/16/sharp-tools.html).
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [December 12, 2019, 12:01am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/16 "2019-12-12T00:01:08Z")
> [@andyferris](#):
>
> I’d possibly have a `freezekeys` or `freezeindices` thing that you call first in order to get what is the current behavior, and revert `similar` on mutable keys to making a copy.
Does it mean there would be (say) `MutableIndices` and `FrozenIndices` types? Reading your comments in #31630, I now can see that it’d work quite nicely with `dict[key] = value` being strict update; i.e., only dictionaries with `MutableIndices` support `insert!` while both types of dictionary support `dict[key] = value`.
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 12, 2019, 2:56am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/17 "2019-12-12T02:56:37Z")
We could make our own types, yes. Or else wait for frozen arrays and freeze the arrays underlying the hashmap. I’m looking for feedback on this one, actually, so opinions welcome.
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [December 12, 2019, 4:00am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/18 "2019-12-12T04:00:57Z")
Skimming #31630, I thought you can just go ahead and define custom mutable and immutable indices types for now and then swap its internal based on `Base.freeze`/`Base.melt`, once #31630 is merged. (And also maybe add `unsafe_freeze` API to do “manual borrow checker” to avoid copying until #31630 arrives?) This, of course, relies on that the design of #31630 does not deviate much from the current version. But do you see pitfalls other than that?
---
### Author:  [@Zach\_Christensen](https://discourse.julialang.org/u/Zach_Christensen)
#### Post date: [December 12, 2019, 11:09am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/19 "2019-12-12T11:09:57Z")
A while ago I started looking at improving indexing for some personal projects. The thing I got stuck on was the need to have distinct static and mutable ranges, which is why I developed [https://github.com/Tokazama/StaticRanges.jl](https://github.com/Tokazama/StaticRanges.jl). I’ve also been trying to get the filtering/find/search stuff optimized for it too. This would only help with an index that can be conceptualized as a range, but I think that’s the most common use case (at least for me).
If you’re interested in using it I’d love to take a look at integrating it with Dictionaries.jl. It’s not fully optimized yet but I’ve included nearly all the tests on ranges in base and added many others to test some of the novel functionalities.
---
### Author:  [@anon92994695](https://discourse.julialang.org/u/anon92994695)
#### Post date: [December 12, 2019, 11:19am UTC](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074/20 "2019-12-12T11:19:46Z")
It’s efforts like these, and say DataStructures.jl that I feel should just be included in Base Julia. Then again, I see why they aren’t, but now that I think about it, no I don’t. Awesome idea though!
[Next page](https://discourse.julialang.org/t/ann-dictionaries-jl-improved-productivity-and-performance-of-dictionaries-in-julia/32074.md?page=2)