# Sum of n array by recursion in Parallel threads using spawn

**URL:** <https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751>\
**Category:** General Usage\
**Tags:** question, parallel, recursion\
**Created:** [February 6, 2021, 7:24pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751 "2021-02-06T19:24:00Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 6, 2021, 7:24pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/1 "2021-02-06T19:24:00Z")

</div>

I am creating a function that will be call n number of times in recursion to sum the elements of an array in parallel using spawn to divide the array into two parts.

For example Recursion(a, lo, hi)

a = (1,5,6,7,8,8,8,8,9,9)

rt1 = recurision(a, lo, mid)  
rt2 = recursion(a, mid+1, hi)

then adding the sum of the return values from the first and second call. I am unable to store the values of rt1 and rt2 in a global variable to return the total sum of an array.

---

<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:** [February 6, 2021, 7:26pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/2 "2021-02-06T19:26:07Z")

</div>

what have you tried so far?

---

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 6, 2021, 7:46pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/3 "2021-02-06T19:46:26Z")

</div>

The problem is when I return the sum, it only returns the sum of the last two recursions, because I have to initialize the value of the return which gets reset in every run

---

<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:** [February 6, 2021, 7:52pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/4 "2021-02-06T19:52:44Z")

</div>

you’re doing it wrong if your “recursion” modifies/relies on some global variable

---

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 6, 2021, 7:59pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/5 "2021-02-06T19:59:14Z")

</div>

Can you please suggest the right way?

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [February 6, 2021, 8:18pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/6 "2021-02-06T20:18:21Z")

</div>

Here is the naive way of recursively writing the Fibonacci sequence:

```julia
julia> function fib(n)
           if n > 1
               fib(n-1) + fib(n-2)
           else
               n
           end
       end
fib (generic function with 1 method)

```

See how at each recursive step, you pass a the decremented argument back to the function? You can do something very similar with `sum`, except it’d involve splitting original the array into halves at each step recursively (and ideally, using `view` so you don’t allocate a whole new array each time)

* * *

By the way, if you’re looking for a ready-made parallel sum, check out the [ThreadsX.jl](https://github.com/tkf/ThreadsX.jl) package:

```julia
julia> using ThreadsX

julia> let v = randn(1_000_000)
           s1 = @btime ThreadsX.sum($v, basesize=100_000)
           s2 = @btime sum($v)
           s1 ≈ s2
       end
  75.279 μs (860 allocations: 36.28 KiB)
  251.748 μs (0 allocations: 0 bytes)
true

```

For smaller array sizes it’s pretty easy to do a lot better than ThreadsX is doing here unfortunately. Not really sure what’s wrong with it’s strategy, but a simple recursive `@spawn` sum can be a fair bit faster for smaller arrays.

---

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 6, 2021, 9:12pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/7 "2021-02-06T21:12:31Z")

</div>

Thanks, I am aware of the basic recursive functions, but here when I use Spawn to divide the tasks and run them in parallel, I am unable to get the point of summing the output of spawned tasks.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [February 6, 2021, 9:19pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/8 "2021-02-06T21:19:09Z")

</div>

> Thanks, I am aware of the basic recursive functions,

Ah sorry, it’s a little hard to understand what you do and don’t know here, as the way you talked about using a global variable was setting off a lot of warning lights for me.

* * *

> when I use Spawn to divide the tasks and run them in parallel, I am unable to get the point of summing the output of spawned tasks.

Does this help?

```julia
function fib(n::Int)
    if n < 2
        return n
    end
    t = @spawn fib(n - 2)
    return fib(n - 1) + fetch(t)
end

```

The idea is that you first spawn one task, then do the other computation, and then use `fetch` to get the result of the first task and add them together.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [February 6, 2021, 10:18pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/9 "2021-02-06T22:18:30Z")

</div>

If you post the code that you already have, it will be easier to help.

---

<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:** [February 6, 2021, 11:39pm UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/10 "2021-02-06T23:39:16Z")

</div>

If you just want to sum one array in parallel, a nice simple way to do it is

```julia
function tsum(xs)
    if length(xs) <= 1048576
        return sum(xs) # base case
    else
        t = Threads.@spawn tsum(@view xs[begin:begin+(end-begin+1)÷2])
        return tsum(@view xs[begin+(end-begin+1)÷2+1:end]) + fetch(t)
    end
end

```

---

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 7, 2021, 12:20am UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/11 "2021-02-07T00:20:12Z")

</div>

Perfect solution, thanks and it worked.

---

<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:** [February 7, 2021, 12:30am UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/12 "2021-02-07T00:30:19Z")

</div>

By the way, unless you wnat to _learn_ how to implement parallel very low-level code, I strongly advice to _not_ use `@spawn` directly. It’s especially true for a high-level task like this. FYI, I wrote an overview for the high-level approach here: [A quick introduction to data parallelism in Julia](https://juliafolds.github.io/data-parallelism/tutorials/quick-introduction/)

---

<div class="post-metadata">

**Author:** ![naviinkapoor](https://avatars.discourse-cdn.com/v4/letter/n/977dab/32.png) [@naviinkapoor](https://discourse.julialang.org/u/naviinkapoor)\
**Post date:** [February 7, 2021, 12:38am UTC](https://discourse.julialang.org/t/sum-of-n-array-by-recursion-in-parallel-threads-using-spawn/54751/13 "2021-02-07T00:38:11Z")

</div>

Thanks, I will surely read your article!