# Summing arrays efficiently

**URL:** <https://discourse.julialang.org/t/summing-arrays-efficiently/15338>\
**Category:** Performance\
**Created:** [September 22, 2018, 12:43pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338 "2018-09-22T12:43:58Z")\
**Posts on this page:** 10\
**Page:** 1

<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:** [September 22, 2018, 12:43pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/1 "2018-09-22T12:43:58Z")

</div>

```julia
N = 1024 ^ 2;
A = [ones(N), ones(N), ones(N), ones(N)];

```

The naive way of summing the arrays in `A` would be to do `sum(A)`. However, note the performance:

```julia
julia> @btime sum(A);
  7.968 ms (6 allocations: 24.00 MiB)

```

It unnecessarily allocates an array of size `N` for each addition (3x8 MB). Is there a way around this, or is the recommended approach to write a for loop, i.e.:

```julia
julia> @btime (S = copy(A[1]); for B in A[2:end]; S .+= B; end; S);
  4.818 ms (13 allocations: 8.00 MiB)

```

---

<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:** [September 22, 2018, 1:10pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/2 "2018-09-22T13:10:32Z")

</div>

> [@bennedich](#):
>
> N = 1024 ^ 2; A = [ones(N), ones(N), ones(N), ones(N)];

Try `sum(sum.(A))`

```julia
julia> @btime sum(sum.($A))
  1.876 ms (1 allocation: 112 bytes)
4.194304e6

```

---

<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:** [September 22, 2018, 1:13pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/3 "2018-09-22T13:13:11Z")

</div>

Or, to go completely allocation free

```julia
julia> @btime sum(a->sum(a),$A)
  1.873 ms (0 allocations: 0 bytes)
4.194304e6

```

---

<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:** [September 22, 2018, 1:26pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/4 "2018-09-22T13:26:40Z")

</div>

Thanks! But the result I’m after here is an array which is the element wise sum of the 4 other arrays, and not the total sum of the individual elements.

---

<div class="post-metadata">

**Author:** ![improbable22](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/improbable22/32/5464_2.png) [@improbable22](https://discourse.julialang.org/u/improbable22)\
**Post date:** [September 22, 2018, 1:42pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/5 "2018-09-22T13:42:16Z")

</div>

If you don’t mind overwriting A then this would work:

```julia
A = [ones(2^10) for i=1:4];
sum(A)'
reduce((x,y) -> begin x .+= y; x end, A)'
A

using BenchmarkTools
@btime sum(A);
@btime reduce((x,y) -> begin x .+= y; x end, $A);

```

Edit: perhaps I should think more about `foldl` vs `reduce` here, but right now I think it’s OK.

---

<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:** [September 22, 2018, 1:45pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/6 "2018-09-22T13:45:06Z")

</div>

Or similarily, but without overwriting `A`

```julia
N = 1024 ^ 2;
A = [ones(N), ones(N), ones(N), ones(N)];
@time r = zeros(size(A[1]));reduce((x,y)->(x .+= y),A, init=r);
 0.002367 seconds (7 allocations: 8.000 MiB)

```

---

<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:** [September 22, 2018, 1:49pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/7 "2018-09-22T13:49:51Z")

</div>

This version looks a bit more pleasing

```julia
N = 1024 ^ 2;
A = [ones(N), ones(N), ones(N), ones(N)];
a ⊕ b = a .+= b
@time r = reduce(⊕, A, init=zeros(size(A[1])))
 0.009119 seconds (15 allocations: 8.001 MiB)

```

If the operator (`⊕, \oplus`) looks confusing, I found this interesting operator that might better correspond to what is done `⥆ \leftarrowplus` 😁

---

<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:** [September 22, 2018, 2:16pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/8 "2018-09-22T14:16:18Z")

</div>

Thanks! That should work. I modified it to make it slightly more efficient:

```julia
julia> @btime reduce(⊕, view(A,2:length(A)), init=copy(A[1]));
  3.578 ms (8 allocations: 8.00 MiB)

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 22, 2018, 2:20pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/9 "2018-09-22T14:20:06Z")

</div>

> [@baggepinnen](#):
>
> Or, to go completely allocation free
> 
> ```julia
> julia> @btime sum(a->sum(a),$A)
> 1.873 ms (0 allocations: 0 bytes)
> 4.194304e6
> 
> ```

Shouldn’t that be `sum(sum, A)`?

---

<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:** [September 22, 2018, 2:20pm UTC](https://discourse.julialang.org/t/summing-arrays-efficiently/15338/10 "2018-09-22T14:20:44Z")

</div>

Yes you are right!