# Iterating over two vectors with vcat is faster than Iterators.flatten and CatViews?

**URL:** <https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698>\
**Category:** Performance\
**Tags:** memory-allocation\
**Created:** [September 30, 2018, 2:48pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698 "2018-09-30T14:48:41Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![control13](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/control13/32/5563_2.png) [@control13](https://discourse.julialang.org/u/control13)\
**Post date:** [September 30, 2018, 2:48pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/1 "2018-09-30T14:48:41Z")

</div>

Hey,

I have two independant vectors, which change in size over time, but sometimes I need to iterate over them both. I tried `vcat`, `Iterators.flatten` and CatViews and `vcat` needs the least amount of runtime and memory, quite the opposite of what I was expecting.

```julia
using BenchmarkTools, CatViews

function mysum(x)
    s = zero(eltype(x))
    for e in x
        s += e # only a dummy operation
    end
    s
end

a = rand(1_000);
b = rand(1_000);

@btime vcatvec = vcat(a, b);
  1.809 μs (1 allocation: 15.75 KiB)
@btime mysum(vcatvec)
  2.093 μs (1 allocation: 16 bytes)

@btime flatted = Base.Iterators.flatten((a, b));
  268.347 ns (2 allocations: 48 bytes)
@btime mysum(flatted)
  30.454 μs (4001 allocations: 125.02 KiB)

@btime catview = CatView(a, b);
  492.593 ns (7 allocations: 256 bytes)
@btime mysum(catview)
  911.768 μs (12989 allocations: 765.66 KiB)

```

I used Julia 1.0.0 and triggered the compilation bevor all measurments.  
Is there a faster way for iterating over two vectors?

---

<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 30, 2018, 4:34pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/2 "2018-09-30T16:34:18Z")

</div>

Make sure to interpolate the variables, always.

---

<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 30, 2018, 4:54pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/3 "2018-09-30T16:54:14Z")

</div>

> [@control13](#):
>
> @btime catview = CatView(a, b)

Apparently, adding `$` doesn’t help much here. It seems that `sum(CatViews(...))` at least is type unstable, not sure what’s causing it.

---

<div class="post-metadata">

**Author:** ![oxinabox](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oxinabox/32/206603_2.png) [@oxinabox](https://discourse.julialang.org/u/oxinabox)\
**Post date:** [October 1, 2018, 3:38am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/5 "2018-10-01T03:38:05Z")

</div>

> [@control13](#):
>
> I tried `vcat` , `Iterators.flatten` and CatViews and `vcat` needs the least amount of runtime and memory, quite the opposite of what I was expecting.

Yes,  
computers don’t work the way we like to think they do.

Cache-friendlyness and Branch-prediction friendlness matters an immense amount.  
when you do a `vcat` you pay the one off price for the coping of everything to contagious memory,  
but then you get to be doing an operation that the CPU is really well optimized for.  
(This is a hardware thing, not a julia thing)

For large enough arrays CatViews should overtake

---

<div class="post-metadata">

**Author:** ![Ajaychat3](https://avatars.discourse-cdn.com/v4/letter/a/ecd19e/32.png) [@Ajaychat3](https://discourse.julialang.org/u/Ajaychat3)\
**Post date:** [October 1, 2018, 6:20am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/6 "2018-10-01T06:20:30Z")

</div>

```julia
@btime vcatvec = vcat(a, b);
  1.809 μs (1 allocation: 15.75 KiB)
@btime mysum(vcatvec)
  2.093 μs (1 allocation: 16 bytes)

```

What about this?

```julia
julia> function broadcast_sum(x,y)
    output = zero(eltype(x)) 
    for i in eachindex(x) 
        output += x[i]+y[i]
    end
    output
end
broadcast_sum (generic function with 1 method)

julia> @btime broadcast_sum(a,b)
  1.007 μs (1 allocation: 16 bytes)
julia> @btime broadcast_sum(a,b)
  996.286 ns (1 allocation: 16 bytes)

```

Another version

```julia
 @btime sum(broadcast((x,y)->x+y,a,b))
  509.019 ns (2 allocations: 7.95 KiB)

```

---

<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:** [October 1, 2018, 6:29am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/7 "2018-10-01T06:29:14Z")

</div>

But it’s not just a bit slower, it’s couple of orders of magnitude, with lots of allocations.

I tried to write my own custom sum for `CatView`s:

```julia
a = rand(1_000);
b = rand(1_000);
v = CatView(a, b)
mysum(v::CatView) = sum(sum.(v.arr))

```

Then

```julia
julia> @btime mysum($v);
  915.714 ns (4 allocations: 80 bytes)

```

vs

```julia
julia> @btime sum($v);
  191.408 μs (6995 allocations: 109.78 KiB)

```

---

<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:** [October 1, 2018, 6:48am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/8 "2018-10-01T06:48:57Z")

</div>

And here’s a very barebones toy implementation of something similar (but of course less general):

```julia
struct MyCatView{N, T}
    arr::NTuple{N, Vector{T}}    
end
MyCatView(arrs::Vector{T}...) where {T} = MyCatView(arrs)
mysum(v::MyCatView) = sum(sum.(v.arr))

```

Then

```julia
julia> a, b = rand(1000), rand(1000);

julia> v = MyCatView(a, b);

julia> @btime mysum($v)
  192.796 ns (0 allocations: 0 bytes)

```

That’s three orders of magnitude faster(!) I think there must be something else going on.

---

<div class="post-metadata">

**Author:** ![laborg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laborg/32/5474_2.png) [@laborg](https://discourse.julialang.org/u/laborg)\
**Post date:** [October 1, 2018, 7:46am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/9 "2018-10-01T07:46:05Z")

</div>

I don’t understand a couple of implementation details in CatViews:

- How should `getindex` be fast at all? It’s doesn’t properly propagate bounds checking and a for-loop is called for each access. Using the tuple getindex accessor makes it faster, but its still type unstable.
- As already noticed it isn’t typestable - maybe this came with the 1.0 update, where a lot of type params declarations were removed.
- The perf.jl file doesn’t actually contain usable comparison benchmarks.
- What’s the purpose of the `inner` field in CatView? It’s never used?

I’d stay away from CatViews until it has proven that the original benefits are still valid in Julia 1.0.

Maybe @rdeits can chime in on performance problems with CatView, as he upgrade CatViews for Julia 1.0.

---

<div class="post-metadata">

**Author:** ![oxinabox](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oxinabox/32/206603_2.png) [@oxinabox](https://discourse.julialang.org/u/oxinabox)\
**Post date:** [October 1, 2018, 8:21am UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/10 "2018-10-01T08:21:38Z")

</div>

For anyone who isn’t aware,  
it is worth noting CatViews is quiet old.  
It was designed for Julia 0.3 IIRC.  
I think it’s type stability issues actually came from the 0.3-\>0.4 transition.  
(or maybe 0.4-\>0.5)

RecurisveArrayTools.jl is a good alternative, IIRC.  
But I’ve not benchmarked it on this.

> **[GitHub - SciML/RecursiveArrayTools.jl: Tools for easily handling objects like...](https://github.com/SciML/RecursiveArrayTools.jl)**
>
> Tools for easily handling objects like arrays of arrays and deeper nestings in scientific machine learning (SciML) and other applications - GitHub - SciML/RecursiveArrayTools.jl: Tools for easily h...

---

<div class="post-metadata">

**Author:** ![control13](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/control13/32/5563_2.png) [@control13](https://discourse.julialang.org/u/control13)\
**Post date:** [October 1, 2018, 2:04pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/11 "2018-10-01T14:04:01Z")

</div>

Thx to you all for the quick answers.  
@oxinabox RecurisveArrayTools.jl seems to be very promising. I tried this:

```julia
vofp = ArrayPartition(a, b)
@btime mysum(vofp)
  15.247 μs (2001 allocations: 31.27 KiB)
@btime sum(vofp)
  929.750 ns (7 allocations: 112 bytes)

```

In `mysum` I had to adjust this:

```julia
s = zero(eltype(eltype(x)))

```

They report “Broadcasting like `f.(A)` is efficient.” on their github page. I’ll try this later in my project.

---

<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 1, 2018, 4:07pm UTC](https://discourse.julialang.org/t/iterating-over-two-vectors-with-vcat-is-faster-than-iterators-flatten-and-catviews/15698/12 "2018-10-01T16:07:14Z")

</div>

Imo the really annoying thing is that the flattened iterator allocates during iteration, which makes `mysum(flattened)` so slow. Looking at `@code_warntype`, the bad object is of type `::Union{Nothing, Tuple{Float64,Tuple{Int64,Array{Float64,1},Int64}}}`.

In the case of flattening over a tuple of iterators or an array of iterators (anything that can be indexed with Int), there is no good reason for having an iterator-state that is not bitstype (it should be a tuple of integers, such that the next element is `iterate(flattened_iterators[i], j)`). So I’d say that this is either a problem of `Base.Iterators.flatten` or yet another manifestation of the problem with heap-allocating small immutable non-bitstypes.