# Dict with integer keys and fastest insertion?

**URL:** <https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171>\
**Category:** Performance\
**Tags:** dictionary, data\_structures, hash, algorithm\
**Created:** [January 24, 2025, 3:44pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171 "2025-01-24T15:44:29Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [January 24, 2025, 3:44pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/1 "2025-01-24T15:44:29Z")

</div>

What are the best options for a dict/map with integer keys and the fastest insert/update? For background, I wish to aggregate those position-weight pairs (p,w) where the position is the same, I’m tinkering with the idea of having a sparse matrix be implemented as a list of dict’s, one for each column, and the matrix product needs this aggregation. So far, my benchmarks are:

```julia
function f0(pp::Vector{tp}, ww::Vector{tw}, Z::Vector{tw}) where {tp,tw}
    # aggregating with a dense vector Z
    for (p,w) ∈ zip(pp,ww) Z[p] += w end;   
    _pp = findall(Z .≠ 0)
    _ww = Z[_pp]
    Z .= 0 # clean up
    return _pp, _ww end;

function _add!(D::Dict{tp,tw}, p::tp, w::tw) where {tp, tw}
    idx = Base.ht_keyindex(D,p)
    if idx<0 D[p] = w  
    else D.vals[idx] += w end end;

function f1(pp::Vector{tp}, ww::Vector{tw}, D::Dict{tp,tw}) where {tp,tw}
    # aggregating with a dict
    for (p,w) ∈ zip(pp,ww)  
        @inline _add!(D,p,w) end 
    filter!(pw -> !iszero(pw[2]), D) end; # clean up

n, N =10^5, 10^7;
pp, ww = UInt32.(rand(1:n,N)), rand(-1:0.001:1,N);
Z, D = fill(0.0, n), Dict{UInt32,Float64}();
@time f0(pp, ww, Z);
@time f1(pp ,ww, D);
  0.034545 seconds (11 allocations: 1.538 MiB)
  0.212361 seconds (39 allocations: 4.334 MiB)

```

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [January 24, 2025, 6:45pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/2 "2025-01-24T18:45:35Z")

</div>

> [@Leo\_I](#):
>
> `_pp = findall(Z .≠ 0)`

`findall(!iszero, Z)` might be faster

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [January 24, 2025, 7:14pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/3 "2025-01-24T19:14:22Z")

</div>

Is there a way to also specify the type of elements in output of findall?  
Something like `findall(UInt32, !iszero, Z)`?

---

<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:** [January 24, 2025, 7:21pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/4 "2025-01-24T19:21:41Z")

</div>

> [@jling](#):
>
> `findall(!iszero, Z)` might be faster

Probably even better to overwrite `pp` and `ww` in-place if you can (since you are already overwriting `Z`), and merge the loops, e.g.

```julia
function f0!(pp::AbstractVector, ww::AbstractVector, Z::AbstractVector)
    for (p,w) ∈ zip(pp,ww); Z[p] += w; end
    ip, iw = firstindex(pp)-1, firstindex(ww)-1
    for p in eachindex(Z)
        @inbounds if Z[p] ≠ 0
            pp[ip += 1] = p
            ww[iw += 1] = Z[p]
        end
    end
    return resize!(pp, ip - firstindex(pp)+1),
           resize!(ww, iw - firstindex(ww)+1)
end

```

(Note that argument-type declarations like `pp::Vector{tp}` make no difference whatsoever to the performance; they just make your function less generic.)

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [January 24, 2025, 8:16pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/5 "2025-01-24T20:16:12Z")

</div>

No, in the case of matrix multiplication, I cannot overwrite pp and ww. But thank you! Any idea about fast Dict’s that I mentioned?

---

<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:** [January 24, 2025, 10:54pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/6 "2025-01-24T22:54:27Z")

</div>

> [@Leo\_I](#):
>
> `Z, D = fill(0.0, n), Dict{UInt32,Float64}();`

These two will have very different memory footprints. The former is proportional to domain size, the latter is proportional to size of support of `pp` values. This may determine the method to use. If `f0` memory footprint is acceptable, it should be hard to beat in terms of performance.

> [@Leo\_I](#):
>
> `filter!(pw -> !iszero(pw[2]), D)`

can be written as: `filter!((!iszero)∘last, D)`

And `_add!` can be elided with the use of `mergewith!`:

```julia
using OrderedCollections
f2(pp::Vector{tp}, ww::Vector{tw}, D::Dict{tp,tw}) where {tp,tw} =
  filter!((!iszero)∘last, mergewith!(+, D, LittleDict(pp,ww)))

```

Finally, better to benchmark with `@btime` (in BenchmarkTools) instead of `@time` (due to non-determinism and compilation time)

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [January 25, 2025, 8:50am UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/7 "2025-01-25T08:50:50Z")

</div>

This last suggestion is much slower:

```julia
@time f0(pp,ww,Z); @time f1(pp,ww,D1); @time f2(pp,ww,D2);
  0.054900 seconds (11 allocations: 1.538 MiB)
  0.243859 seconds (39 allocations: 4.334 MiB)
  0.871619 seconds (6 allocations: 208.000 MiB, 4.03% gc time)

```

I also tried `Base.IdDict` and `Dictionaries.UnorderedDictionary`, but both were slower than `f1`.

---

<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:** [January 25, 2025, 12:06pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/8 "2025-01-25T12:06:04Z")

</div>

`@time` should be run **twice** to avoid including compilation times.

---

<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:** [January 25, 2025, 1:28pm UTC](https://discourse.julialang.org/t/dict-with-integer-keys-and-fastest-insertion/125171/9 "2025-01-25T13:28:35Z")

</div>

Or better yet, using BenchmarkTools.jl or ChairMarks.jl to perform more careful repeated timing.

(However, you have to be careful to include a setup phase to re-initialize the arguments between benchmarks, since these functions modify their third argument.)