# What is the fastest way of making a vector of dictionaries?

**URL:** <https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363>\
**Category:** General Usage\
**Created:** [March 31, 2024, 11:53pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363 "2024-03-31T23:53:51Z")\
**Posts on this page:** 12\
**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, 11:53pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/1 "2024-03-31T23:53:51Z")

</div>

I know the type (`Dict{Int,Int}`) and I know the size of the vector.  
How do I make the vector quickly? (Just to be explicit, all those dictionaries  
are independent; I do not want to fill the vector with just a single dictionary.)

---

<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:** [April 1, 2024, 12:01am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/2 "2024-04-01T00:01:39Z")

</div>

Just write a comprehension and call it a day? It’s inconceivable to me that constructing a vector of empty dictionaries is a performance-critical step in a real application — do you have profiling evidence to the contrary?

---

<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:02am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/3 "2024-04-01T00:02:53Z")

</div>

The problem is that there may be several million of them, and the construction should ideally scale with a number of computing threads.

This is kind of okay,

```julia
    empty = Dict{Int,Int}()
    rows = fill(empty, size(pattern, 2))
    Threads.@threads for c in axes(pattern, 2)
        cr = pattern.colptr[c]:(pattern.colptr[c+1]-1)
        rows[c] = Dict{Int,Int}(zip(view(pattern.rowval, cr), cr))
    end

```

but there might be a better (faster) way?

---

<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:** [April 1, 2024, 12:05am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/4 "2024-04-01T00:05:54Z")

</div>

Presumably you are going to do something with these millions of empty dictionaries. Won’t that dominate your runtime?

---

<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:06am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/5 "2024-04-01T00:06:57Z")

</div>

True, the loop fills them, and then I want to read them.  
But if the whole thing is sequential, eventually it will spoil parallel scaling.

---

<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:** [April 1, 2024, 12:11am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/6 "2024-04-01T00:11:47Z")

</div>

> [@PetrKryslUCSD](#):
>
> eventually it will spoil parallel

Are you actually at that point for a realistic run, or is this just theoretical?

That being said, there are multiple implementations of multi-threaded `map` lying around, e.g. in ThreadedIterables.jl, which should probably be simpler than the code you posted.

---

<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:15am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/7 "2024-04-01T00:15:00Z")

</div>

The construction takes enough time to reduce parallel efficiency to 0.5 for 16 computing threads. So, yes.

---

<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:34am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/8 "2024-04-01T00:34:51Z")

</div>

Alas, it would appear the whole idea was a washout.  
Preliminary investigation ([What is faster: sparse vector or a dictionary? - #12 by PetrKryslUCSD](https://discourse.julialang.org/t/what-is-faster-sparse-vector-or-a-dictionary/112341/12)) seemed to indicate that I could get a speedup by using dictionaries, yet in actual application they are much slower than the original approach.

---

<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:** [April 1, 2024, 2:59pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/9 "2024-04-01T14:59:52Z")

</div>

> [@PetrKryslUCSD](#):
>
> seemed to indicate that I could get a speedup by using dictionaries, yet in actual application they are much slower than the original approach.

I’m not surprised — if allocating _empty_ dictionaries takes a significant fraction of your compute time, then you must do only a small number of subsequent operations per dictionary. For very small dictionaries being accessed a limited number of times it will be probably faster to use another data structure (even linear search).

(For performance optimizing dictionaries, one may also want to consider custom hash function — [Dictionary with custom hash function](https://discourse.julialang.org/t/dictionary-with-custom-hash-function/49168))

---

<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, 3:26pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/10 "2024-04-01T15:26:20Z")

</div>

Not so. Creating the vector is relatively cheap, and it scales. What turned out to be expensive was to access the non-empty dictionaries. The minimal example needed to be actually made more realistic by using N=27, so you are right that the dictionaries are rather small. But the minimal working example still indicated that they should be faster than binary search. In practice, they turned out to be much much slower.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [April 1, 2024, 3:31pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/11 "2024-04-01T15:31:19Z")

</div>

> [@PetrKryslUCSD](#):
>
> ```julia
> empty = Dict{Int,Int}()
> rows = fill(empty, size(pattern, 2))
> 
> ```

Note that with this pattern you are filling each row with _the same_ dictionary:

```julia
julia> empty = Dict{Int,Int}()
Dict{Int64, Int64}()

julia> rows = fill(empty, 2)
2-element Vector{Dict{Int64, Int64}}:
 Dict()
 Dict()

julia> rows[1][1] = 1
1

julia> rows[1]
Dict{Int64, Int64} with 1 entry:
  1 => 1

julia> rows[2]
Dict{Int64, Int64} with 1 entry:
  1 => 1

```

and that here:

```julia
        rows[c] = Dict{Int,Int}(zip(view(pattern.rowval, cr), cr))

```

you are replacing that empty dictionary in row `c` by a new one. So probably you just need

```julia
rows = Vector{Dict{Int,Int}}(undef, size(patterns,2))

```

to initialize your structure (independently of that being the best data structure there, or not).

---

<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, 3:36pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-of-making-a-vector-of-dictionaries/112363/12 "2024-04-01T15:36:47Z")

</div>

Your way of creating the vector is optimal, thanks. Unfortunately, that was never the bottleneck.