# Concatenating iterables without allocating memory

**URL:** <https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282>\
**Category:** Performance\
**Created:** [January 12, 2020, 11:50pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282 "2020-01-12T23:50:07Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 12, 2020, 11:50pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/1 "2020-01-12T23:50:07Z")

</div>

Hi, for a library I am working now I need to find minimum and maximum values. I am looking elegant way to express that.

```julia
signal1 = rand(10000000)
signal2 = rand(10000000)
@time lo, hi = extrema(vcat(signal1, signal2))
  0.159702 seconds (7 allocations: 152.588 MiB)

```

Code above looks good but allocates lots of memory just to iterate values, so it’s not making sense for me.

In C# I can write

```julia
(lo, hi) = signal1.Concat(signal2).Extrema();

```

and there is no allocation at all. It there any predefined method in Base that works in a similar way?

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 12, 2020, 11:54pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/2 "2020-01-12T23:54:51Z")

</div>

[`Iterators.flatten`](https://docs.julialang.org/en/v1/base/iterators/#Base.Iterators.flatten)

---

<div class="post-metadata">

**Author:** ![StevenSiew](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevensiew/32/218393_2.png) [@StevenSiew](https://discourse.julialang.org/u/StevenSiew)\
**Post date:** [January 12, 2020, 11:59pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/3 "2020-01-12T23:59:26Z")

</div>

```julia
julia> vec1 = rand(100);

julia> vec2 = rand(100);

julia> extrema1 = extrema(vec1)
(0.019555577401858537, 0.9995712478383711)

julia> extrema2 = extrema(vec2)
(0.016606741252352952, 0.9849117868980357)

julia> extrema_combined = extrema(vcat(collect(extrema1),collect(extrema2)))
(0.016606741252352952, 0.9995712478383711)

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 13, 2020, 12:01am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/4 "2020-01-13T00:01:26Z")

</div>

> [@StevenSiew](#):
>
> extrema\_combined = extrema(vcat(collect(extrema1),collect(extrema2)))

`collect` will allocate, and so will `vcat`.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 13, 2020, 12:01am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/5 "2020-01-13T00:01:51Z")

</div>

@ChrisRackauckas it still allocates memory

```julia
@time Iterators.flatten((signal1, signal2)) |> extrema
  0.285192 seconds (20.00 M allocations: 610.352 MiB, 24.17% gc time)

```

---

<div class="post-metadata">

**Author:** ![StevenSiew](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevensiew/32/218393_2.png) [@StevenSiew](https://discourse.julialang.org/u/StevenSiew)\
**Post date:** [January 13, 2020, 12:02am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/6 "2020-01-13T00:02:36Z")

</div>

```julia
julia> length(extrema1)
2

```

Yes it will allocate! I am losing sleep over the remaining of my 8 gigabytes of computer memory.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 13, 2020, 12:04am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/7 "2020-01-13T00:04:08Z")

</div>

@ChrisRackauckas, ok this works for me, I need to read implementations to understand what is going on

```julia
@time Iterators.flatten(zip(signal1, signal2)) |> extrema
  0.080821 seconds (8 allocations: 256 bytes)

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 13, 2020, 12:10am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/8 "2020-01-13T00:10:24Z")

</div>

Just because an example is length 2 doesn’t mean the real code is… it’s still a valid question to compose iterators without allocating intermediates…

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 13, 2020, 12:12am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/9 "2020-01-13T00:12:27Z")

</div>

I think @StevenSiew is right here, `extrema` always returns 2 elements no matter how long input is, and it does not allocate.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 13, 2020, 12:37am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/10 "2020-01-13T00:37:41Z")

</div>

I will stick to solution with `Iterators.flatten`, I wrote a helper method

```julia
function concatenate(iterables...)
    return zip(iterables...) |> Iterators.flatten
end

@time lo, hi = extrema(concatenate(signal1, signal2))
  0.072824 seconds (12 allocations: 352 bytes)
(4.430056321780285e-9, 0.9999998165880861)

```

I cannot reason why sometimes `flatten` allocates even more than the size of arrays is

```julia
@time Iterators.flatten((signal1, signal2)) |> extrema
  0.281161 seconds (20.00 M allocations: 610.352 MiB, 23.62% gc time)
(4.430056321780285e-9, 0.9999998165880861)

@time Iterators.flatten([signal1; signal2;]) |> extrema
  0.174777 seconds (8 allocations: 152.588 MiB, 11.98% gc time)
(4.430056321780285e-9, 0.9999998165880861)

@time Iterators.flatten(vcat(signal1, signal2)) |> extrema
  0.159507 seconds (8 allocations: 152.588 MiB)

@time Iterators.flatten(zip(signal1, signal2)) |> extrema
  0.073975 seconds (8 allocations: 256 bytes)
(4.430056321780285e-9, 0.9999998165880861)

```

It seems implementation is here, correct me if I am wrong:  
[https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/base/iterators.jl#L898](https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/base/iterators.jl#L898)  
I will try to figure it out tomorrow, it’s very late in my time zone.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 14, 2020, 1:01am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/11 "2020-01-14T01:01:22Z")

</div>

It looks like the problem is with extrema function. I put details in existing github issue. It describes different problem but they can be fixed together. I think I have draft of the solution, if no one will reply I will open pull request.

[https://github.com/JuliaLang/julia/issues/31442#issuecomment-573939429](https://github.com/JuliaLang/julia/issues/31442#issuecomment-573939429)

---

<div class="post-metadata">

**Author:** ![aramirezreyes](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aramirezreyes/32/42573_2.png) [@aramirezreyes](https://discourse.julialang.org/u/aramirezreyes)\
**Post date:** [January 14, 2020, 4:36am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/12 "2020-01-14T04:36:18Z")

</div>

Is `CatViews.jl` useful for your purposes?

> **[GitHub - ahwillia/CatViews.jl: Concatenated Array views in Julia.](https://github.com/ahwillia/CatViews.jl)**
>
> Concatenated Array views in Julia. Contribute to ahwillia/CatViews.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 14, 2020, 6:00am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/13 "2020-01-14T06:00:27Z")

</div>

Nope, it is slow and allocates memory like a crazy, but thanks, the API is nice.

```julia
ulia> @time CatView(signal1, signal2) |> minimum
 24.332661 seconds (320.16 M allocations: 14.611 GiB, 6.30% gc time)
2.4065947235030194e-8

julia> @time CatView(signal1, signal2) |> extrema
 25.199472 seconds (340.00 M allocations: 14.901 GiB, 6.13% gc time)
(2.4065947235030194e-8, 0.9999999501303669)

julia> @time Iterators.flatten((signal1, signal2)) |> extrema
  0.311673 seconds (20.00 M allocations: 610.352 MiB, 25.23% gc time)
(2.4065947235030194e-8, 0.9999999501303669)

```

---

<div class="post-metadata">

**Author:** ![aramirezreyes](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aramirezreyes/32/42573_2.png) [@aramirezreyes](https://discourse.julialang.org/u/aramirezreyes)\
**Post date:** [January 14, 2020, 6:17am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/14 "2020-01-14T06:17:32Z")

</div>

Wow, interesing! I thought that was what CatViews was for!

Argel Ramírez Reyes

---

<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:** [January 14, 2020, 6:51am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/15 "2020-01-14T06:51:02Z")

</div>

In addition to the problems with `extrema`, you shouldn’t use the `@time` macro for benchmarking, and especially avoid benchmarking with non-constant globals.

Use the BenchmarkTools package, and remember to interpolate the variables.

---

<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:** [January 14, 2020, 7:21am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/16 "2020-01-14T07:21:06Z")

</div>

Flatten is a typical example where performance is not great with the lazy iterator approach. Fortunately, we’ll have transducers in Julia 1.4. It means that we can write efficient “fused” extrema quite easily:

```julia
julia> using BenchmarkTools

julia> @btime extrema(Iterators.flatten(($signal1, $signal2)));
  258.958 ms (20000002 allocations: 610.35 MiB)

julia> @btime mapfoldl(
           x -> (x, x),
           ((a, b), (c, d)) -> (min(a, c), max(b, d)),
           Iterators.flatten(($signal1, $signal2)),
       );
  42.014 ms (0 allocations: 0 bytes)

```

* * *

OK, I lied. Above example actually does not work yet, until this bug fix is merged

[https://github.com/JuliaLang/julia/pull/34369](https://github.com/JuliaLang/julia/pull/34369)

Trying to comment here actually helped me find out this bug 🙂

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [January 14, 2020, 7:48am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/17 "2020-01-14T07:48:20Z")

</div>

This solution is not particularly nice but it is allocation free in released Julia 1.x versions:

```julia
julia> @btime extrema(Iterators.flatten(extrema.(($signal1, $signal2))));
  47.482 ms (0 allocations: 0 bytes)

```

---

<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:** [January 14, 2020, 7:59am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/18 "2020-01-14T07:59:12Z")

</div>

> [@tkf](#):
>
> ```julia
> julia> @btime mapfoldl( 
> x -> (x, x),
> ((a, b), (c, d)) -> (min(a, c), max(b, d)), 
> Iterators.flatten(($signal1, $signal2)), );
> 
> ```

Is this the syntax with transducers? I must admit I find it a bit hard to read.

---

<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:** [January 14, 2020, 8:12am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/19 "2020-01-14T08:12:36Z")

</div>

The ugly `mapfoldl` I wrote above is just a plain old `mapfoldl`. It should be executable in all Julia 1.x.

I should’ve clarified that transducers built in `Base` is just an implementation detail for executing `foldl` (see [Transducer as an optimization: map, filter and flatten by tkf · Pull Request #33526 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/33526)). Things like `sum(x for x in xs if x !== missing)` are processed through transducers “behind your back” so that it can be compiled to a better machine code. But there is no stable API for touching transducers in `Base`.

I think it’s better to use transducers in `reduce` as well so that you can just write `extrema(Iterators.flatten(...))` and it’s fast.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [January 14, 2020, 9:33am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/20 "2020-01-14T09:33:16Z")

</div>

@tkf, thank you so much, I am happy my example helped you to fix that 😃  
I am coming from C# and F# world, and I am really missing those pipelining features. When I first realised that in Julia `map(x->2x, someArray)` allocates and array for its result I was more than disappointed 🙂

[Next page](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282.md?page=2)