Performance of first

[MasonProtter]

Things like first are currently quite slow with the current way Transducers.jl handles iteration of complex eductions. Here's an example from Zulip:

#+begin_src julia
using Transducers

function processxf(input)
    input |> Filter(isodd) |> Map(a -> a^2) |> Drop(100) |> first
end

@btime processxf(a^3 for a in Iterators.countfrom(1))
#+end_src

#+RESULTS:
   702.507 ns (109 allocations: 3.50 KiB)
 65944160601201

vs

#+begin_src julia
function process(input)
    output = Iterators.map(a -> a^2, Iterators.filter(isodd, input))
    Iterators.drop(output, 100) |> first
end

@btime process(a^3 for a in Iterators.countfrom(1))
#+end_src

#+RESULTS:
   120.779 ns (0 allocations: 0 bytes)
 65944160601201

One way around this is to use foldl(right, xs |> Take(1), init=0),

#+begin_src julia
function processxf2(input)
    firstx(xs) = foldxl(right, xs |> Take(1), init=0)
    input |> Filter(isodd) |> Map(a -> a^2) |> Drop(100) |> firstx
end

@btime processxf2(a^3 for a in Iterators.countfrom(1))
#+end_src

#+RESULTS:
   112.925 ns (0 allocations: 0 bytes)
 65944160601201

but still is still a little slower than the version with iterators, it won't error if the collection is empty, and it requires us to give the right type of init argument.

I think due to the Drop and Filter, we encounter some type instability if we try to use generic initial values:

#+begin_src julia
using InitialValues
function processxf3(input)
    firstx(xs) = foldxl(right, xs |> Take(1), init=InitialValue(right))
    input |> Filter(isodd) |> Map(a -> a^2) |> Drop(100) |> firstx
end

@btime processxf3(a^3 for a in Iterators.countfrom(1))
#+end_src

#+RESULTS:
:   4.441 μs (509 allocations: 14.23 KiB)
: 65944160601201