Very best way to concatenate an array of arrays
FWIW the relevant concept to implement here is possibly flatmap. Then flatten(vv) = flatmap(x->x, vv)
My understanding is that with the PR above having been merged, this is now handled nicely in Base with reduce(vcat, ...).
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.
Tamas solution is the one implemented in Base intended to solve this exact problem
[ 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.
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.
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.
It does the right thing, no extra allocations. This should be both efficient and clear, a win-win.
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:
(Also, generally, it is not recommended to resurrect old topics unless there is a good reason.)
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.
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?
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
initmust be a neutral element foropthat will be returned for empty collections. It is unspecified whetherinitis 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.
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 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.
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> xs = Int8[100 27 1];
julia> sum(xs)
128
julia> reduce(+, xs)
-128
On this topic, I think that a flatmap verb would still be useful:
- Different typing of results
- allows to map
- verb that is obviously correct+optimized
- 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.
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).
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 +)?
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:
- 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.
- 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.
Got it. Yes, I’m very interested in this, too. How natural op(xs...) == reduce(op, xs) really is? If we implement optimization for op(...f.(xs)) (or another syntax), are people going to use it? Is it less “scary” and more intuitive than reduce?
Isn’t it enough to lower op(...f.(xs)) to reduce(op, broadcasted(f, xs)) so that broadcasting and reduction are fused? Can we do more than this?
Right: the reduction syntax acts as a barrier for broadcast and removes the call to materialize. I’m not sure anything else is required. We already discussed the dims keyword on the issue and it seemed clear that was an orthogonal problem.