# Allocations in mapreduce/sum etc

**URL:** <https://discourse.julialang.org/t/allocations-in-mapreduce-sum-etc/27053>\
**Category:** Performance\
**Created:** [July 31, 2019, 9:19pm UTC](https://discourse.julialang.org/t/allocations-in-mapreduce-sum-etc/27053 "2019-07-31T21:19:33Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![tchr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tchr/32/15138_2.png) [@tchr](https://discourse.julialang.org/u/tchr)\
**Post date:** [July 31, 2019, 9:19pm UTC](https://discourse.julialang.org/t/allocations-in-mapreduce-sum-etc/27053/1 "2019-07-31T21:19:33Z")

</div>

I’m confused by why the following allocates (this is a reduced example that arose from trying to implement a function from [#32739](https://github.com/JuliaLang/julia/pull/32739) via higher order functions instead of explicit loops):

```julia
g(v) = mapreduce(i->v[1]*i, +, eachindex(v))
v=rand(10)
@btime g($v)

```

Results in `... (1 allocation: 16 bytes)` on v1.1. How can I get rid of that allocation?

A similar thing happens with e.g. `sum(f, itr)` as soon as the passed function `f` contains reference to any element of a captured array:

```julia
_h(i,v) = i*v[i]
h(v) = sum(i->_h(i,v), eachindex(v))

```

also produces `... (1 allocation: 16 bytes)`.

I guess that suggests that the allocations are not really due to `mapreduce`, `foldl`, `sum`, or similar, but to the anonymous function itself? Still, I don’t really get why this happens.

[This was tested on julia-v1.1.1, btw.]

---

<div class="post-metadata">

**Author:** ![tchr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tchr/32/15138_2.png) [@tchr](https://discourse.julialang.org/u/tchr)\
**Post date:** [August 1, 2019, 2:29am UTC](https://discourse.julialang.org/t/allocations-in-mapreduce-sum-etc/27053/2 "2019-08-01T02:29:53Z")

</div>

For anyone who might stumble upon this in the future:

From some digging, this seems to basically be a consequence of two elements:

1. [#18207](https://github.com/JuliaLang/julia/issues/18207) (interplay of function arguments with recursive functions) and the [recursive elements of `mapreduce`](https://github.com/JuliaLang/julia/blob/927f7d83a8b555e3acc3558491288ab10bdd48ed/base/reduce.jl#L164-L165), and
2. an allocating [`throw(ArgumentError(...))` call](https://github.com/JuliaLang/julia/blob/927f7d83a8b555e3acc3558491288ab10bdd48ed/base/reduce.jl#L301) that handles empty-iterables inputs for non-specialized function input (oddly, this allocation can be removed by adding `@inline` to [`mymapreduce_empty(f,op,T)`](https://github.com/JuliaLang/julia/blob/927f7d83a8b555e3acc3558491288ab10bdd48ed/base/reduce.jl#L212), contrary to usual `@noinline`-strategy for avoiding [spurious `throw` allocations](https://github.com/JuliaLang/julia/issues/23281)).

Eliminating both of these elements removes the allocation noted above; but getting rid of recursion essentially butchers the method.

[~~It seems that recursion and zero allocations can co-exist, at least in principle, if specialization on the function input is forced via `mapreduce_impl(f::F, ...) where F<:Function` as suggested in [#18207(comment)](https://github.com/JuliaLang/julia/issues/18207#issuecomment-241872839); that’s probably not very viable for such a generic function though~~Scratch that; doesn’t actually seem to work for me.]

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [August 1, 2019, 4:11am UTC](https://discourse.julialang.org/t/allocations-in-mapreduce-sum-etc/27053/3 "2019-08-01T04:11:02Z")

</div>

I actually think that the root cause here is the fact that a closure over a non-`isbits` value (`v`) is created and subsequently passed to a non-inlined function (`mapreduce` or one of the functions it calls with the closure as an argument, recursively). The compiler essentially treats the function as a black box (or at least more so than if the function were inlined), and can’t figure out that the closure is short-lived; for all it knows, `mapreduce` could store a reference to the closure somewhere in a global array of objects. This means that the closure needs to be GC-rooted, which requires allocation.