# Parallel accumulation over large dictionary

**URL:** <https://discourse.julialang.org/t/parallel-accumulation-over-large-dictionary/116316>\
**Category:** General Usage\
**Tags:** question, parallel, dictionary\
**Created:** [June 27, 2024, 3:53pm UTC](https://discourse.julialang.org/t/parallel-accumulation-over-large-dictionary/116316 "2024-06-27T15:53:50Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![OHL](https://avatars.discourse-cdn.com/v4/letter/o/76d3ee/32.png) [@OHL](https://discourse.julialang.org/u/OHL)\
**Post date:** [June 27, 2024, 3:53pm UTC](https://discourse.julialang.org/t/parallel-accumulation-over-large-dictionary/116316/1 "2024-06-27T15:53:50Z")

</div>

I have a large Dict `D` and a function `f` that takes as input a pair of dictionary entries and outputs a float. I would like to compute `f` for all pairs in `D` and sum the results. `f` is also symmetric, `f(a,b) = f(b,a)`, so I only need to iterate over unique unsorted pairs, saving a factor of ~2 in runtime. Here is a basic MWE that works on a single thread:

```julia
tot = 0
for (i, a) in enumerate(D)
    for (j, b) in enumerate(D)
        if j < i
            continue
        elseif j==i
            tot += f(a,b)
        else
            tot += 2*f(a,b)
        end
    end
end
return tot

```

`f` is fairly quick to calculate, so the main thing making this slow is the large size of `D`. Since the loops are independent apart from the accumulation in `tot`, I have therefore been trying to parallelize this function.

The problem is that most parallelization tools I have come across seem to require using something like `collect` to convert `D` into an array, so that it can be split into segments and distributed across multiple threads. But unfortunately that is not an option here because `D` is very large and I do not have the memory to make a copy.

**Q:** What are my options for parallelizing this accumulating function _without_ making a copy of `D`?

---

<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:** [June 27, 2024, 5:14pm UTC](https://discourse.julialang.org/t/parallel-accumulation-over-large-dictionary/116316/2 "2024-06-27T17:14:53Z")

</div>

> [@OHL](#):
>
> The problem is that most parallelization tools I have come across seem to require using something like `collect` to convert `D` into an array, so that it can be split into segments and distributed across multiple threads. But unfortunately that is not an option here because `D` is very large and I do not have the memory to make a copy.
> 
> **Q:** What are my options for parallelizing this accumulating function _without_ making a copy of `D`?

One way to do this would by accessing the [internals of `Dict`](https://github.com/JuliaLang/julia/blob/5163d5585a5c2014f92fb1668b356bee30625a83/base/dict.jl) which have a [simple array of “slots”](https://github.com/JuliaLang/julia/blob/5163d5585a5c2014f92fb1668b356bee30625a83/base/dict.jl#L67) under the hood, and an [`isslotfilled`](https://github.com/JuliaLang/julia/blob/5163d5585a5c2014f92fb1668b356bee30625a83/base/dict.jl#L134) function to check whether a slot actually has an element. So, you could use a standard parallelization method to partition the array `dict.slots` among your threads, have each thread iterate over its slots and sum the pairs for slots that are filled.

An additional advantage over this approach is that you can skip the j \< i check—to iterate over unique pairs for a filled slot i, you can just loop over slots \ge i.

Another option is to switch to another `Dict`-like collection. For example, the `OrderedDict` structure from OrderedCollections.jl has a simple [array of keys](https://github.com/JuliaCollections/OrderedCollections.jl/blob/7a4a781095628ed78075c4da1d18f52ad2d9e077/src/ordered_dict.jl#L11-L18) that [its iteration loops over](https://github.com/JuliaCollections/OrderedCollections.jl/blob/7a4a781095628ed78075c4da1d18f52ad2d9e077/src/ordered_dict.jl#L449-L457), so you can parallelize a loop over `dict.keys` directly without worrying about “unfilled” slots.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [June 27, 2024, 7:32pm UTC](https://discourse.julialang.org/t/parallel-accumulation-over-large-dictionary/116316/3 "2024-06-27T19:32:43Z")

</div>

Seems like [Transducers](https://juliafolds.github.io/Transducers.jl/dev/tutorials/tutorial_parallel/#Parallel-processing-with-iterator-comprehensions) can even parallelize across iterators. Thus, you could try something like the following:

```julia
using Transducers

d = Dict(i => rand() for i in 1:10_000)

f(a, b) = last(a) * last(b)

pipeline = Iterators.product(enumerate(d), enumerate(d)) |>
           Filter(xy -> let ((i, _), (j, _)) = xy; i >= j end) |>
           Map(xy -> let ((i, a), (j, b)) = xy; i == j ? f(a, b) : 2 * f(a, b) end)

# Sequential execution
foldl(+, pipeline)
# Threaded execution
foldxt(+, pipeline

```