# The sum of an array is faster in the sequential version than in the parallelized version

**URL:** <https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171>\
**Category:** Julia at Scale\
**Created:** [October 11, 2018, 12:20pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171 "2018-10-11T12:20:03Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![dsHitman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dshitman/32/5465_2.png) [@dsHitman](https://discourse.julialang.org/u/dsHitman)\
**Post date:** [October 11, 2018, 12:20pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/1 "2018-10-11T12:20:04Z")

</div>

I have an i7 with 8 logical process but the sum of an array is faster in the sequential versione than in the parallel. Why? Am I doing something wrong? Thanks for the answers.

```julia
using Distributed

x = rand(1000000)
#println(x)

dim = size(x)[1]
println(dim)

t = @elapsed begin
    let
        cont = 0
        dim = size(x)[1]
        println(dim)
        for i in 1:dim

            cont = cont + x[i]

        end
        println(cont)
    end
end
println(t)

if (nworkers() != 4)
    addprocs(4)
end

t1 = @elapsed begin

    cont1 = @distributed (+) for i in 1:size(x)[1]
        x[i]
    end
    println(cont1)

end
println(t1)

```

---

<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:** [October 11, 2018, 12:43pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/2 "2018-10-11T12:43:26Z")

</div>

Parallelizing imposes a big communications overhead, which is especially huge in this example because your array `x` is all stored on the main process and the contents `x[i]` have to be sent to the subprocesses.

Also, [don’t benchmark in global scope](https://docs.julialang.org/en/v1/manual/performance-tips/#Avoid-global-variables-1).

---

<div class="post-metadata">

**Author:** ![dsHitman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dshitman/32/5465_2.png) [@dsHitman](https://discourse.julialang.org/u/dsHitman)\
**Post date:** [October 11, 2018, 12:53pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/3 "2018-10-11T12:53:00Z")

</div>

Thanks for the answer, I tried to use a SharedArray but is the same thing. Any suggestion?

---

<div class="post-metadata">

**Author:** ![dsHitman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dshitman/32/5465_2.png) [@dsHitman](https://discourse.julialang.org/u/dsHitman)\
**Post date:** [October 11, 2018, 1:25pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/4 "2018-10-11T13:25:29Z")

</div>

```julia
using Distributed, SharedArrays

x = rand(1000000)
#println(x)

dim = size(x)[1]
println(dim)

t = @elapsed begin
    let
        cont = 0
        dim = size(x)[1]
        println(dim)
        for i in 1:dim

            cont = cont + x[i]

        end
        println(cont)
    end
end
println(t)

if (nworkers() != 4)
    addprocs(4)
end

x1 = SharedArray(x)

t1 = @elapsed begin

    cont1 = @distributed (+) for i in 1:size(x1)[1]
        x1[i]
    end
    println(cont1)

end
println(t1)

```

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [October 11, 2018, 1:46pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/5 "2018-10-11T13:46:15Z")

</div>

`sum(x)` is simd accelerated, and therefore already ~4x faster than a real serial sum.  
So the first challenge is to preserve simd acceleration in your reduction. The second challenge is, that even with ~10^7 element arrays, a sum only takes around ~3.5ms - a low number that can easily be eaten up any multi threading overhead.  
This sum is a bit faster (1.4x) than Base.sum:

```julia
function threadsum(x::AbstractArray{T}) where T
    N = Threads.nthreads()
    result = similar(x, N)
    segment = floor(Int, length(x) / N) 
    Threads.@threads for id in 1:N
        accum = zero(T)
        start = (id - 1) * segment + 1
        @simd for i in start:(start + segment - 1)
            @inbounds (accum += x[i])
        end
        @inbounds result[id] = accum
    end
    res = sum(result)
    if segment * N != length(x)
        res += sum(view(x, (segment * N + 1):length(x)))
    end
    res
end

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [October 11, 2018, 1:51pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/6 "2018-10-11T13:51:43Z")

</div>

Your variable `cont` changes type from `Int` to `Float64` and is thus not type stable. Consider using `cont = zero(eltype(x))`, similar to sdanisch’s version.

---

<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:** [October 11, 2018, 2:29pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/7 "2018-10-11T14:29:53Z")

</div>

Also note that `sum` uses a pairwise-summation algorithm, which is substantially more accurate than a simple loop like this.

Summing a bunch of numbers is just a poor case for parallelization. You only want to think about parallelism when you have a computational task that is so slow it is impeding your work, and you have already made a good effort at speeding up the serial code (including going through the Julia performance tips … often the code by inexperienced Julia programmers can be sped up by a factor of 10 or more).

---

<div class="post-metadata">

**Author:** ![dsHitman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dshitman/32/5465_2.png) [@dsHitman](https://discourse.julialang.org/u/dsHitman)\
**Post date:** [October 11, 2018, 2:32pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/8 "2018-10-11T14:32:46Z")

</div>

The serial version is always faster. Thanks for the answer

---

<div class="post-metadata">

**Author:** ![dsHitman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dshitman/32/5465_2.png) [@dsHitman](https://discourse.julialang.org/u/dsHitman)\
**Post date:** [October 11, 2018, 2:36pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/9 "2018-10-11T14:36:49Z")

</div>

Thanks, I make this test with only sum because I want to parallelize a cellular automata but the same algorithm is faster in serial version than the version with parallelism and I don’t understend why 😕

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [October 11, 2018, 3:57pm UTC](https://discourse.julialang.org/t/the-sum-of-an-array-is-faster-in-the-sequential-version-than-in-the-parallelized-version/16171/10 "2018-10-11T15:57:19Z")

</div>

> [@sdanisch](#):
>
> This sum is a bit faster (1.4x) than Base.sum:

Putting my code review hat on, here’s a slightly cleaner way to split an array like that (less code repetition, it’s also more consistent since, as @stevengj points out, `sum` does not simply sum elements):

```julia
function threadsum(x::AbstractArray{T}) where T
    M = length(x)
    N = Threads.nthreads()
    result = similar(x, N)
    @inbounds Threads.@threads for t = 1:N
        accum = zero(T)
        @simd for i = round(Int, M*(t-1)/N)+1:round(Int, M*t/N)
            accum += x[i]
        end
        result[t] = accum
    end
    sum(result)
end

```