# 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:** 13\
**Page:** 2

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 10:07am UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/21 "2024-12-13T10:07:56Z")

</div>

I tried to use Dictionares instead of the basic Dict, but keeping the same structure, in [this elegant script by @Daniel\_Gonzalez](https://julialang.zulipchat.com/#narrow/channel/469479-advent-of-code-.282024.29/topic/Day.2011) that solves the problem of the AOC 2024 d11, but I got no improvements.

I don’t know if the failure is due to a clumsy application of the Dictionares.jl package or if the script needs to be changed to take advantage of the package’s features.  
I hope someone else will succeed in doing so.

> **one SOL od d11 AOC 2024**
>
> ```julia
> const NO_STONE = -1 # folks, we're writing old school C today
> 
> stones = split(readlines("2024/inputs/day11.txt") |> only, " ") .|> x -> parse(Int, x)
> 
> number_of_digits(x) = floor(Int, log10(x)) + 1
> 
> function blink(stone::Integer)
> stone == 0 && return (1, NO_STONE)
> n = number_of_digits(stone)
> iseven(n) && return divrem(stone, 10^(n ÷ 2))
> (stone * 2024, NO_STONE)
> end
> 
> function solve(stones, n)
> d = Dict{Int64,Int64}()
> for s ∈ stones
> d[s] = 1
> end
> for _ in 1:n
> d_n = Dict{Int64,Int64}()
> for (s, n) ∈ d
> for s2 ∈ blink(s)
> s2 == NO_STONE && continue
> if haskey(d_n, s2)
> d_n[s2] += n
> else
> d_n[s2] = n
> end
> end
> end
> d = d_n
> end
> sum(values(d))
> end
> 
> solve(stones, 25)
> solve(stones, 75)
> 
> ```

For those who want to try, I leave the input to use in the tests

```julia
stones=[4610211, 
       4,
       0,
      59,
    3907,
  201586,
     929,
   33750]

```

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [December 13, 2024, 12:14pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/22 "2024-12-13T12:14:38Z")

</div>

Since the posters above seem to suggest that Dictionaries.jl is faster for iteration but possibly slower for random access, it’s normal to not expect a speedup for your code which involves random access of the `d_n` Dict.

Having said that, the following part your code could potentially be made faster if the code can be rewritten to take advantage of a token API for avoiding repeated hash computations:

> [@rocco\_sprmnt21](#):
>
> ```julia
> if haskey(d_n, s2)
> d_n[s2] += n
> else
> d_n[s2] = n
> end
> 
> ```

---

<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 13, 2024, 1:44pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/23 "2024-12-13T13:44:31Z")

</div>

Another version of `solve` saving hash calculation using `mergewith!`:

```julia
using OrderedCollections

function solve(stones, n)
    d_new = Dict{Int,Int}()
    d_old = Dict(stones .=> 1)
    for _ in 1:n
        for (s, n) ∈ d_old
            t1, t2 = blink(s)
            mergewith!(+, d_new,
              t2 == NO_STONE ? LittleDict((t1,),(n,)) : 
                               LittleDict((t1,t2),(n,n)))
        end
        d_old, d_new = d_new, d_old
        empty!(d_new)
    end
    sum(values(d_old))
end

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 3:17pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/24 "2024-12-13T15:17:20Z")

</div>

If I did not measure badly, the performance does not improve. On the contrary …

```julia
julia> @btime solve(stones, 25) # 260 us
  3.339 ms (13913 allocations: 1.56 MiB)
197357

julia> @btime solve(stones, 75) # 12ms
  155.595 ms (516906 allocations: 49.95 MiB)
234568186890978

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 3:35pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/25 "2024-12-13T15:35:30Z")

</div>

I apologize for bringing up these old messages, but for me, and perhaps for others too, they are of current interest.  
I tried to use the instructions of the update function!() but I get no improvements.  
Maybe I apply it wrong

```julia
julia> function solve(stones, n)
           d = Dict{Int64,Int64}()
           for s ∈ stones
               d[s] = 1
           end
           for _ in 1:n
               d_n = Dict{Int64,Int64}()
               for (s, n) ∈ d
                   for s2 ∈ blink(s)
                       s2 == NO_STONE && continue
                       index = Base.ht_keyindex2!(d_n, s2)
           if index > 0
               @inbounds d_n.vals[index] += n # = func(dict.vals[index])
           else
               @inbounds Base._setindex!(d_n, n, s2, -index)
           end
                       # if haskey(d_n, s2)
                       # d_n[s2] += n
                       # else
                       # d_n[s2] = n
                       # end
                   end
               end
               d = d_n
           end
           sum(values(d))
       end
solve (generic function with 1 method)

julia> solve(stones, 25)
197357

julia> solve(stones, 75)
234568186890978

julia> @btime solve(stones, 25) # 260 us
  635.100 μs (9800 allocations: 496.95 KiB)
197357

julia> @btime solve(stones, 75) # 12ms
  29.340 ms (590514 allocations: 23.42 MiB)
234568186890978

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 3:51pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/26 "2024-12-13T15:51:43Z")

</div>

In the case of this script, using get!() does not improve the situation.

```julia
julia> function solve(stones, n)
           d = Dict{Int64,Int64}()
           for s ∈ stones
               d[s] = 1
           end
           for _ in 1:n
               d_n = Dict{Int64,Int64}()
               for (s, n) ∈ d
                   for s2 ∈ blink(s)
                       s2 == NO_STONE && continue
                       d_n[s2] = n + get!(d_n, s2, 0)
                       # index = Base.ht_keyindex2!(d_n, s2)
                       # if index > 0
                       # @inbounds d_n.vals[index] += n # = func(dict.vals[index])
                       # else
                       # @inbounds Base._setindex!(d_n, n, s2, -index)       
                       # end
                       # if haskey(d_n, s2)
                       # d_n[s2] += n
                       # else
                       # d_n[s2] = n
                       # end
                   end
               end
               d = d_n
           end
           sum(values(d))
       end
solve (generic function with 1 method)

julia> @btime solve(stones, 25) # 260 us
  593.500 μs (8490 allocations: 476.48 KiB)
197357

julia> @btime solve(stones, 75) # 12ms
  26.786 ms (345428 allocations: 19.68 MiB)
234568186890978

```

---

<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 13, 2024, 3:56pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/27 "2024-12-13T15:56:46Z")

</div>

> [@rocco\_sprmnt21](#):
>
> ```julia
> julia> @btime solve(stones, 75) # 12ms
> 155.595 ms (516906 allocations: 49.95 MiB)
> 234568186890978
> 
> ```

Something is not measured properly - too many allocations. Here is the same run from my REPL:

```julia
julia> @btime solve($stones, 75)
  6.904 ms (84 allocations: 511.62 KiB)
234568186890978

```

```julia
julia> versioninfo()
Julia Version 1.11.1

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 4:04pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/28 "2024-12-13T16:04:26Z")

</div>

```julia
using OrderedCollections

function solve(stones, n)
    d_new = Dict{Int,Int}()
    d_old = Dict(stones .=> 1)
    for _ in 1:n
        for (s, n) ∈ d_old
            t1, t2 = blink(s)
            mergewith!(+, d_new,
              t2 == NO_STONE ? LittleDict((t1,),(n,)) : 
                               LittleDict((t1,t2),(n,n)))
        end
        d_old, d_new = d_new, d_old
        empty!(d_new)
    end
    sum(values(d_old))
end

julia> solve(stones, 25)
197357

julia> solve(stones, 75)
234568186890978

julia> @btime solve(stones, 25) # 260 us
  3.321 ms (13913 allocations: 1.56 MiB)
197357

julia> @btime solve($stones, 25) # 260 us
  3.332 ms (13912 allocations: 1.56 MiB)
197357

julia> @btime solve($stones, 75) # 12ms
  152.654 ms (516905 allocations: 49.95 MiB)
234568186890978

```

```julia

julia> versioninfo()
Julia Version 1.10.6

```

Someone changed the code of dict.jl!?!?

---

<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 13, 2024, 4:48pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/29 "2024-12-13T16:48:32Z")

</div>

That is strange.

More likely some reference to a global instead of local. Have you checked `blink`?

Is `NO_STONE` `const`?

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 4:56pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/30 "2024-12-13T16:56:02Z")

</div>

from a fresh session

> **Summary**
>
> ```julia
> julia> const NO_STONE = -1 # folks, we're writing old school C today
> -1
> 
> julia> stones = split(readlines("input_aoc24_d11.txt") |> only, " ") .|> x -> parse(Int, x)
> 8-element Vector{Int64}:
> 4610211
> 4
> 0
> 59
> 3907
> 201586
> 929
> 33750
> 
> julia> number_of_digits(x) = floor(Int, log10(x)) + 1
> number_of_digits (generic function with 1 method)
> 
> julia> function blink(stone::Integer)
> stone == 0 && return (1, NO_STONE)
> n = number_of_digits(stone)
> iseven(n) && return divrem(stone, 10^(n ÷ 2))
> (stone * 2024, NO_STONE)
> end
> blink (generic function with 1 method)
> 
> julia> using OrderedCollections
> 
> julia> function solve(stones, n)
> d_new = Dict{Int,Int}()
> d_old = Dict(stones .=> 1)
> for _ in 1:n
> for (s, n) ∈ d_old
> t1, t2 = blink(s)
> mergewith!(+, d_new,
> t2 == NO_STONE ? LittleDict((t1,),(n,)) : 
> LittleDict((t1,t2),(n,n)))
> end
> d_old, d_new = d_new, d_old
> empty!(d_new)
> end
> sum(values(d_old))
> end
> solve (generic function with 1 method)
> 
> julia> solve(stones, 25)
> 197357
> 
> julia> solve(stones, 75)
> 234568186890978
> 
> julia> @btime solve($stones, 25) # 260 us
> ERROR: LoadError: UndefVarError: `@btime` not defined
> in expression starting at c:\Users\sprmn\.julia\environments\v1.10.5\AOC_24_d11.jl:168
> 
> julia> using BenchmarkTools
> 
> julia> @btime solve($stones, 25) # 260 us
> 602.400 μs (441 allocations: 1.04 MiB)
> 197357
> 
> julia> 
> 
> julia> @btime solve($stones, 75) # 12ms
> 25.083 ms (3614 allocations: 30.75 MiB)
> 234568186890978
> 
> ```

---

<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 13, 2024, 5:10pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/31 "2024-12-13T17:10:21Z")

</div>

> [@rocco\_sprmnt21](#):
>
> ```julia
> julia> @btime solve($stones, 75) # 12ms
> 152.654 ms (516905 allocations: 49.95 MiB)
> 234568186890978
> 
> ```

> [@rocco\_sprmnt21](#):
>
> ```julia
> julia> @btime solve($stones, 75) # 12ms
> 25.083 ms (3614 allocations: 30.75 MiB)
> 234568186890978
> 
> ```

Already a big improvement.  
My results:

```julia
julia> @btime solve($stones, 75)
  6.851 ms (84 allocations: 511.62 KiB)
234568186890978

```

seem to be due to `1.11` changes.

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [December 13, 2024, 5:34pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/32 "2024-12-13T17:34:29Z")

</div>

But isn’t the original script improved by julia 1.11?

I mean this

```julia
                       # if haskey(d_n, s2)
                       # d_n[s2] += n
                       # else
                       # d_n[s2] = n
                       # end

```

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [December 13, 2024, 6:31pm UTC](https://discourse.julialang.org/t/performance-of-dictionaries-jl-vs-base-dict/92073/33 "2024-12-13T18:31:31Z")

</div>

Haven’t followed all the benchmarking, but dict.jl has changed in Julia 1.11 and now uses `Memory` instead of `Vector` internally for holding data.

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