# Parallelizing a Nested Loop Concurrently
**URL:** https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402
**Category:** Performance
**Tags:** parallel, loops
**Created:** [January 28, 2022, 11:56pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402 "2022-01-28T23:56:07Z")
**Posts on this page:** 18
**Page:** 1
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 28, 2022, 11:56pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/1 "2022-01-28T23:56:07Z")
Hi! I am trying to code a problem in which I have two loops. An inner loop that a computes a sample average for a given agent using many many simulations of a particular function (which is not trivial, but each individual function is not excruciatingly slow either, it takes like one second) and in the outer loop I loop across different agents.
What is the best practice for paralellizing both the inner loop and the outer loop at the same time. Say, for a given agent, computing several simulations in parallel and at the same time computing the value for different agents in parallel.
```julia
using Random
const N = 1000
const S = 100000000
Data = rand(S,N)
function slow_inner_loop(data_n) # This function computes a sample average through Monte Carlo simulations
res_slow = zeros(S)
for s = 1 : S
res_slow[s] = data_n[s] # Here I have a function that computes a value for a given Monte Carlo Draw
end
return sum(res_slow)/S
end
function outer_loop(Data) # This function computes the sample average for N different "agents" and then computes a function with the computed averages
res_outer = zeros(N)
for n = 1 : N
res_outer[n] = slow_inner_loop(Data[:,n])
end
return sum(res_outer)/N
end
outer_loop(Data)
```
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [January 29, 2022, 12:15am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/2 "2022-01-29T00:15:01Z")
My shot at it can be, leave it to the masters (in this case, FLoops). I played with it now, and this is what I get here:
```julia
using Random
using FLoops
function mc()
sleep(0.01)
return 0.5
end
function slow_inner_loop(data_n) # This function computes a sample average through Monte Carlo simulations
S = length(data_n)
res_slow = zeros(S)
for s = 1 : S
res_slow[s] = mc()
end
return sum(res_slow)/S
end
function slow_inner_loop_floops(data_n) # This function computes a sample average through Monte Carlo simulations
S = length(data_n)
@floop for s = 1 : S
mc_s = mc()
@reduce( res_slow = zero(eltype(data_n)) + mc_s )
end
return sum(res_slow)/S
end
function outer_loop(Data) # This function computes the sample average for N different "agents" and then computes a function with the computed averages
N = size(Data,2)
res_outer = zeros(N)
for n = 1 : N
res_outer[n] = slow_inner_loop(Data[:,n])
end
return sum(res_outer)/N
end
function outer_loop_floops(Data) # This function computes the sample average for N different "agents" and then computes a function with the computed averages
N = size(Data,2)
@floop for n = 1 : N
r_inner = slow_inner_loop(Data[:,n])
@reduce(res_outer = zero(eltype(Data)) + r_inner)
end
return sum(res_outer)/N
end
function test(;N=10,S=100)
data = rand(S,N)
println("Serial")
outer_loop(rand(10,5))
@time (r1 = outer_loop(data))
println("FLoops:")
outer_loop_floops(rand(10,5))
@time (r2 = outer_loop_floops(data))
r1 ≈ r2
end
```
With that, I get:
```julia
julia> test()
Serial
11.316991 seconds (5.09 k allocations: 172.938 KiB)
FLoops:
1.172280 seconds (5.15 k allocations: 175.453 KiB)
true
```
Which means that `@floop` took the total time from 11 seconds to 1.17 seconds (here with 8 threads). I guess it is not only the parallelization which the macro is improving here, but the result is great overall, and probably the nested parallelization here is as good as it can be.
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 29, 2022, 12:26am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/3 "2022-01-29T00:26:55Z")
Hi @lmiq this is amazing. Just a quick follow up.
Assume that in `outer_loop_floops()` I actually want to store the value for each `n`. What would be the proper way to do this?
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [January 29, 2022, 12:29am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/4 "2022-01-29T00:29:40Z")
How did the code produce better than ideal speedup?
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [January 29, 2022, 12:37am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/5 "2022-01-29T00:37:04Z")
FYI, you can also write it as `Folds.sum(f, Data) / S / N` where `f` is the function you’d use on `data_n[s]`. Or, if you really want to do it as a nested loop (e.g., `S` is different for each inner loop) you can do `Folds.sum(Folds.sum(f, @view Data[:, n]) / S for n in axes(Data, 2)) / N`.
See also:
- [A quick introduction to data parallelism in Julia](https://juliafolds.github.io/data-parallelism/tutorials/quick-introduction/)
- [GitHub - JuliaFolds/Folds.jl: A unified interface for sequential, threaded, and distributed fold](https://github.com/JuliaFolds/Folds.jl)
- [https://github.com/tkf/ThreadsX.jl](https://github.com/tkf/ThreadsX.jl)
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [January 29, 2022, 12:43am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/6 "2022-01-29T00:43:01Z")
> [@jmcastro2109](#):
>
> I actually want to store the value for each `n` .
I guess you need to preallocate an array to store that data, and annotate it there. Nothing special (there is no concurrency there, as far as I can see).
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 29, 2022, 12:52am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/7 "2022-01-29T00:52:26Z")
But with SharedArrays?
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 29, 2022, 12:53am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/8 "2022-01-29T00:53:48Z")
With the `Folds.` would it be running in parallel? `S` is always the same across `n`’s. Which package should I upload to use this?
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [January 29, 2022, 1:01am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/9 "2022-01-29T01:01:22Z")
> [@PetrKryslUCSD](#):
>
> How did the code produce better than ideal speedup?
I don’t know, but the low hanging fruit in the serial code is to use a view for `Data[:,n]`, and the macro may be doing something smart with it.
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [January 29, 2022, 1:02am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/10 "2022-01-29T01:02:29Z")
> [@jmcastro2109](#):
>
> But with SharedArrays?
I’ve no experience with these.
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [January 29, 2022, 2:57am UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/11 "2022-01-29T02:57:08Z")
> [@jmcastro2109](#):
>
> With the `Folds.` would it be running in parallel? `S` is always the same across `n` 's. Which package should I upload to use this?
Yes, `Folds` functions are all parallel (by default). Folds.jl is here: [https://github.com/JuliaFolds/Folds.jl](https://github.com/JuliaFolds/Folds.jl). To start parallel programming in Julia, see: [A quick introduction to data parallelism in Julia](https://juliafolds.github.io/data-parallelism/tutorials/quick-introduction/)
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 29, 2022, 3:24pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/13 "2022-01-29T15:24:25Z")
Should one option be faster than the other?
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [January 29, 2022, 8:18pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/14 "2022-01-29T20:18:11Z")
What are you comparing?
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [January 29, 2022, 8:33pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/15 "2022-01-29T20:33:03Z")
FLoops vrs Folds
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [January 29, 2022, 8:37pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/16 "2022-01-29T20:37:43Z")
There should be typically no performance difference. But, if something can be done with Folds, I’d recommend Folds. FLoops is more flexible so you can mess things up easily but it also means that you can hand-optimize things.
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [February 1, 2022, 1:58pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/17 "2022-02-01T13:58:56Z")
Is there a way to use `pmap` in the inner loop and `@floops` in the outer loop?
Or to do this with `Distributed` instead of multithreading?
Providing a little bit of context, the current solution based on FLoops spends a lot of time in Garbage Collection and uses a lot of memory. In this post, @odow provides a version based on `Distributed` which has comparable speed but uses much less memory.
> [@Improve performance of a code with very large % of Garbage Collection](https://discourse.julialang.org/t/improve-performance-of-a-code-with-very-large-of-garbage-collection/75548):
>
> Hello, I am trying to squeeze performance of the following code as much as possible. When I benchmark it, I get a very large number for the garbage collection statistic (see below). Does anyone have any recommendation for addressing this issue? using JuMP, Ipopt, LinearAlgebra, Random, Distributions, BenchmarkTools, MosekTools, NLopt, Plots, FLoops Threads.nthreads() const N = 100 const Ι = 250 const J = 50 const σ = 5 const α = 0.15 const S= 100 Random.seed!(2109) zbar = rand(Ι) variance =…
---
### Author:  [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)
#### Post date: [February 1, 2022, 5:08pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/18 "2022-02-01T17:08:38Z")
@lmiq
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [February 1, 2022, 5:23pm UTC](https://discourse.julialang.org/t/parallelizing-a-nested-loop-concurrently/75402/19 "2022-02-01T17:23:03Z")
I think you need to follow the directions that where given in the other thread, that is, you should not create a model at every iteration of the loop. I am not that familiar with JuMP to know how exactly to do that, but I can imagine that one alternative is to create a model for each thread, and update the data/iniital values of that model in hot loops inside each thread.
Maybe a pattern like
```julia
for threads in 1:Threads.nthreads()
model = JuMP.model(...)
for trail in 1:ntrials
# update model parameters for this thread
end
end
```