# 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:** 15\
**Page:** 2

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [January 14, 2020, 10:23am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/21 "2020-01-14T10:23:25Z")

</div>

Perhaps it is easiest to not try to be too smart and just do

```julia
(min1, max1), (min2, max2) = extrema(signal1), extrema(signal2)
return min(min1, min2), max(max1, max2)

```

---

<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, 11:00am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/22 "2020-01-14T11:00:50Z")

</div>

@mschauer, this approach was already suggested two times in previous posts.  
I don’t think it is being “too smart”. In every modern language (C# with LINQ, Java with Streams) I am allowed to do such lazy concatenation of arrays without performance penalties. I think there is a bug or a design flaw that needs to be addressed.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [January 14, 2020, 11:11am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/23 "2020-01-14T11:11:05Z")

</div>

I think this is because you are going “against the grain” of the memory layout here. Compare what you are trying with the “generic” but very natural version using an `unzip` \*)

```julia
mins, maxs = unzip(extrema.(signals))
minimum(mins), maximum(maxs)

```

It is to me more natural to compute the extremas first of each series and combine the results than to combine the series and compute the extremas. That also respects the locality of the memory better.

\*) something is indeed missing

---

<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, 11:18am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/24 "2020-01-14T11:18:27Z")

</div>

It doesn’t seem so unnatural to me to want to treat two (or more!) series as one, and do some operation on it. For example, it could be that they are semantically one series that just happened to be split up for size reasons.

Perhaps the operation even depends on boundary effects which makes it hard to apply the operation on the parts separately.

---

<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, 12:02pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/25 "2020-01-14T12:02:17Z")

</div>

@mschauer I really like your approach.

But please consider those 2 examples:

```julia
const signal1 = rand(10000000)
const signal2 = rand(10000000)

```

```julia
julia> @btime Iterators.flatten(($signal1, $signal2)) |> extrema
  283.061 ms (20000002 allocations: 610.35 MiB)
(6.728651613663317e-8, 0.9999999625593397)

julia> @btime Iterators.flatten(zip($signal1, $signal2)) |> extrema
  68.612 ms (3 allocations: 64 bytes)
(6.728651613663317e-8, 0.9999999625593397)

```

In the first one I am going exactly with the memory layout and allocation is high, performance is poor. In the second one I am going “against the grain”, interleaving data from both arrays. For some reason that I don’t understand this “against the grain” version is faster and optimal.

Also when I define my own function

```julia
function my_extrema(itr)
    begin
        vmin = vmax = first(itr)
        for item in itr
            vmax = max(item, vmax)
            vmin = min(item, vmin)
        end
    end

    return (vmin, vmax)
end

```

Performance as is good as I would expect for original `extrema` from Julia base library.

```julia
julia> @btime Iterators.flatten(($signal1, $signal2)) |> my_extrema
  68.700 ms (2 allocations: 48 bytes)
(6.728651613663317e-8, 0.9999999625593397)

```

If someone is able to explain it to me I would be thankful. I am going to investigate it anyway but I have no time this right now.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [January 14, 2020, 1:13pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/26 "2020-01-14T13:13:02Z")

</div>

Good that you insist. I also agree with you that something is not right when computing `extrema` of a flattened iterator. It only has nothing to do with flatten (as you also said). Something is not right about how `extrema` works…

---

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [January 14, 2020, 1:47pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/27 "2020-01-14T13:47:22Z")

</div>

Just because I’m currently working with it, here’s `OnlineStats`’ performance:

```julia
julia> o = Extrema()
Extrema: n=0 | value=(Inf, -Inf)

julia> @btime foreach(x -> fit!(o, x), ($signal1, $signal2))
  51.465 ms (0 allocations: 0 bytes)

julia> value(o)
(4.8156351573069855e-8, 0.9999999801147899)

```

For comparison, here’s what flatten results in on my machine:

```julia
julia> @btime Iterators.flatten(zip($signal1, $signal2)) |> extrema

  43.234 ms (3 allocations: 64 bytes)
(4.8156351573069855e-8, 0.9999999801147899)

```

So `OnlineStats` needs zero allocations but takes 20% longer…

---

<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, 2:50pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/28 "2020-01-14T14:50:01Z")

</div>

@yakir12 , thanks for another solution. I am not concerned about those tens or hundreds bytes. Hundreds of megabytes and gigabytes from above examples are painful for me.  
Probably your example is slightly slower, cause access to variables can be optimised better than fields of mutable struct. 20% slower is fine for me, 400% slower not.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [January 14, 2020, 3:13pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/29 "2020-01-14T15:13:07Z")

</div>

> [@Jakub\_Wronowski](#):
>
> Hundreds of megabytes and gigabytes from above examples are painful for me.

Out of curiosity, are you running on a system where you are not allowed to allocate (e.g. a GPU)? If not, why do you care about the total number of allocations and not just the time it takes to run the operation?

---

<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, 3:45pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/30 "2020-01-14T15:45:17Z")

</div>

@kristoffer.carlsson I am starting a quantitative finance project and I am exploring possibility to use Julia as a backend for numeric calculations. I am not planning to use GPU, just CPU. You’re right, I care about total time of calculation only, but I can see that there is a correlation between time of execution and amount of allocations. Also operation that clearly should not allocate at all allocates a lot (610 MiB for 150 MiB of data processed) in some rare circumstances (`Base.extrema`) and works as expected for other cases (`Base.sum`, `Base.minimum`, `my_extrema`).  
I am willing to investigate it when I find some time for debugging and reading generated lowered and native code but I am also hoping that this is a known issue that someone already works on.

---

<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, 11:56pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/31 "2020-01-14T23:56:27Z")

</div>

I agree that it would be great if `map`, `filter`, etc. are lazy. But I think that core devs had to balance compilation time, execution time, and usability. I imagine non-lazy `map` was an OK solution for this especially in early days of Julia compiler.

> [@Jakub\_Wronowski](#):
>
> In every modern language (C# with LINQ, Java with Streams) I am allowed to do such lazy concatenation of arrays without performance penalties.

Unlike many languages (except Clojure and what else?), Julia has builtin transducers. I think it’s cool that you can do:

```julia
julia> function demo()
           a = (1, 2, 3)
           b = SVector(4, 5, 6)
           return sum(x for xs in (a, b) for x in xs)
           # another way to write Iterators.flatten
       end
demo (generic function with 1 method)

julia> @code_llvm demo()

; @ REPL[80]:2 within `demo'
define i64 @julia_demo_19412() {
L29.1:
; @ REPL[80]:4 within `demo'
  ret i64 21
}

```

I tried to explain why doing flatten using transducers works so well in my talk in the last JuliaCon ([YouTube](https://www.youtube.com/watch?v=wxN4lKR3kFw)). See, e.g., [this slide](https://tkf.github.io/juliacon2019-transducers/#43).

If you care the performance of lazy iterators, I think Julia is one the best languages. Well, at least as long as you use `foldl` and `reduce` everywhere.

---

<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 15, 2020, 12:35pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/32 "2020-01-15T12:35:04Z")

</div>

@tkf, thanks for links, I saw your recent PRs and I think the work you did is outstanding.

> [@tkf](#):
>
> Unlike many languages (except Clojure and what else?), Julia has builtin transducers. I think it’s cool that you can do:

I think I did such things 10 years ago in F#, and can easily do stuff like this also in C#. I prepared even performance comparison with C#.

```csharp
csharp> var a = new [] {1, 2, 3};
csharp> var b = new [] {4, 5, 6};
csharp> Time(() => new [] {a,b}.SelectMany(x => x).Sum());
00:00:00.0002290

```

```julia
julia> const a = [1,2,3];
julia> const b = [4,5,6];
julia> @btime sum(x for xs in ($a, $b) for x in xs)
  54.606 ns (8 allocations: 192 bytes)
21

```

225 ns vs 54 ns

```julia
csharp> var a = new [] {1, 2, 3};
csharp> var b = Enumerable.Repeat(1, 10000000);
csharp> Time(() => new [] {a,b}.SelectMany(x => x).Sum());
00:00:00.1963760

```

```julia
julia> const a = [1,2,3];
julia> const b = [1 for i in 1:10000000];
julia> @btime sum(x for xs in ($a, $b) for x in xs)
  8.107 ms (8 allocations: 192 bytes)
10000006

```

196 ms vs 8 ms

```csharp
csharp> Time(() => new [] {a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b}.SelectMany(x => x).Sum());
00:00:01.8202740

```

```julia
julia> @btime sum(x for xs in (a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b) for x in xs)
  86.810 ms (44 allocations: 1.17 KiB)
100000060

```

1820 ms vs 86 ms

I used interactive C# session, one can say that compiled would be faster. I [checked that](https://gist.github.com/jakubwro/1a1fe06ff028bb87065e90f33e8abbfc) with all optimisations enabled it’s 1200 ms (on mac, win could do better, but no more that twice). What I really wanted to prove, that you are wrong, but I failed. Julia seems to be superior in this field, no doubt.

Anyway I still think this behaviour of flatten iterator with `extrema` seems to be a bug and I opened an issue with more details: [Extrema, flattened iterator and too much memory alloation · Issue #34385 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/34385)

---

<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 15, 2020, 8:59pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/33 "2020-01-15T20:59:52Z")

</div>

> [@Jakub\_Wronowski](#):
>
> ```julia
> julia> @btime sum(x for xs in ($a, $b) for x in xs)
> 54.606 ns (8 allocations: 192 bytes)
> 
> ```

As I said in my first comment, reduce with `Iterators.flatten` was slow in Julia \< 1.4 which did not have transducers. Maybe you are checking this only in a released version of Julia. See:

In 1.5.0-DEV.67:

```julia
julia> @btime sum(x for xs in ($a, $b) for x in xs)
  5.718 ns (0 allocations: 0 bytes)

```

In 1.3.1:

```julia
julia> @btime sum(x for xs in ($a, $b) for x in xs)
  40.254 ns (8 allocations: 192 bytes)

```

---

<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 15, 2020, 9:51pm UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/34 "2020-01-15T21:51:51Z")

</div>

Right, I used 1.3.1, on 1.5 for the last one I have:

```julia
  43.255 ms (1 allocation: 16 bytes)
100000060

```

It’s more that 25x faster than C#. I wouldn’t believe if someone told me that. I wonder if more complicated iterators like linked lists or trees will be that much faster too.

---

<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 16, 2020, 4:06am UTC](https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282/35 "2020-01-16T04:06:57Z")

</div>

> [@Jakub\_Wronowski](#):
>
> linked lists or trees

My guess is that there won’t be much improvement for the usual linked lists or trees as iteration over such structures probably is dominated by chasing the pointers. But, I think transducers would be a great framework for iterating over “hybrid” data structures like B-trees.

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