# Multithreading for nested loops

**URL:** <https://discourse.julialang.org/t/multithreading-for-nested-loops/36002>\
**Category:** Performance\
**Tags:** multithreading\
**Created:** [March 15, 2020, 5:31am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002 "2020-03-15T05:31:15Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![henry2004y](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henry2004y/32/9284_2.png) [@henry2004y](https://discourse.julialang.org/u/henry2004y)\
**Post date:** [March 15, 2020, 5:31am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/1 "2020-03-15T05:31:15Z")

</div>

Hi,

I am wondering how to apply multi-threading to nested for loops.

For the function `nestedloop` below, I guess the threads will only be launched for the outermost k loop for `OMP_JULIA_THREADS` times:

```julia
function nestedloops(nx, ny, nz)

   state = ones(nx,ny,nz)

   Threads.@threads for k = 1:nz
      for j = 1:ny
         for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   return
end

```

If I add more `@thread` like the following:

```julia
function nestedloops2(nx, ny, nz)

   state = ones(nx,ny,nz)

   Threads.@threads for k = 1:nz
      Threads.@threads for j = 1:ny
         Threads.@threads for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   return
end

```

Will it launch `OMP_JULIA_THREADS`^3 threads in total? At least I can see an obvious decrease in performance and significant amount of additional memory allocations.

If I write the nested loops in a more compact way:

```julia
function nestedloops3(nx, ny, nz)

   state = ones(nx,ny,nz)

   Threads.@threads for k = 1:nz, j = 1:ny, for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
   end

   return
end

```

This will return error:

```julia
ERROR: LoadError: syntax: invalid assignment location "k = 1:nz"

```

Is there a way like OpenMP that we can collapse the nested loops and apply simd, i.e., something like `#pragma for collapse(3) simd` in C?

---

<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:** [March 15, 2020, 6:55am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/2 "2020-03-15T06:55:18Z")

</div>

in `1.3+`, you can nest `@threades` and Julia will figure out what to do

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [March 15, 2020, 7:15am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/3 "2020-03-15T07:15:21Z")

</div>

I don’t think that’s true. You can nest threads created with `@spawn` but `@threads` isn’t using the new partr scheduler AFAIU.

---

<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:** [March 15, 2020, 7:29am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/4 "2020-03-15T07:29:02Z")

</div>

um, it’s a bit late for me to search examples properly but the language on [Announcing composable multi-threaded parallelism in Julia](https://julialang.org/blog/2019/07/multithreading/) says:

> Some History  
> In version 0.5 about two years later, we released the `@threads for` macro with “experimental” status … however: `@threads` loops could not be nested: if the functions they called used `@threads` recursively, those inner loops would only occupy the CPU that called them. …

my understanding (and memory) is that in `1.3+` you can?

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [March 15, 2020, 8:50am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/5 "2020-03-15T08:50:08Z")

</div>

[https://github.com/JuliaLang/julia/pull/35003](https://github.com/JuliaLang/julia/pull/35003)

---

<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:** [March 15, 2020, 9:41am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/6 "2020-03-15T09:41:54Z")

</div>

well, I’m the

> confusion online

---

<div class="post-metadata">

**Author:** ![henry2004y](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henry2004y/32/9284_2.png) [@henry2004y](https://discourse.julialang.org/u/henry2004y)\
**Post date:** [March 15, 2020, 3:32pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/7 "2020-03-15T15:32:02Z")

</div>

So what I asked in the main thread is still currently not possible?

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [March 15, 2020, 4:13pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/8 "2020-03-15T16:13:35Z")

</div>

Just don’t use `@threads` but `@spawn` the tasks in the loops. You can also check out the PR I linked in which @Mason proposed a `@mythreads` macro which should give you what you want.

---

<div class="post-metadata">

**Author:** ![pbayer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pbayer/32/11675_2.png) [@pbayer](https://discourse.julialang.org/u/pbayer)\
**Post date:** [March 15, 2020, 6:25pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/9 "2020-03-15T18:25:30Z")

</div>

@threads seems to be deterministic in starting tasks on threads:

```julia
using .Threads

const N = nthreads()
const t1 = zeros(Int, N)

julia> for j in 1:5
           @sync @threads for i in 1:N
               t1[i] = threadid()
           end
           println(t1, " - ", Set(t1))
       end
[1, 2, 3, 4, 5, 6, 7, 8] - Set([7, 4, 2, 3, 5, 8, 6, 1])
[1, 2, 3, 4, 5, 6, 7, 8] - Set([7, 4, 2, 3, 5, 8, 6, 1])
[1, 2, 3, 4, 5, 6, 7, 8] - Set([7, 4, 2, 3, 5, 8, 6, 1])
[1, 2, 3, 4, 5, 6, 7, 8] - Set([7, 4, 2, 3, 5, 8, 6, 1])
[1, 2, 3, 4, 5, 6, 7, 8] - Set([7, 4, 2, 3, 5, 8, 6, 1])

```

vs @spawn

```julia
const s1 = zeros(Int, N)

julia> for j in 1:5
           @sync for i in 1:N
               Threads.@spawn s1[i] = threadid()
           end
           println(s1, " - ", Set(s1))
       end
[2, 7, 3, 8, 6, 4, 5, 1] - Set([7, 4, 2, 3, 8, 5, 6, 1])
[3, 4, 8, 7, 3, 8, 7, 4] - Set([7, 4, 3, 8])
[5, 2, 2, 5, 2, 5, 4, 4] - Set([4, 2, 5])
[8, 3, 7, 3, 7, 7, 3, 3] - Set([7, 3, 8])
[4, 4, 4, 7, 6, 3, 3, 2] - Set([7, 4, 2, 3, 6])

```

with @spawn not every thread always gets a task. Or am I doing something wrong here?

Maybe @spawn is better for just spawning lots of tasks to threads.

---

<div class="post-metadata">

**Author:** ![henry2004y](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henry2004y/32/9284_2.png) [@henry2004y](https://discourse.julialang.org/u/henry2004y)\
**Post date:** [March 15, 2020, 8:01pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/10 "2020-03-15T20:01:56Z")

</div>

As pointed by @lungben

> You need to add `@sync` for your `@spawn` versions, otherwise the timer just measures the time to start the tasks and does not wait until they finish.

Now I have added the `@sync` macros.

```julia
# export JULIA_NUM_THREADS=2

function nestedloops1(nx, ny, nz)

   state = ones(nx,ny,nz)

   for k = 1:nz
      for j = 1:ny
         for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return
end

function nestedloops2(nx, ny, nz)

   state = ones(nx,ny,nz)

   @inbounds for k = 1:nz
      @inbounds for j = 1:ny
         @inbounds for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return
end

function nestedloops3(nx, ny, nz)

   state = ones(nx,ny,nz)

   Threads.@threads for k = 1:nz
      for j = 1:ny
         for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return

end

function nestedloops4(nx, ny, nz)

   state = ones(nx,ny,nz)

   @sync Threads.@spawn for k = 1:nz
      for j = 1:ny
         for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return

end

function nestedloops5(nx, ny, nz)

   state = ones(nx,ny,nz)

   for k = 1:nz, j = 1:ny, i = 1:nx
      state[i,j,k] *= sin(i*j*k)
   end

   #println(state[2,2,2])

   return

end

function nestedloops6(nx, ny, nz)

   state = ones(nx,ny,nz)

   Threads.@threads for k = 1:nz
      Threads.@threads for j = 1:ny
         Threads.@threads for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return

end

function nestedloops7(nx, ny, nz)

   state = ones(nx,ny,nz)

   @sync Threads.@spawn for k = 1:nz
      @sync Threads.@spawn for j = 1:ny
         @sync Threads.@spawn for i = 1:nx
            state[i,j,k] *= sin(i*j*k)
         end
      end
   end

   #println(state[2,2,2])

   return

end

function nestedloops8(nx, ny, nz)

   state = ones(nx,ny,nz)

   @sync Threads.@spawn for k = 1:nz, j = 1:ny, i = 1:nx
      state[i,j,k] *= sin(i*j*k)
   end

   #println(state[2,2,2])

   return

end

##
nx, ny, nk = 200, 200, 200
nestedloops1(nx, ny, nk)
nestedloops2(nx, ny, nk)
nestedloops3(nx, ny, nk)
nestedloops4(nx, ny, nk)
nestedloops5(nx, ny, nk)
nestedloops6(nx, ny, nk)
nestedloops7(nx, ny, nk)
nestedloops8(nx, ny, nk)

println("Number of threads = ",Threads.nthreads())
println("base line:")
@time nestedloops1(nx, ny, nk)
println("explicit @inbound:")
@time nestedloops2(nx, ny, nk)
println("@threads on the outer loop:")
@time nestedloops3(nx, ny, nk)
println("@spawn on the outer loop:")
@time nestedloops4(nx, ny, nk)
println("nested loop:")
@time nestedloops5(nx, ny, nk)
println("@threads on the triple loops:")
@time nestedloops6(nx, ny, nk)
println("@spawn on the triple loops:")
@time nestedloops7(nx, ny, nk)
println("@spawn on the nested loops:")
@time nestedloops8(nx, ny, nk)

```

which gives

```julia
Number of threads = 2
base line:
  0.209827 seconds (6 allocations: 61.035 MiB)
explicit @inbound:
  0.215929 seconds (6 allocations: 61.035 MiB, 4.34% gc time)
@threads on the outer loop:
  0.131187 seconds (24 allocations: 61.037 MiB)
@spawn on the outer loop:
  0.236467 seconds (17 allocations: 61.036 MiB, 4.39% gc time)
nested loop:
  0.212745 seconds (6 allocations: 61.035 MiB)
@threads on the triple loops:
  0.313132 seconds (221.97 k allocations: 77.209 MiB, 3.14% gc time)
@spawn on the triple loops:
  0.352818 seconds (444.76 k allocations: 95.426 MiB)
@spawn on the nested loops:
  0.246418 seconds (17 allocations: 61.036 MiB, 5.74% gc time)

```

The only speedup I see from this result is the `@threads` on the outermost loop, which is kind of unexpected to me…

---

<div class="post-metadata">

**Author:** ![lungben](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lungben/32/12314_2.png) [@lungben](https://discourse.julialang.org/u/lungben)\
**Post date:** [March 15, 2020, 9:04pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/11 "2020-03-15T21:04:40Z")

</div>

You need to add `@sync` for your `@spawn` versions, otherwise the timer just measures the time to start the tasks and does not wait until they finish.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 15, 2020, 9:43pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/12 "2020-03-15T21:43:31Z")

</div>

Nested `@threads` works in Julia 1.3 and later in the sense it doesn’t crash (before, it sometimes did, IIRC). But parallelization only happens at the outer-most `for` loop. So, if you want load-balance across multiple levels of `for` loops, I don’t think `@threads` is a good option.

FWIW, I think we need a better tooling for threading in Julia. `@spawn` is too much of a foot-gun for high-level programming and `@threads` is too limited for nested case. FYI, I’m packaging up a high-level threading API as [ThreadsX.jl](https://github.com/tkf/ThreadsX.jl) which includes [`ThreadsX.foreach`](https://tkf.github.io/ThreadsX.jl/dev/#ThreadsX.foreach) that supports (possibly nested) parallel loops. I requested registration a few days ago so hopefully this will be registered soon.

---

<div class="post-metadata">

**Author:** ![henry2004y](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henry2004y/32/9284_2.png) [@henry2004y](https://discourse.julialang.org/u/henry2004y)\
**Post date:** [March 15, 2020, 9:46pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/13 "2020-03-15T21:46:32Z")

</div>

But my original timings are for the whole function scope, not just the loops. Does it still matter?

I am puzzled by the result that after I added `@sync` there’s literally no speedup. Also, if I say

```julia
function nestedloops8(nx, ny, nz)

   state = ones(nx,ny,nz)

   @sync for k = 1:nz, j = 1:ny, i = 1:nx
      Threads.@spawn state[i,j,k] *= sin(i*j*k)
   end

   #println(state[2,2,2])

   return

end

```

It will get stuck.

---

<div class="post-metadata">

**Author:** ![henry2004y](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henry2004y/32/9284_2.png) [@henry2004y](https://discourse.julialang.org/u/henry2004y)\
**Post date:** [March 15, 2020, 9:53pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/14 "2020-03-15T21:53:15Z")

</div>

That clarifies some of my doubts. However, why is my `@spawn` version not working as expected?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 15, 2020, 10:09pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/15 "2020-03-15T22:09:47Z")

</div>

Your `nestedloops8` seems to be using `@sync` and `@spawn` correctly (though not very efficiently). It works for me with small inputs like `nestedloops8(2, 3, 4)`. But, when `n`s are big, I think it’ll spawn too many tasks. Since `@spawn` has some overhead, you need to “chunk” the iteration space into reasonably large sub-regions for computations like this.

---

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [March 21, 2021, 5:32pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/16 "2021-03-21T17:32:53Z")

</div>

Indeed this returns a “LoadError: ArgumentError: nested outer loops are not currently supported by @threads”:

```julia
a = [1,2,]
b = [10,20,30]

Threads.@threads for i in a, j in b
    println("$i $j")
end

```

Does a “combinatorics” function exists that returns all the “combinations” of a nested loop, so I could write instead something like:

```julia
Threads.@threads for (i,j) in allCombinations(a,b)
    ...
end

```

I don’t care about the order of the specific combination as much as they remain deterministically specified…

EDIT: This seems to work (still to be fully tested, at least it doesn’t error…):

```julia
Threads.@threads for (i,j) in collect(Iterators.product(a,b))
    println("$i $j")
end

```

---

<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:** [March 21, 2021, 5:56pm UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/17 "2021-03-21T17:56:41Z")

</div>

> [@henry2004y](#):
>
> I am wondering how to apply multi-threading to nested for loops.

You can use a loop over a [`CartesianIndices` range](https://docs.julialang.org/en/v1/base/arrays/#Base.IteratorsMD.CartesianIndices), which essentially combines multiple nested loops into a single loop that works with `@threads`. For example:

```julia
 function nestedloops!(state)
    Threads.@threads for ijk in CartesianIndices(state)
        state[ijk] *= sin(prod(Tuple(ijk)))
    end
    return state
end

```

> [@sylvaticus](#):
>
> `Threads.@threads for (i,j) in collect(Iterators.product(a,b))`

This is a less efficient way to do the same thing, since `collect` actually allocates an array to hold the list of indices.

---

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [March 22, 2021, 9:56am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/18 "2021-03-22T09:56:30Z")

</div>

Thank you.  
I think I got about CartesianInddices.  
This is applied to the original example:

```julia
a = [1,2,]
b = [10,20,30]
Threads.@threads for ij in CartesianIndices((length(a),length(b)))
       (ai, bj) = a[Tuple(ij)[1]], b[Tuple(ij)[2]]
       println("$ai - $bj")
end

```

---

<div class="post-metadata">

**Author:** ![qsong](https://avatars.discourse-cdn.com/v4/letter/q/d07c76/32.png) [@qsong](https://discourse.julialang.org/u/qsong)\
**Post date:** [March 24, 2021, 7:28am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/19 "2021-03-24T07:28:55Z")

</div>

Just curious: what difference `@sync` would make before `@threads`? Thanks.

> [@pbayer](#):
>
> `@sync @threads for i in 1:N`

---

<div class="post-metadata">

**Author:** ![pbayer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pbayer/32/11675_2.png) [@pbayer](https://discourse.julialang.org/u/pbayer)\
**Post date:** [March 24, 2021, 8:02am UTC](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002/20 "2021-03-24T08:02:35Z")

</div>

> [@qsong](#):
>
> what difference `@sync` would make before `@threads` ?

The [julia manual](https://docs.julialang.org/en/v1.6-dev/base/parallel/#Base.@sync) says:

> ```
> @sync
> 
> ```
> 
> Wait until all lexically-enclosed uses of `@async` , `@spawn` , `@spawnat` and `@distributed` are complete. All exceptions thrown by enclosed async operations are collected and thrown as a `CompositeException‘ .

Otherwise you wouldn’t know when the started tasks have finished. In the above example you want all parallel computations to finish before printing the results.

[Next page](https://discourse.julialang.org/t/multithreading-for-nested-loops/36002.md?page=2)