# Avoid temporary array creation for the argument of \`reduce\`

**URL:** <https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464>\
**Category:** General Usage\
**Created:** [June 26, 2017, 7:42am UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464 "2017-06-26T07:42:07Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![fjarri](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fjarri/32/630_2.png) [@fjarri](https://discourse.julialang.org/u/fjarri)\
**Post date:** [June 26, 2017, 7:42am UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/1 "2017-06-26T07:42:07Z")

</div>

It is common to reduce (e.g. sum) the result of an array expression without needing the whole resulting array itself. In this case Julia will still create a temporary array to pass to the function, even if you managed to avoid temporary arrays before by taking advantage of loop fusion. Is there some way to skip that for reduction somehow? Perhaps some macro or specialized function?

If the reduced expression has only one array argument, one can use `mapreduce()`, but since it only accepts one iterator, for an expression with several arrays `zip()` is required which degrades the performance (it also looks somewhat ugly without tuple destructuring). As an example:

```julia
function test_vectorized(x, y)
    sqrt(sum((x .- y) .^ 2))
end

function test_devectorized(x, y)
    s = zero(eltype(x))
    @inbounds @simd for i in 1:length(x)
        s += (x[i] - y[i])^2
    end
    sqrt(s)
end

function test_mapreduce(x, y)
    sqrt(mapreduce(p -> (p[1]-p[2])^2, +, zip(x, y)))
end

x = rand(100000000)
y = rand(100000000)

r1 = test_vectorized(x, y)
@time test_vectorized(x, y)

r2 = test_devectorized(x, y)
@time test_devectorized(x, y)

r3 = test_mapreduce(x, y)
@time test_mapreduce(x, y)

@assert isapprox(r1, r2)
@assert isapprox(r1, r3)

```

The result:

```julia
  0.575121 seconds (87 allocations: 762.946 MiB, 18.08% gc time)
  0.094775 seconds (5 allocations: 176 bytes)
  0.140150 seconds (9 allocations: 272 bytes)

```

Is there a better way to do this kind of calculation without resorting to devectorization?

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [June 26, 2017, 1:48pm UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/2 "2017-06-26T13:48:21Z")

</div>

You can do `sqrt(sum((a - b)^2 for (a, b) in zip(x, y)))`, but it’s quite verbose and I’m not sure how it will perform. A reduction syntax which would automatically be combined with dot broadcasting operations has been discussed, but no solution exists yet. See for example [this comment](https://github.com/JuliaLang/julia/issues/16285#issuecomment-237320513).

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [June 26, 2017, 2:13pm UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/3 "2017-06-26T14:13:24Z")

</div>

Another way to do this is: `norm(x-y)`. It is the most character economical but allocates another array. Perhaps an iterator/stream/generator version of `norm` can be defined.

IMHO the `mapreduce` version is fast enough but the indexing is annoying aesthetically, so I defined:

```julia
import Base: mapreduce
mapreduce(f, op, v0, itr1, itr2) = mapreduce(t->f(t[1],t[2]),op,v0, zip(itr1,itr2))

```

and then the `mapreduce` flows better:

```julia
sqrt(mapreduce((x,y)->(x-y)^2,+,0.0,x,y))

```

And runs quite decently fast.

---

<div class="post-metadata">

**Author:** ![fjarri](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fjarri/32/630_2.png) [@fjarri](https://discourse.julialang.org/u/fjarri)\
**Post date:** [June 27, 2017, 2:44am UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/4 "2017-06-27T02:44:04Z")

</div>

> [@nalimilan](#):
>
> You can do sqrt(sum((a - b)^2 for (a, b) in zip(x, y))), but it’s quite verbose and I’m not sure how it will perform.

Better than `test_vectorized()`, but worse than `test_mapreduce()`, unfortunately.

> [@nalimilan](#):
>
> A reduction syntax which would automatically be combined with dot broadcasting operations has been discussed, but no solution exists yet. See for example this comment.

Thanks for the link, glad to see I’m not the only one who needs this functionality.

---

<div class="post-metadata">

**Author:** ![fjarri](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fjarri/32/630_2.png) [@fjarri](https://discourse.julialang.org/u/fjarri)\
**Post date:** [June 27, 2017, 2:48am UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/5 "2017-06-27T02:48:18Z")

</div>

> [@Dan](#):
>
> Another way to do this is: norm(x-y).

It is actually as slow as `test_vectorized()`, because `norm()` is still a fusion boundary. Plus, the norm is just an example, I have various expressions I need to sum.

> [@Dan](#):
>
> IMHO the mapreduce version is fast enough but the indexing is annoying aesthetically, so I defined:

Yes, that’s what I ended up with as well. Still 50% slower than devectorized code, but at least not as slow as just `sum()`.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [August 30, 2019, 10:46pm UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/6 "2019-08-30T22:46:31Z")

</div>

Just stumbled on this old discussion - and I was wondering, since a lot has changed since then, esp. with broadcasting, is there work going on regarding elision of temporary arrays?

It just so … imperfect … that `sum(log.(A))` allocates a temporary array (`mapreduce(log, +, A)` won’t, of course). Nowadays, we could use

```julia
sum(Base.broadcasted(log, A))

```

It works, but it’s kinda verbose, and doesn’t support dot-notation. If there was a way to say “don’t materialize my broadcast here” … is there something going on in that direction? I’d be surprised if people haven’t thought about it already (some probably in depth).

It might also be help if `Base.broadcasted` were a (read-only) `AbstractArray`, e.g. to allow multi-threaded operation. Or alternatively, if there was a standard option to materialize it as a some kind of mapped-array type. But maybe this has been considered too already (and possibly been rejected for good reasons)?

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [August 30, 2019, 11:03pm UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/7 "2019-08-30T23:03:29Z")

</div>

> [@oschulz](#):
>
> It might also be help if `Base.broadcasted` were a (read-only) `AbstractArray`

Only in cases were all bcast arguments are arrays, of course (via bcast style?).

---

<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:** [August 30, 2019, 11:30pm UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/8 "2019-08-30T23:30:51Z")

</div>

> [@oschulz](#):
>
> If there was a way to say “don’t materialize my broadcast here” … is there something going on in that direction?

Using `@~` from [LazyArrays.jl](https://github.com/JuliaArrays/LazyArrays.jl), you can write `sum(@~ log.(A))`. In Julia itself, the discussion is happening at:

> <https://github.com/JuliaLang/julia/issues/19198>
>
> The notation \`f.(v)\` effectively maps \`f\` over an array \`v\`. This operation is n…ot lazy, it materializes the mapped array.
> 
> I think it could be useful to have an analogous notation for lazy maps. Maybe \`f..(v)\`? Instead of materializing the mapped array, this should return something equivalent to the generator:
> 
> \`\`\`(f(x) for x in v)\`\`\`
> 
> For example, this could be useful to do something like:
> 
> \`\`\`sum(f..(v))\`\`\`
> 
> which is more efficient than materializing the intermediate array in:
> 
> \`\`\`sum(f.(v))\`\`\`
> 
> Of course right now \`sum\` takes an optional function argument, so one can write \`sum(f,v)\`. But see the discussion here: https://github.com/JuliaLang/julia/issues/19146. If one decides to remove the method \`sum(f,v)\`, I think the notation \`sum(f..(v))\` could be a nice alternative.

> [@oschulz](#):
>
> It might also be help if `Base.broadcasted` were a (read-only) `AbstractArray`

See:

> <https://github.com/JuliaLang/julia/issues/32940>
>
> Would be useful for many packages, JuliennedArrays, LightQuery, SplitApplyCombin…e, MappedArrays, Query, etc. Base already has an AbstractEltypelessArray: the lazy broadcast machinery, it would just be a matter of formalizing the interface. Given that traits aren't coming any time soon, it couldn't be \`\<: AbstractArray\`, so we would have to duplicate all of the machinery for \`AbstactArrays\`. I could try to build a prototype if people are interested?

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [August 31, 2019, 10:03am UTC](https://discourse.julialang.org/t/avoid-temporary-array-creation-for-the-argument-of-reduce/4464/9 "2019-08-31T10:03:23Z")

</div>

Thanks for the links, @tkf! I was pretty sure that there would be a discussion about this going on somewhere, just didn’t manage to find it for some reason.