# Slow \`reduce(vcat, itr)\`

**URL:** <https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115>\
**Category:** Performance\
**Tags:** cat\
**Created:** [September 12, 2022, 7:50am UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115 "2022-09-12T07:50:56Z")\
**Posts on this page:** 7\
**Page:** 2

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [September 13, 2022, 3:38pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/21 "2022-09-13T15:38:05Z")

</div>

I aim to deprecate the idiom, not either function. What I mean is to stop encouraging people to use `reduce(vcat,...)`, discourage them from using it unless they’re trying to support old Julia versions, and instead encourage `stack` for this purpose.

Although _very technically_, removing the specializations would be non-breaking because a naive call to `reduce(vcat,...)` would return the correct answer – although with a staggering performance degradation. I don’t seriously propose doing this. The specializations can stick around at least until v2.0 and longer if they’re still entrenched.

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [September 13, 2022, 5:49pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/22 "2022-09-13T17:49:29Z")

</div>

> `reduce(vcat,...)` is problematic because (…)

Kinda agree: it always works and does what’s needed, but not always performant.  
It was a nice idea to try switching to fast path with `reduce(vcat, array)`, but turned out not to be intuitive and lacks predictable performance.

> looks like `stack` might already be the function we need

As planned for 1.9, `stack` will always, well, “stack” input arrays along a new dimension. That’s different from what `reduce(vcat)` does.  
Why cram yet another functionality into `stack`? `flatten` is a nice name, and present in both stdlibs (`Iterators`) and packages (eg `SplitApplyCombine.jl`) with the same meaning.

Not really arguing for inclusion of `flatten` into Base, btw - I think it’s totally fine to have such a function in a package. Base cannot contain all reasonable data manipulation functions anyway, the question is where to draw the line. But also not against inclusion, just neutral.

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [September 13, 2022, 6:00pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/23 "2022-09-13T18:00:06Z")

</div>

> [@aplavin](#):
>
> As planned for 1.9, `stack` will always, well, “stack” input arrays along a new dimension. That’s different from what `reduce(vcat)` does.

Thanks. You’re right. First I underestimated what `stack` was capable and people pointed out that it had a `dims` argument. But since then I’ve overestimated it in assuming that `dims` didn’t have to be a new dimension. I don’t have a 1.9 checkout so I haven’t been able to test it, but did take a closer look at the docstring.

So then there is a vacancy for a `concat(_;dims)` or `concatenate(_;dims)` function to generalize `cat(_...;dims)` for collections (as `maximum` is to `max`) and supersede `reduce(vcat,_)` and `reduce(hcat,_)`.

---

<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 13, 2022, 6:08pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/24 "2022-09-13T18:08:55Z")

</div>

> [@mikmoore](#):
>
> I don’t have a 1.9 checkout so I haven’t been able to test it

Installing and `using Compat` (or `using Compat: stack`) will allow you to test `stack`.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [September 13, 2022, 7:14pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/25 "2022-09-13T19:14:59Z")

</div>

> [@mikmoore](#):
>
> So then there is a vacancy for a `concat(_;dims)` or `concatenate(_;dims)` function to generalize `cat(_...;dims)` for collections (as `maximum` is to `max`) and supersede `reduce(vcat,_)` and `reduce(hcat,_)`.

Maybe the question here is: How often does anyone use these for operations which aren’t either `stack` or `flatten`? (Where `flatten` works like `collect ∘ Iterators.flatten`, but faster.)

`reduce(vcat, vec_of_matrices)` makes a matrix. But my impression is that its main use case is vectors of vectors, with other things just inherited from `vcat`. Even `reduce(vcat, [[i;;;] for i in 1:3])` works, but surely is pretty rare. (Edit: I presume that’s why the optimised method doesn’t bother to include this.) Do we need a new verb for these cases at all?

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [September 13, 2022, 9:11pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/26 "2022-09-13T21:11:48Z")

</div>

> [@mcabbott](#):
>
> Maybe the question here is: How often does anyone use these for operations which aren’t either `stack` or `flatten`?

Fair question. Indeed, I would imagine that a serious majority of cases are covered by `stack` and some others by `flatten`. But there is currently no function to efficiently concatenate 3-dimensional arrays along any of the first 3 dimensions (although `stack` could insert one). One can use `reshape` gymnastics to make it work in many more cases, but if I was happy with solutions like that I never would have left MATLAB.

> [@mcabbott](#):
>
> Even `reduce(vcat, [[i;;;] for i in 1:3])` works

Notice that your example produces the correct result (as `reduce` always does), but is not efficient because it misses the `reduce` specializations:

```julia
julia> z = [[i;;;] for i in 1:3]; @btime reduce(vcat, $z);
  1.210 μs (26 allocations: 960 bytes)

julia> z = [[i;;;] for i in 1:30]; @btime reduce(vcat, $z);
  18.100 μs (377 allocations: 16.66 KiB)

# superior despite a materialized broadcast
julia> z = [[i;;;] for i in 1:30]; @btime reshape(reduce(vcat, reshape.($z,1)),:,1,1);
  956.757 ns (65 allocations: 3.31 KiB)

```

EDIT: I guess I’m suggesting that concatenation is not an exotic operation and that it’s something that I’d expect a language like Julia (with its otherwise-excellent N-dimensional array support) to handle well. In its current state, it’s a minefield of performance traps that sometimes requires `reshape`-fu or writing your own concatenation functions.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [September 13, 2022, 11:03pm UTC](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115/27 "2022-09-13T23:03:50Z")

</div>

> [@aplavin](#):
>
> > `reduce(vcat,...)` is problematic because (…)
> 
> Kinda agree: it always works and does what’s needed, but not always performant.  
> It was a nice idea to try switching to fast path with `reduce(vcat, array)`, but turned out not to be intuitive and lacks predictable performance.

Also agreed. I think this is a case where we got burnt by the power of the language. I imagine someone said, “Oh neat, we can add a `reduce(typeof(vcat), ...)` method to get fast array concatenation,” which resulted in the `reduce(vcat, ...)` fast path being added to the language rather than a `stack` or `flatten` or `concat` function.

That’s not to say I wouldn’t have made the same mistake, just that hindsight is 20/20. 🙂

[Previous page](https://discourse.julialang.org/t/slow-reduce-vcat-itr/87115.md?page=1)
