Extrema, flattened iterator and too much memory alloation

[jakubwro]

Hi,

The issue I am reporting is related to discourse conversation: https://discourse.julialang.org/t/concatenating-iterables-without-allocating-memory/33282
Also I commented some details to other issue: #31442 (comment)

I encountered it using extrema function with flattened iterator, but here I am providing more distilled example.

First of all I need 2 big arrays which we are going to concatenate with a lazy iterator.

const signal1 = rand(10000000)
const signal2 = rand(10000000)
const flat = Iterators.flatten((signal1, signal2))

Now I am going to define a functions that will iterate this flattened data. They are based on extrema implementation.

function works_ok(itr)
    y = iterate(itr)
    (v, s) = y
    y = iterate(itr, s)
    while y !== nothing
        (v, s) = y
        y = iterate(itr, s)
    end

    return v
end

function gives_strange_result(itr)
    y = iterate(itr)
    (v, s) = y
    while y !== nothing
        y = iterate(itr, s)
        y === nothing && break
        (v, s) = y
    end

    return v
end

The second one has strange timings and memory consumption.

julia> @time works_ok(flat)
  0.024651 seconds (7 allocations: 240 bytes)
0.9342115147070622

julia> @time gives_strange_result(flat)
  0.252765 seconds (20.00 M allocations: 610.352 MiB, 22.57% gc time)
0.9342115147070622

There is no memory leak, I tried to run in a loop 1000 times.

[jakubwro]

julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.6.0)
  CPU: Intel(R) Core(TM) i7-4558U CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, haswell)

[KristofferC]

It seems that in the second case, the creation of the (v, s) tuple is not elided.

[jakubwro]

It seems that in the second case, the creation of the (v, s) tuple is not elided.

Please note that this happens just when used with flatten iterator, it's state is quite complicated nested tuple. For simple array it works ok:

julia> @btime gives_strange_result(signal1)
  3.030 ms (0 allocations: 0 bytes)
0.7037899384755859

julia> @btime works_ok(signal1)
  3.030 ms (0 allocations: 0 bytes)
0.7037899384755859

@KristofferC this tuple eliding is done when generating LLVM IR, right?

[tkf]

I think the issue itself would be solved by #36265.

(Though I'm not sure if this issue should be treated as a possible improvement for the compiler.)

[martinholters]

I can't reproduce. Fixed in the meantime?

[jakubwro]

I can't reproduce. Fixed in the meantime?

I can't reproduce too, it is fixed in 1.5. Thanks :)