# Performance of Dictionaries.jl vs Base.Dict

**URL:** <https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073>\
**Category:** Internals & Design\
**Tags:** package, performance, dictionary, dictionaries\
**Created:** [December 22, 2022, 4:58pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073 "2022-12-22T16:58:03Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![ParadaCarleton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paradacarleton/32/20005_2.png) [@ParadaCarleton](https://discourse.julialang.org/u/ParadaCarleton)\
**Post date:** [December 22, 2022, 4:58pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/1 "2022-12-22T16:58:03Z")

</div>

Lots of places; Dictionaries.jl’s packages are just _much_ faster than Base `Dict`s to iterate over. There’s a reason most package designers use them rather than `Dict`s.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 23, 2022, 9:53pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/2 "2022-12-23T21:53:44Z")

</div>

I would be very interested in seeing a direct benchmark showing that Dict is five times slower than Dictionaries.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [December 24, 2022, 1:58am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/3 "2022-12-24T01:58:59Z")

</div>

> [@StefanKarpinski](#):
>
> I would be very interested in seeing a direct benchmark showing that Dict is five times slower than Dictionaries.

Using my benchmark above, it seems that `Dictionary` is _slower_ than `Dict` for `getindex` (`mul1!` benchmark), but faster for iterating over `pairs(dict)` (`mul2!` benchmark).

In particular, this code:

> **Code**
>
> ```julia
> function mul1!(y, D, x)
> for i = 1:length(y)
> s = zero(eltype(y))
> @inbounds for j = 1:length(x)
> s += D[CartesianIndex((i,j))] * x[j]
> end
> y[i] = s
> end
> return y
> end
> 
> function mul2!(y, D, x)
> y .= 0
> for (k,v) in pairs(D)
> i,j = Tuple(k)
> @inbounds y[i] += v * x[j]
> end
> return y
> end
> 
> using Dictionaries, BenchmarkTools
> A = rand(1000,1000)
> x = rand(1000)
> y = similar(x)
> D = Dict(pairs(A))
> D2 = Dictionary(D)
> 
> ```

gives:

```julia
julia> @btime mul1!($y, $D, $x); @btime mul1!($y, $D2, $x);
  67.968 ms (0 allocations: 0 bytes)
  110.422 ms (0 allocations: 0 bytes)

julia> @btime mul2!($y, $D, $x); @btime mul2!($y, $D2, $x);
  9.907 ms (0 allocations: 0 bytes)
  1.897 ms (0 allocations: 0 bytes)

```

If you look at the way `Dictionary` is implemented, it has separate _contiguous_ arrays of the keys and values in the dictionary, which makes it fast to iterate, at the expense of an additional indirection during `getindex` (via a separate array of indices into the contiguous data).

---

<div class="post-metadata">

**Author:** ![ParadaCarleton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paradacarleton/32/20005_2.png) [@ParadaCarleton](https://discourse.julialang.org/u/ParadaCarleton)\
**Post date:** [December 24, 2022, 2:09am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/4 "2022-12-24T02:09:17Z")

</div>

cc @andyferris

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [December 24, 2022, 5:59am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/5 "2022-12-24T05:59:27Z")

</div>

Yes. I think Andy writes about this in several places.  
Like in [Getting Started](https://github.com/andyferris/Dictionaries.jl#getting-started) in the README.

> The three main difference to `Dict` are that it preserves the order of elements, it iterates much faster, and it iterates values rather than key-value pairs.

His [JuliaCon talk](https://www.youtube.com/watch?v=Y-hAZcqAw28) is very clear.

If you do a lot of insertion and deletion and not much iterating over keys and values, then `Dict` might be faster. If you do a lot of iterating, and not so much insertion and deletion, then `Dictionary`

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 25, 2022, 5:05pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/6 "2022-12-25T17:05:49Z")

</div>

Ah yes, that’s a known trade off for ordered dicts—iteration gets much faster but other operations get a bit slower. Describing that as “Dictionaries are five times faster than Dict” is a bit misleading.

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [December 25, 2022, 6:41pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/7 "2022-12-25T18:41:01Z")

</div>

Dictonaries.jl also has the [tokens](https://github.com/andyferris/Dictionaries.jl#tokens) API which helps with performance.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 25, 2022, 6:45pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/8 "2022-12-25T18:45:31Z")

</div>

yeah, we really need to add the token API to base.

---

<div class="post-metadata">

**Author:** ![uniment](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/uniment/32/24532_2.png) [@uniment](https://discourse.julialang.org/u/uniment)\
**Post date:** [December 25, 2022, 8:24pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/9 "2022-12-25T20:24:08Z")

</div>

For a less-gifted individual like me, can you offer a basic example of how to use tokens and how they help?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 25, 2022, 8:29pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/10 "2022-12-25T20:29:51Z")

</div>

The idea of a token is that a lot of the time people will write code like the following

```julia
D = get_random(dict)
if !(a in keys(D))
    D[a] = 1
end

```

This looks decent, but requires doing a duplicate lookup in `D`. Using a token will save a call to `hash(a)` and may save some lookup costs.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 25, 2022, 8:44pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/11 "2022-12-25T20:44:47Z")

</div>

There is `get!` for that pattern. It’s more when you want to update an existing index `D[a] += 1` where I don’t think there is a good way to do it now without double lookup.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 25, 2022, 8:57pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/12 "2022-12-25T20:57:02Z")

</div>

`get!` can be used for my case, but since it isn’t lazy it sometimes isn’t a good option.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 25, 2022, 11:46pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/13 "2022-12-25T23:46:39Z")

</div>

There’s a lazy method where the value is computed by a function call.

---

<div class="post-metadata">

**Author:** ![fingolfin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fingolfin/32/6033_2.png) [@fingolfin](https://discourse.julialang.org/u/fingolfin)\
**Post date:** [December 26, 2022, 12:01am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/14 "2022-12-26T00:01:55Z")

</div>

AFAIK there is no great way to se a Base.Dict to implement a “lazy accumulator”, like this:

```julia
   if haskey(dict, key)
    dict[key] += 1
  else
    dict[key] = 1
  end

```

This needs three lookups. We can reduce this to two via `get!`:

```julia
    dict[key] = 1 + get!(dict, key, 0)

```

But I am not aware of way to get it down to 1 (if there is one, I’d love to learn about it).

---

<div class="post-metadata">

**Author:** ![ToucheSir](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/touchesir/32/14411_2.png) [@ToucheSir](https://discourse.julialang.org/u/ToucheSir)\
**Post date:** [December 26, 2022, 12:05am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/15 "2022-12-26T00:05:48Z")

</div>

[Add modify! function for lookup/update/insert/delete in one go by tkf · Pull Request #33758 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/33758) enables this, and to my understanding is a reason why a token-based API doesn’t currently exist in Base. Maybe the current thread will reignite efforts on landing one of the two approaches.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 26, 2022, 1:06am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/16 "2022-12-26T01:06:49Z")

</div>

> [@fingolfin](#):
>
> But I am not aware of way to get it down to 1

Neither was I… but now I think the following `incrementkey!` does it:

```julia
using OrderedCollections

incrementkey!(d, k) = ( mergewith!(+, d, LittleDict((k,), (1,))) ;nothing)
classic_incrementkey!(d, k) = ( d[k] = 1 + get!(d, k, 0) ;nothing)

```

A little test:

```julia
julia> using BenchmarkTools

julia> d = Dict(4=>5, 3=>0, 1=>2);

julia> @btime incrementkey!($d, 3)
  10.763 ns (0 allocations: 0 bytes)

julia> @btime classic_incrementkey!($d, 3)
  14.533 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [December 26, 2022, 3:10pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/17 "2022-12-26T15:10:38Z")

</div>

The last time I looked into it (a long time ago), you have to go behind the API for `Dict`. Whereas (as discussed above) avoiding looking up twice is part of the API for `Dictionary`. I wrote some things towards giving `Dict` and `Dictionary` a common interface here [DictTools.jl](https://github.com/jlapeyre/DictTools.jl). In one place, it avoids computing the hash twice [like this](https://github.com/jlapeyre/DictTools.jl/blob/d24a11201d331043cd2eacb20e1ef4aa5efd9df9/src/DictTools.jl#L139-L156)

```julia
@inline function update!(dict::AbstractDictionary{T, V}, _key::T, func::F, default) where {F, T, V}
    (hasval, token) = gettoken(dict, _key)
    if hasval
        settokenvalue!(dict, token, func(gettokenvalue(dict, token)))
    else
        insert!(dict, _key, default)
    end
end

# Stolen from StatsBase. This is faster than naive method
@inline function update!(dict::Dict{T, V}, _key::T, func::F, default) where {F, T, V}
    index = Base.ht_keyindex2!(dict, _key)
    if index > 0
        @inbounds dict.vals[index] = func(dict.vals[index])
    else
        @inbounds Base._setindex!(dict, default, _key, -index)
    end
end

```

After using `DictTools.jl`, I think that in general trying to use a common interface is too much trouble.

But one of the main reasons that Andy wrote `Dictionaries` is to provide an associative array with an `AbstractArray`-like interface. I _have_ found this useful. It is much easier to write a generic function that will take either a `Vector` or a `Dictionary`.

I first started `DictTools` for a couple of things: Provide a count map for `Dict` that accepts an iterator, rather than just a `AbstractVector`. Provide a count map for `Dictionary`. It’s natural to try to abstract part of this away with a common interface to the two implementations of dictionaries. And then to support `Vector` as well.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 28, 2022, 12:51am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/18 "2022-12-28T00:51:00Z")

</div>

Fwiw, adding a token API to Dict would be a reasonable thing. Someone just need to make a proposal/implementation. Could be based on Dictionaries.

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [December 30, 2022, 7:08am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/19 "2022-12-30T07:08:24Z")

</div>

Agreed - there’s a lot of `AbstractDict` API work that could happen in `Base` without breaking changes.

---

<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:** [December 30, 2022, 3:36pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/20 "2022-12-30T15:36:47Z")

</div>

A post was split to a new topic: [Dictionary.jl’s token API](https://discourse.julialang.org/t/dictionary-jls-token-api/92318)

[Next page](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073.md?page=2)