How to build fast iterators? about resumablefunctions.jl

[Krastanov]

It seems that sometime in the last two years there was a significant regression to the benchmarks. What you describe is supposed to be fast (kinda the reason this library was created in the first place), but it was out of maintenance for a few years, so this might be due to a regression in the julia compiler or due to a minor modification in the library that was never tested for performance.

Similar issue is tracked here #72

I can not commit to fixing this in the near term, but do not hesitate to ask questions if you decide to give it a try.

[pepijndevos]

I'm trying this again on @gerlero's branch, and my conclusion so far seems to be that ResumableFunctions only really work reasonably in concrete typed functions.

Which is kind of a problem if you want to compose functions. You can't really write a function that takes an iterator and produces something with good performance.

using ResumableFunctions
using BenchmarkTools

bin(s, bins) = Iterators.map(((x, y),) -> (x, searchsortedfirst(bins, y)), s)

@resumable function any_hysteresis(s)
    bin = -1
    for (x, y) in s
        @yield if iseven(y)
            (x, (bin+1)÷2)
        else
            bin = y
            (x, (y+1)÷2)
        end
    end
end

@resumable function hysteresis(s::Vector{Tuple{Int,Int}})
    bin = -1
    for (x, y) in s
        @yield if iseven(y)
            (x, (bin+1)÷2)
        else
            bin = y
            (x, (y+1)÷2)
        end
    end
end

tolbins(bins, tol=1e-9) = collect(Iterators.flatmap((x -> (x-tol,x+tol)), bins))

hybin(s, bins, tol=1e-9) = bin(s, tolbins(bins, tol)) |> collect

s = collect(zip(1:1000, rand(1000)))

b = hybin(s, [0.5])

println("Any typed")
@btime for _ in any_hysteresis(b) end;
println("Struct types")
println(fieldtypes(typeof(any_hysteresis([(0,0)]))))
println("Vector typed")
@btime for _ in hysteresis(b) end;
println("Struct types")
println(fieldtypes(typeof(hysteresis([(0,0)]))))

Result:

Any typed
  202.546 μs (11470 allocations: 335.52 KiB)
Struct types
(UInt8, Any, Any, Any, Any, Any, Any)
Vector typed
  2.027 μs (1 allocation: 64 bytes)
Struct types
(UInt8, Int64, Vector{Tuple{Int64, Int64}}, Int64, Int64, Vector{Tuple{Int64, Int64}}, Int64)

[Krastanov]

I tried to simplify the examples you gave a bit. While not covering everything you mentioned, I think a good first step would be to try to make the following faster:

@resumable function one_to_n(n)
    for i in 1:n
        @yield i
    end
end

@resumable function one_to_n_typed(n::Int)
    for i in 1:n
        @yield i
    end
end

function append_one_to_n(n)
    l = typeof(n)[]
    for i in 1:n
        push!(l, i)
    end
    l
end

const n = 100
@btime collect(one_to_n($n)) evals=1;       # 4.258 μs (306 allocations: 11.36 KiB)
@btime collect(one_to_n_typed($n)) evals=1; # 390.000 ns (5 allocations: 1.97 KiB)
@btime append_one_to_n($n);                 # 334.060 ns (4 allocations: 1.92 KiB)
@btime collect(1:$n) evals=1;               # 30.000 ns (1 allocation: 896 bytes)

This issue is quite multifaceted. If we start working on it, probably we should split it in smaller pieces along the lines of the topics you have already enumerated (type annotations in the generated structs, the need for function annotation, specialization, reporting length and eltype when possible).

[pepijndevos]

There are two avenues I think could be useful. I found if you do `function foo(x::T) where T` that makes it to the struct, but not so for any of the locals that depend on T, so indeed one improvement would be to turn type annotations on locals into struct type parameters. How to annotate iterators is still an open problem in this case. A more radical solution that I've been told is a crime is to defer code_typed from get_slots to the constructor, a generated function that uses the argument types as called, rather than as declared to infer struct types.

…

On Wed, 6 Sep 2023, 22:43 Stefan Krastanov ***@***.***> wrote: I tried to simplify the examples you gave a bit. While not covering everything you mentioned, I think a good first step would be to try to make the following faster: @Resumable function one_to_n(n) for i in 1:n @yield i end end @Resumable function one_to_n_typed(n::Int) for i in 1:n @yield i end end function append_one_to_n(n) l = typeof(n)[] for i in 1:n push!(l, i) end l end const n = 100 @Btime collect(one_to_n($n)) evals=1; # 4.258 μs (306 allocations: 11.36 KiB) @Btime collect(one_to_n_typed($n)) evals=1; # 390.000 ns (5 allocations: 1.97 KiB) @Btime append_one_to_n($n); # 334.060 ns (4 allocations: 1.92 KiB) @Btime collect(1:$n) evals=1; # 30.000 ns (1 allocation: 896 bytes) This issue is quite multifaceted. If we start working on it, probably we should split it in smaller pieces along the lines of the topics you have already enumerated (type annotations in the generated structs, the need for function annotation, specialization, reporting length and eltype when possible). — Reply to this email directly, view it on GitHub <#67 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABJFINUOPLBKW36DO7LPXTXZDN7TANCNFSM6AAAAAAYOP7PII> . You are receiving this because you authored the thread.Message ID: ***@***.***>