# Very best way to concatenate an array of arrays

**URL:** <https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672>\
**Category:** General Usage\
**Tags:** arrays\
**Created:** [January 29, 2018, 3:29pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672 "2018-01-29T15:29:50Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [January 19, 2019, 2:07pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/21 "2019-01-19T14:07:39Z")

</div>

> [@Tamas\_Papp](#):
>
> making the extra marginal effort

Sometimes not so marginal. A while ago I wrote this (simplified here)

```julia
function merge_dict(ds...)
    t = eltype(ds)
    merge_dict!(t(),ds)
end

function merge_dict!(d::AbstractDict, others)
    for other in others
        @inbounds for (k,v) in other
            d[k] = v
        end
    end
    return d
end

```

```julia
julia> v = [Dict(rand(1:1000) => rand() for _ in 1:10) for _ in 1:10^4];

julia> @btime merge_dict(v...);
  2.191 ms (21 allocations: 327.00 KiB)

julia> @btime merge(v...);
ERROR: StackOverflowError:

julia> v = [Dict(rand(1:1000) => rand() for _ in 1:10) for _ in 1:10^3];

julia> @btime merge_dict(v...);
  236.527 μs (21 allocations: 116.06 KiB)

julia> @btime merge(v...);
  49.820 ms (11963 allocations: 27.52 MiB)

```

I submitted a PR about a year ago making this a method for `merge`. But, my version breaks type-stability, important in some cases, obviously not here. Still my code is useful in many situations (and I actually a use a version that takes a `Vector` rather than splatting. However splatting 10^3 and 10^4 arguments entails very little performance penalty.)

So I changed the PR, upon suggestion, to improve the efficiency of `reduce(merge, dicts)` instead. There were many choices, but getting the basic implementation was fast. Pushing the PR through was an odyssey. Because `reduce`, `Dicts`, and `merge` are so widely used, things have to be done carefully. I forgot, just looked now, that the PR still has not been merged. It was bumped less than a day ago.

It was a great learning experience, but quite a bit of effort. This depends also on how experienced you are at making PRs to base.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [January 20, 2019, 7:23pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/22 "2019-01-20T19:23:45Z")

</div>

just a curious: what is the reason to use `@inbounds` in `merge_dict!` function?

(BTW I needed to add word “function” to avoid [Interrobang](https://en.wikipedia.org/wiki/Interrobang)🙂 )

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [January 20, 2019, 9:23pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/23 "2019-01-20T21:23:36Z")

</div>

That’s a good question. It doesn’t seem to make sense. My best recollection is that I copied it from code in base. Or maybe I tried it and got a performance improvement.

---

<div class="post-metadata">

**Author:** ![kolia](https://avatars.discourse-cdn.com/v4/letter/k/c68b51/32.png) [@kolia](https://discourse.julialang.org/u/kolia)\
**Post date:** [January 22, 2019, 7:03pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/24 "2019-01-22T19:03:04Z")

</div>

[https://github.com/JuliaDiffEq/RecursiveArrayTools.jl/issues/49](https://github.com/JuliaDiffEq/RecursiveArrayTools.jl/issues/49)

---

<div class="post-metadata">

**Author:** ![DavidKMaslen](https://avatars.discourse-cdn.com/v4/letter/d/b5e925/32.png) [@DavidKMaslen](https://discourse.julialang.org/u/DavidKMaslen)\
**Post date:** [October 11, 2019, 5:59pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/25 "2019-10-11T17:59:32Z")

</div>

FWIW the relevant concept to implement here is possibly flatmap. Then flatten(vv) = flatmap(x-\>x, vv)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [October 12, 2019, 7:05am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/26 "2019-10-12T07:05:14Z")

</div>

My understanding is that with the PR above having been merged, this is now handled nicely in `Base` with `reduce(vcat, ...)`.

---

<div class="post-metadata">

**Author:** ![vvjn](https://avatars.discourse-cdn.com/v4/letter/v/5f9b8f/32.png) [@vvjn](https://discourse.julialang.org/u/vvjn)\
**Post date:** [October 12, 2019, 2:41pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/27 "2019-10-12T14:41:22Z")

</div>

This is the one function that I keep wanting to be in core Julia because I keep reimplementing or googling this function so much. I don’t think splatting huge arrays gives you good performance. Something like concatenate or vconcatenate and hconcatenate, analogous to maximum and max, would be really nice.

---

<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 12, 2019, 3:05pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/28 "2019-10-12T15:05:58Z")

</div>

Tamas solution is the one implemented in Base intended to solve this exact problem

---

<div class="post-metadata">

**Author:** ![DavidKMaslen](https://avatars.discourse-cdn.com/v4/letter/d/b5e925/32.png) [@DavidKMaslen](https://discourse.julialang.org/u/DavidKMaslen)\
**Post date:** [October 12, 2019, 3:22pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/29 "2019-10-12T15:22:51Z")

</div>

[Scratch the flatmap suggestion (for now).]

reduce(vcat, vector\_of\_vectors) seems to imply iteratively applying vcat — which seems like a possibly an inefficient way of doing this — and certainly there is nothing in the documentation to suggest otherwise. You can look at the code, but we shouldn’t want people to have to dive through reduce.jl just to understand what their code is doing. There is are some hints about reduce having specific implementations for different operations — which I mostly read as “this will do what you want, just trust us, but you will never know what your code does”.

I suppose it would be nice to know (i.e. be true and have documented), that there wasn’t one vector allocation happening per vector in vector\_of\_vectors. The other thing one might hope to happen would be for there to be just one allocation, though I suppose log(N=total size) might not be that bad (e.g. for appending to a growing vector). In any case someone using reduce(vcat, vector\_of\_vectors) is going to find it hard to know whether there are N allocations happening, or log(N), or 1 allocation, and whether either of the two “efficient” flatten approaches (filling up one pre-allocated vector or appending to a vector) is being used, or something else altogether.

---

<div class="post-metadata">

**Author:** ![DavidKMaslen](https://avatars.discourse-cdn.com/v4/letter/d/b5e925/32.png) [@DavidKMaslen](https://discourse.julialang.org/u/DavidKMaslen)\
**Post date:** [October 12, 2019, 3:27pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/30 "2019-10-12T15:27:54Z")

</div>

The documentation for reduce says:

" Reductions for certain commonly-used operators may have special implementations, and should be used instead: `maximum(itr)` , `minimum(itr)` , `sum(itr)` , `prod(itr)` , `any(itr)` , `all(itr)` ."

So I suppose to be consistent with the design intent expressed in the documentation that there should be a new function for the special implementation needed for reduce with the vcat operator.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [October 12, 2019, 4:08pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/31 "2019-10-12T16:08:22Z")

</div>

You seem to be misunderstanding something — there _is_ a specialized implementation of `reduce(vcat, ...)`, implemented by the PR linked above. The entry point is [here](https://github.com/JuliaLang/julia/blob/d9c84bf76303bd6233ce9b72bef2e9804424b642/base/abstractarray.jl#L1375).

It does the right thing, no extra allocations. This should be _both_ efficient and clear, a win-win.

> [@DavidKMaslen](#):
>
> There is are some hints about reduce having specific implementations for different operations — which I mostly read as “this will do what you want, just trust us, but you will never know what your code does”.

This is not true — of course you can learn what the code does, rather easily. Julia is open source.

If you think this could be documented better, please make a pull request:

> <https://github.com/JuliaLang/julia/blob/master/CONTRIBUTING.md#improving-documentation>

(Also, generally, it is not recommended to resurrect old topics unless there is a good reason.)

---

<div class="post-metadata">

**Author:** ![DavidKMaslen](https://avatars.discourse-cdn.com/v4/letter/d/b5e925/32.png) [@DavidKMaslen](https://discourse.julialang.org/u/DavidKMaslen)\
**Post date:** [October 12, 2019, 6:31pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/32 "2019-10-12T18:31:38Z")

</div>

Thanks. I also just used @benchmark to see how many allocations were being made and observed just 1.

Where would the documentation of this feature go? It’s a feature of reduce, but someone looking for advice on how to properly flatten a vector of vectors would be unlikely to look there.

On a completely personal note - I personally find myself not wanting to use reduce because the documentation explicitly states there are no guarantees either now, or in the future, on what it does.

---

<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:** [October 13, 2019, 8:14pm UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/33 "2019-10-13T20:14:56Z")

</div>

I guess the docstring for `reduce` should mention this. Anyway somebody looking for this is more likely to look at `?reduce` than at the docstring for a function… whose name he’s precisely looking for!

I’m surprised by the recommendation to use special methods like `maximum`, as these are defined precisely in terms of `reduce`. Maybe these are out of date. Can you file an issue in GitHub?

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [October 14, 2019, 1:18am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/34 "2019-10-14T01:18:11Z")

</div>

> [@DavidKMaslen](#):
>
> On a completely personal note - I personally find myself not wanting to use reduce because the documentation explicitly states there are no guarantees either now, or in the future, on what it does.

If the docs are giving you that impression we should tweak them a bit. Do you refer to the following?

> If provided, the initial value `init` must be a neutral element for `op` that will be returned for empty collections. It is unspecified whether `init` is used for non-empty collections.

This does seem strange especially given that one of the examples violates this rule by using something other than the multiplicative identity in `reduce(*, [2; 3; 4]; init=-1) == -24`, demonstrating that the value of `init` is used in this case.

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [October 14, 2019, 3:59am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/35 "2019-10-14T03:59:25Z")

</div>

> [@nalimilan](#):
>
> I’m surprised by the recommendation to use special methods like `maximum` , as these are defined precisely in terms of `reduce`. Maybe these are out of date.

The wording looks somewhat out of date but there’s also the matter of what’s easier to read. Personally I’d prefer to see code using `sum` rather than `reduce(+, xs)`. Having said that, I do wonder whether a sufficiently nice syntax for reduction could let us delete some of the special purpose reduction verbs in the future. There was some interesting speculation about this at [Julep: Syntax for reduction (overloadable splatting?) · Issue #32860 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/32860) (read further than the initial proposal — there’s a range of options discussed there).

I think it’s interesting that we currently conflate binary operators like `vcat(a,b)`, with a lifted version of the binary operator `vcat_(xs...) = reduce(vcat, xs)`. This seems similar to the conflation of vectorized functions with their scalar versions prior to broadcast syntax being introduced. The introduction of broadcast syntax let us delete all the “broadcast-lifted” (ie, vectorized) methods. Similarly, having a reduction syntax would let us delete all the “reduction-lifted” methods.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [October 14, 2019, 6:19am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/36 "2019-10-14T06:19:04Z")

</div>

> [@c42f](#):
>
> Personally I’d prefer to see code using `sum` rather than `reduce(+, xs)` .

This is not just a matter of being easier to read. `reduce(+, xs)` must return the result of applying `+ ` repeatedly. The `sum` function on the other hand is free to have a different return type than that of `+`, reducing the risk of integer overflow.

```julia
julia> xs = Int8[100 27 1];

julia> sum(xs)
128

julia> reduce(+, xs)
-128

```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 14, 2019, 8:28am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/37 "2019-10-14T08:28:25Z")

</div>

On this topic, I think that a `flatmap` verb would still be useful:

1. Different typing of results
2. allows to map
3. verb that is obviously correct+optimized
4. directly maps from concept that people know from other languages

(3) is not just docs, it is the fact that it is non-apparent from the name. Hence, it would often be better to spell this like `reduce(vcat, stuff) #special cased in Base, faster than it looks`. Being correct is not enough, code should try to be _obviously_ correct (which is a much higher bar). That is a question of coding style, though.

---

<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:** [October 15, 2019, 1:05am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/38 "2019-10-15T01:05:06Z")

</div>

> [@c42f](#):
>
> I think it’s interesting that we currently conflate binary operators like `vcat(a,b)` , with a lifted version of the binary operator `vcat_(xs...) = reduce(vcat, xs)` . This seems similar to the conflation of vectorized functions with their scalar versions prior to broadcast syntax being introduced.

I’ve been thinking that this is natural, but maybe this is because of my positive experience in writing lisp where `(+)`, `(+ x)`, `(+ x y)`, `(+ x y z)`, … are all defined. But even without mentioning lisp, I think the unary `+ x` being an identity function in math already motivates that `+(args...)` should be `reduce(+, args)`.

---

<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:** [October 15, 2019, 1:36am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/39 "2019-10-15T01:36:32Z")

</div>

> [@Per](#):
>
> `reduce(+, xs)` must return the result of applying `+ ` repeatedly.

Would it be crazy to use `init = 0 :: Int` for `reduce(+, xs)` when `eltype(xs) <: Union{Int8,Int16,Int32}`? From how `reduce` is specified in the documentation, this is a valid definition AFAICT. Though maybe it was decided that it was too much of a magic, given that `sum` is implemented differently (i.e., using `add_sum` instead of `+`)?

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [October 15, 2019, 3:20am UTC](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672/40 "2019-10-15T03:20:00Z")

</div>

> [@tkf](#):
>
> I’ve been thinking that this is natural, but maybe this is because of my positive experience in writing lisp where `(+)` , `(+ x)` , `(+ x y)` , `(+ x y z)` , … are all defined. But even without mentioning lisp, I think the unary `+ x` being an identity function in math already motivates that `+(args...)` should be `reduce(+, args)` .

Yes, when I say I think it’s “interesting” I really mean it: I don’t know whether it’s good or bad overall 🙂 However I can think of two ways it leads to inconsistency:

1. The existence of a “reduction-lifted” method depends on whether the author of a given binary operator saw fit to include it. The user of the reduction can’t directly control that.
2. The “reduction-lifted” methods are inefficient when combined with splatting, so `vcat(xs...)` is very natural but nevertheless not recommended.

A reduction syntax could solve both these issues at once. Whether it’s worthwhile depends on whether it can really bring a lot of value. If it could be made to compose really nicely with broadcast that might be fairly compelling.

[Previous page](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672.md?page=1)

[Next page](https://discourse.julialang.org/t/very-best-way-to-concatenate-an-array-of-arrays/8672.md?page=3)