# What is faster: sparse vector or a dictionary?

**URL:** <https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341>\
**Category:** General Usage\
**Created:** [March 31, 2024, 3:34am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341 "2024-03-31T03:34:03Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 3:34am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/1 "2024-03-31T03:34:03Z")

</div>

Sparse vector uses binary search. Dictionary uses a hash. Anyone has an experience to share?

---

<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:** [March 31, 2024, 4:23am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/2 "2024-03-31T04:23:49Z")

</div>

in general, most sparse matrix code can be written as iteration over the nonzero elements. for cases that can’t, dictionaries will usually be faster.

---

<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:** [March 31, 2024, 11:00am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/3 "2024-03-31T11:00:29Z")

</div>

Dictionary lookup should be faster than binary search of a sorted array once you have more than a few dozen elements.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 1:37pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/4 "2024-03-31T13:37:10Z")

</div>

Thanks. What I need is to read from “random” locations.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 6:44pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/5 "2024-03-31T18:44:34Z")

</div>

So, here is a MWE.

```julia
module m

using InteractiveUtils

function _binary_search(array::Array{IT,1}, target::IT, left::IT, right::IT) where {IT}
    @inbounds while left <= right # Generating the middle element position 
        mid = fld((left + right), 2) # If element > mid, then it can only be present in right subarray
        if array[mid] < target
            left = mid + 1 # If element < mid, then it can only be present in left subarray 
        elseif array[mid] > target
            right = mid - 1 # If element is present at the middle itself 
        else # == 
            return mid
        end
    end
    return 0
end

N = 5103
r = collect(1:N)
g = collect(N:-1:1)
NLOOP = 1000000
d = Dict{Int, Int}(zip(r, r))

function test_bsearch(N, r, g)
    for l in 1:NLOOP
        for R in Int.(round.([0.13, 0.39, 0.49, 0.61, 0.77, 0.98] * N))
            v = do_bsearch(N, r, g, R)
            @assert v == g[R]
        end
    end
    nothing
end

function do_bsearch(N, r, g, R)
    #@code_warntype _binary_search(r, R, 1, N)
    k = _binary_search(r, R, 1, N)
    return g[k]
end

function test_dict(N, d, g)
    for l in 1:NLOOP
        for R in Int.(round.([0.13, 0.39, 0.49, 0.61, 0.77, 0.98] * N))
            v = do_dict(N, d, g, R)
            @assert v == g[R]
        end
    end
    nothing
end

function do_dict(N, d, g, R)
    k = d[R]
    return g[k]
end

using BenchmarkTools

@btime test_bsearch(N, r, g)
@btime test_bsearch($N, $r, $g)

@btime test_dict(N, d, g)
@btime test_dict($N, $d, $g)

end # module

```

It seems to be saying that the dictionary is (in this case) nearly twice as fast.  
However, I see oodles of allocations, from both implementations, and I can’t figure out where it comes from.  
The macro “code warn type” says the code is clean.

I don’t see what is wrong there. Does something pop out for you?

---

<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:** [March 31, 2024, 8:42pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/6 "2024-03-31T20:42:23Z")

</div>

I think your binary search is non-allocating.

```julia
julia> const v = [1,5,8,9,10];

julia> const target, left, right = 8, 1, 5;

julia> @allocated _binary_search(v, 8, 1, 5)
0

```

You could be getting allocations from test code like this:

```
for R in Int.(round.([0.13, 0.39, 0.49, 0.61, 0.77, 0.98] * N))

```

where you allocate an array by writing it down and then allocate more arrays to hold the results from broadcasting `round` and `Int`.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 8:50pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/7 "2024-03-31T20:50:18Z")

</div>

OMG, I’ve been totally blind.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 9:10pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/8 "2024-03-31T21:10:17Z")

</div>

Actually tried to fix it, no luck!

```julia
module m

using InteractiveUtils

function _binary_search(array::Array{IT,1}, target::IT, left::IT, right::IT) where {IT}
    @inbounds while left <= right # Generating the middle element position 
        mid = fld((left + right), 2) # If element > mid, then it can only be present in right subarray
        if array[mid] < target
            left = mid + 1 # If element < mid, then it can only be present in left subarray 
        elseif array[mid] > target
            right = mid - 1 # If element is present at the middle itself 
        else # == 
            return mid
        end
    end
    return 0
end

N = 5103
r = collect(1:N)
g = collect(N:-1:1)
NLOOP = 1000000
d = Dict{Int, Int}(zip(r, r))
Rs = Int.(round.([0.13, 0.39, 0.49, 0.61, 0.77, 0.98] * N))

function test_bsearch(N, r, g, Rs)
    for l in 1:NLOOP
        for R in Rs
            v = do_bsearch(N, r, g, R)
            @assert v == g[R]
        end
    end
    nothing
end

function do_bsearch(N, r, g, R)
    k = _binary_search(r, R, 1, N)
    return g[k]
end

function test_dict(N, d, g, Rs)
    for l in 1:NLOOP
        for R in Rs
            v = do_dict(N, d, g, R)
            @assert v == g[R]
        end  
    end
    nothing
end

function do_dict(N, d, g, R)
    k = d[R]
    return g[k]
end

using BenchmarkTools

@btime test_bsearch(N, r, g, $Rs)
@btime test_bsearch($N, $r, $g, $Rs)

@btime test_dict(N, d, g, $Rs)
@btime test_dict($N, $d, $g, $Rs)

end # module

```

The above still allocates.

```julia
WARNING: replacing module m.
  282.951 ms (2998979 allocations: 61.02 MiB)
  280.877 ms (2998979 allocations: 61.02 MiB)
  94.330 ms (2998979 allocations: 61.02 MiB)
  95.013 ms (2998979 allocations: 61.02 MiB)
Main.m

```

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [March 31, 2024, 9:39pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/9 "2024-03-31T21:39:37Z")

</div>

```julia
const NLOOP = 1000000

```

yields

```julia
  157.137 ms (0 allocations: 0 bytes)
  157.251 ms (0 allocations: 0 bytes)
  36.294 ms (0 allocations: 0 bytes)
  37.151 ms (0 allocations: 0 bytes)
Main.m

```

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 9:45pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/10 "2024-03-31T21:45:29Z")

</div>

So, it boxes the `l`? Or why does it allocate?

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [March 31, 2024, 10:26pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/11 "2024-03-31T22:26:23Z")

</div>

The compiler does not know what type `NLOOP` is, so it does not know the type of `1:NLOOP`, consequently it does not know what type `l` is, nor how long the loop is. For what the compiler knows, `1:NLOOP` can be anything, and it has to allocate room for every `l` coming out of it to see if it’s `nothing` or some `(value, state)` tuple (like it does for every iterator). Even if you don’t use `l` in the loop, the iterator `1:NLOOP` is used as described in [Interfaces · The Julia Language](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration).

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 31, 2024, 11:44pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/12 "2024-03-31T23:44:08Z")

</div>

What if I never defined the name (i.e. used `_`)? Edit: That wouldn’t have helped at all.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [April 1, 2024, 12:40am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/13 "2024-04-01T00:40:11Z")

</div>

From this simple example, why, I had some hopes that using a dictionary instead of a sparse data structure (vector) I could get a speedup. Alas, the opposite was found: the binary search is at least 3x as fast as the dictionary. Not sure why. Perhaps the memory fragmentation of the dynamic structures?

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [April 1, 2024, 10:01am UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/14 "2024-04-01T10:01:38Z")

</div>

doesn’t it show the opposite? The numbers reported by you are 280ms for binary search, 95 ms for dictionaries; by Chris Elrod, 157ms for binary search, 36ms for dictionaries. FWIW I get

```julia
  157.283 ms (2998979 allocations: 61.02 MiB)
  157.035 ms (2998979 allocations: 61.02 MiB)
  55.314 ms (2998979 allocations: 61.02 MiB)
  55.730 ms (2998979 allocations: 61.02 MiB)

```

for the non-const `NLOOP`, and

```julia
  127.844 ms (0 allocations: 0 bytes)
  127.847 ms (0 allocations: 0 bytes)
  21.291 ms (0 allocations: 0 bytes)
  21.545 ms (0 allocations: 0 bytes)

```

for the `const` one, also seeing much faster perf with dictionaries.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [April 1, 2024, 1:40pm UTC](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/15 "2024-04-01T13:40:00Z")

</div>

He was saying, this example made the dict look faster making him hopeful to speed up his real use case, but when testing that he found that binary search was actually faster there.