# Fast Multi-Threaded Array Editing without data races?

**URL:** <https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 28, 2024, 6:11pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863 "2024-05-28T18:11:45Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 6:11pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/1 "2024-05-28T18:11:45Z")

</div>

Hi, I am fairly new to multi-threading in Juila and am having trouble finding the best procedure to avoid data races in an a section of code I am writing.

The code uses a monte carlo method to generate values that are then assigned to specific locations in a large 6D array based on some conditions and a second array is used to keep a tally of sampled points. Something like (I cannot share the actual code):

```julia
lk = ReentrantLock()
Threads.@threads :static for iThreads in 1:nThreads
 generatevalues!(val,somedata)
(loc1,loc2,loc3,loc4,loc5,loc6,somedata)=generatelocations(somedata)
 #update arrays
 begin
  lock(lk)
 try
  if (1<=loc1<=num1)
   ArrayofValues[loc1+2,loc2,loc3,loc4,loc5,loc6] += val
  elseif (loc1 > num1)
   ArrayofValues[2,loc2,loc3,loc4,loc5,loc6] += val
  else (loc1 < num1)
   ArrayofValues[1,loc2,loc3,loc4,loc5,loc6] += val
  end
   @view(ArrayofTallys[:,loc2,loc3,loc4,loc5,loc6] .+= 1
 finally
  unlock(lk)
 end
end

```

These arrays are large but in general so the likelihood of two threads editing the same elements of the arrays at the same time is low but non-zero, hence the use of the lock. However this tends to makes the code slower than the serial version. Is there an efficient way to edit small sections/views of arrays without needing to lock the whole thing? Or is there a better approach that I should attempt to take?

edits: square brackets for array indexing.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [May 28, 2024, 6:20pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/2 "2024-05-28T18:20:59Z")

</div>

Welcome! None of this looks like it would work. Julia indexes with square brackets (not parens), and it looks like you’re using the `loc`s and `val` as both containers and scalars in a confusing manner.

Get the serial version working first, and then work towards multithreading if you need it (profile!).

---

<div class="post-metadata">

**Author:** ![adienes](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adienes/32/37459_2.png) [@adienes](https://discourse.julialang.org/u/adienes)\
**Post date:** [May 28, 2024, 6:33pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/3 "2024-05-28T18:33:28Z")

</div>

`OhMyThreads.jl` has quite a few very useful tools for multithreaded applications

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 6:34pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/4 "2024-05-28T18:34:53Z")

</div>

I have edited the original post to include the square brackets that are in the actual code.

To clarify more, the code works and has already been optimised for serial running (as well as I can optimise). The code is sampling over 6D of phase space that has been discretised by a set of `num` bins. The `loc`s are UInt32 values while the `val` is a Float32. The function `generatevalues!` mutates `val` for each monte carlo sample and then `generatelocations!` mutates the values of the `loc`s to generate the location of the correct bin in the 6D phase space with which to add `val` in the `ArrayofValues` array.

---

<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:** [May 28, 2024, 6:37pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/5 "2024-05-28T18:37:40Z")

</div>

How much of the time is in the indexing? If the array indexing isn’t your bottleneck, you could just have 1 thread who’s job is to do the array updates and only multithread `generatevalues!` and `generatelocations!`

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [May 28, 2024, 6:37pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/6 "2024-05-28T18:37:56Z")

</div>

> [@cneverett](#):
>
> The `loc`s are UInt32 values while the `val` is a Float32. The function `generatevalues!` mutates `val`

Right, you can’t mutate `UInt32` or `Float32`s — they’re immutable!

Generally, one strategy that can be useful is to generate a list of indices and values to update and then perform the updates sequentially at the end.

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 7:02pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/7 "2024-05-28T19:02:22Z")

</div>

The indexing and assigning takes about the same time as the other function. Either way, if I did just assign one thread to assign the values in not sure if that would scale well.

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 7:12pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/8 "2024-05-28T19:12:56Z")

</div>

> [@mbauman](#):
>
> Right, you can’t mutate `UInt32` or `Float32`s — they’re immutable!

The `generatelocations!` was just shorthand for some set of functions that revaluated the values of `loc` and `val` for each Monte Carlo sample. I have checked and this part of the code has no issues. I edited the original post to hopefully put it in a more accurate form.

The list of lists/vectors of indices with an associated value might work. Would there be any issues/anything I should be careful of when having multiple threads append to this list? Would I need to also lock the list?

---

<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:** [May 28, 2024, 7:18pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/9 "2024-05-28T19:18:39Z")

</div>

> [@cneverett](#):
>
> Would there be any issues/anything I should be careful of when having multiple threads append to this list

yes. Doing this without a lock doesn’t work.

---

<div class="post-metadata">

**Author:** ![Satvik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/satvik/32/20486_2.png) [@Satvik](https://discourse.julialang.org/u/Satvik)\
**Post date:** [May 28, 2024, 7:22pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/10 "2024-05-28T19:22:01Z")

</div>

Some questions:

- What do you want to happen if two threads would overwrite the same index? Are you ok with getting either value?

- What is your intention with this line of code? `@view(ArrayofTallys[:,loc2,loc3,loc4,loc5,loc6] .+= 1` Do you want to modify that whole row? (In which case you wouldn’t use `@view`

If I were approaching the problem, I would probably have your individual threads calculate their values then submit the intended updates to a `Channel{Task}`. The Channel would run on a single thread and be the only thing that directly accesses the array. If you’re interested in this approach I can write out a more detailed example.

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 7:30pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/11 "2024-05-28T19:30:50Z")

</div>

If appending to this list of vectors also needs a lock, what would the the speed up compared to what I am currently doing?

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [May 28, 2024, 7:36pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/12 "2024-05-28T19:36:21Z")

</div>

some very simple thoughts that might still work:

are your functions that generate data and indices the main bottleneck?  
if so, could you preallocate a buffer of values and one for indices for each Thread and simply write all the changes locally.

afterwards, you can iterate over the buffers in a single thread and sum up all the changes.

You can store the indices as a single number by using CartesianIndices

If you have enough memory you can of course also give each thread a copy of the array and in the end sum together all those arrays

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 7:36pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/13 "2024-05-28T19:36:48Z")

</div>

> [@Satvik](#):
>
> What do you want to happen if two threads would overwrite the same index? Are you ok with getting either value?

To get accurate Monte Carlo results, it would need to sum both values. I.e. I cannot miss a value.

> [@Satvik](#):
>
> What is your intention with this line of code? `@view(ArrayofTallys[:,loc2,loc3,loc4,loc5,loc6] .+= 1` Do you want to modify that whole row? (In which case you wouldn’t use `@view`

Yes, the whole row needs to be incremented by 1. What would your alternative to `@view` be?

> [@Satvik](#):
>
> If you’re interested in this approach I can write out a more detailed example.

If I were to do this, I am unclear how a bottleneck could be avoided if I have lots of threads calculating values and only a single one allocating to an array? Perhaps if you could provide more detail, that would be helpful.

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 28, 2024, 7:46pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/14 "2024-05-28T19:46:06Z")

</div>

The generating functions and the allocation process (in serial) take about equal time, and they are about as fast as I can get them (again in serial).

Storing the indices as a CartesianIndex is a good idea.

> [@Salmon](#):
>
> If you have enough memory you can of course also give each thread a copy of the array and in the end sum together all those arrays

This would be great but the arrays are in general quite large (around 17GB for one case) so I can’t just make copies for each thread.

---

<div class="post-metadata">

**Author:** ![Satvik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/satvik/32/20486_2.png) [@Satvik](https://discourse.julialang.org/u/Satvik)\
**Post date:** [May 28, 2024, 7:48pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/15 "2024-05-28T19:48:28Z")

</div>

> To get accurate Monte Carlo results, it would need to sum both values. I.e. I cannot miss a value.

Good to know, the channel approach can do that.

> If I were to do this, I am unclear how a bottleneck could be avoided if I have lots of threads calculating values and only a single one allocating to an array? Perhaps if you could provide more detail, that would be helpful.

Assigning to an array is _extremely_ fast, so it’s usually the case that something else is slowing you down, such as the if statement. Can you give me a sense of the number of writes per second you expect? For example, writing to 100,000 randomly selected indices takes ~55ms on my machine.

```julia
using BenchmarkTools
base_array = zeros(1_000_000)
rand_indices = rand(1:1_000_000, 100_000)
rand_values = rand(100_000)

@btime for (i, v) in zip(rand_indices, rand_values)
   base_array[i] = v
end
> 55.241 ms (1099356 allocations: 25.93 MiB)

```

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [May 28, 2024, 8:06pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/16 "2024-05-28T20:06:50Z")

</div>

In fact, sorting the indices is likely to be a huge win for arrays this large — random access is _slow_.

---

<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:** [May 28, 2024, 8:09pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/17 "2024-05-28T20:09:36Z")

</div>

This depends a lot on how dense the sorted indices are.

---

<div class="post-metadata">

**Author:** ![Satvik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/satvik/32/20486_2.png) [@Satvik](https://discourse.julialang.org/u/Satvik)\
**Post date:** [May 28, 2024, 8:54pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/18 "2024-05-28T20:54:02Z")

</div>

Here’s an example of the channel approach:

```julia
task_queue = Channel{Task}(Inf)
task_consumer = Threads.@spawn begin
    for task in task_queue
         schedule(task)
         wait(task)
    end
end

function make_worker(task_queue)
    Threads.@spawn begin
         generatevalues!(val,somedata)
        (loc1,loc2,loc3,loc4,loc5,loc6,somedata)=generatelocations(somedata)
        if (1<=loc1<=num1)
           task = @task ArrayofValues[loc1+2,loc2,loc3,loc4,loc5,loc6] += val
        elseif (loc1 > num1)
           task = @task ArrayofValues[2,loc2,loc3,loc4,loc5,loc6] += val
        else (loc1 < num1)
           task = @task ArrayofValues[1,loc2,loc3,loc4,loc5,loc6] += val
       end
      put!(task_queue, task)
  end

workers = [make_worker(task_queue) for i in 1:8]

```

This approach will make 8 worker tasks, and one consumer task. The workers do as much work as possible, then pass a simple update task to the queue, which `task_consumer` processes. Since `task_consumer` is the only one directly touching `ArrayOfValues`, it’s thread-safe, and it will almost certainly process the tasks much faster than the workers can produce them.

---

<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:** [May 28, 2024, 9:42pm UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/19 "2024-05-28T21:42:05Z")

</div>

Unless completely trivial, it’s a good idea to use `Threads.@spawn` for threading, or some of the tools in the `OhMyThreads` package. Locking is ok if the locked portion of the loop is minimal compared to the actual work being done. Otherwise the lock overhead can easily result in a slower threaded version than a serial one.

I’m a bit uncertain about your program, should there be loop around the generation? Ok, I assume so. I think I would have done something like this:

```julia
tasks = Task[]
for _ in 1:nthreads()
    push!(tasks,
      Threads.@spawn begin
        <allocate working memory for e.g. val or other stuff>
        idxval = Vector{Tuple{CartesianIndex{6}, Float32}}(undef, N)
        for i in 1:N # whatever N is
            val = generatevalue(somedata)
            idx = generateindex(somedata) # Assumed to be a CartesianIndex
            idxval[i] = (idx, val)
        end
        sort!(idxval) # sort it to ensure data locality if it's reasonably dense, otherwise leave it.
        return idxval
      end)
end

for t in tasks
    # here we could merge all the index/value vectors, or take them one by one.
    for (id, v) in fetch(t)::Vector{Tuple{CartesianIndex{6}, Float32})
        ArrayofValues[id] += v
        # and the other logic
    end
end

```

All this should be put inside a function, or two functions, one with the `@spawn` loop, one with the `fetch` loop.

Conceptually this is not very different from the `Channel` approach, more like a verbose variant of it.

It’s not obvious that the `idxval` should be a `Vector` of a `Tuple`, it could also be a `Vector{Any}`, whatever is faster. But when it’s fetched it’s probably wise to annotate it with what’s in it. So the compiler knows.

The idea here is to avoid locks altogether, and separating the generation from the storing of values. If a huge number of values are generated, you may do it in smaller chunks to not use all your memory in the `idxval` vector.

---

<div class="post-metadata">

**Author:** ![cneverett](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cneverett/32/209565_2.png) [@cneverett](https://discourse.julialang.org/u/cneverett)\
**Post date:** [May 29, 2024, 9:15am UTC](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863/20 "2024-05-29T09:15:40Z")

</div>

> [@Satvik](#):
>
> Assigning to an array is _extremely_ fast, so it’s usually the case that something else is slowing you down, such as the if statement. Can you give me a sense of the number of writes per second you expect? For example, writing to 100,000 randomly selected indices takes ~55ms on my machine.

My system seems to be faster than yours taking only ~8.5ms to run that code. It must be the if statements slowing it down. When in serial, the whole process, for a single sample point takes ~100ns.

> [@Satvik](#):
>
> This approach will make 8 worker tasks, and one consumer task. The workers do as much work as possible, then pass a simple update task to the queue, which `task_consumer` processes. Since `task_consumer` is the only one directly touching `ArrayOfValues`, it’s thread-safe, and it will almost certainly process the tasks much faster than the workers can produce them.

I will implement this and get back with some benchmarks.

[Next page](https://discourse.julialang.org/t/fast-multi-threaded-array-editing-without-data-races/114863.md?page=2)