use Iterators.reverse for foldr etc.

[stevengj]

This is an alternate version of #25520 (and #24833) that avoids wrapping op in a Switch type. Rationale: avoids potential complications of overloading mapreduce_empty_iter and mapreduce_first discussed in https://github.com/JuliaLang/julia/pull/25520/files#r277144296, at a slight cost in code size.

Fixes #31780. Closes #25520. Fixes #24823.

Performance-wise it seems roughly identical to master in a simple benchmarks as I mentioned in #25520, though for some reason @btime is now reporting (1 allocation: 16 bytes) whereas there were zero allocations before (update: now fixed, see below).

[stevengj]

@nanosoldier runbenchmarks(ALL, vs = ":master")

[stevengj]

In particular, it looks like any reversed-order array iteration, e.g. foo(x) = foldl(-, Iterators.reverse(x)) or bar(x) = sum(Iterators.reverse(x)), gives 1 allocation: 16 bytes from @btime on master. Not sure why.

Correction: the problem seems exclusive to mapreduce with Iterators.Reverse. A manual loop seems fine, for example:

function baz(x) 
       c = 0
       for x in Iterators.reverse(x)
          c += 1
       end
       return c
end

gives zero allocations for x = rand(10). Maybe something is failing to inline?

[KristofferC]

It is probably allocating the Reverse wrapper itself to pass it to the non-inlined mapfoldl_impl:

julia> @code_warntype bar(x)
Body::Float64
1 ── %1  = %new(Base.Iterators.Reverse{Array{Float64,1}}, x)::Base.Iterators.Reverse{Array{Float64,1}}
...
│    %35 = invoke Base.mapfoldl_impl(%2::typeof(identity), %3::typeof(Base.add_sum), %34::NamedTuple{(:init,),Tuple{Float64}}, %1::Base.Iterators.Reverse{Array{Float64,1}}, %30::Tuple{StepRange{Int64,Int64},Int64})::Float64
└───       goto #11

[KristofferC]

The explicit @noinline was added in 705a187 but I am not sure what the exact reason was. I'll try remove it and see what happens.

[stevengj]

I can confirm that removing the @noinline removes the allocation. I'll add that to this PR.

Update: No, I take that back, removing @noinline removes the allocation from bar(x) = sum(Iterators.reverse(x)) but not from foo(x) = foldl(-, Iterators.reverse(x)) …

[KristofferC]

In foo(x) = foldl(-, Iterators.reverse(x)) the reverse wrapper gets allocated because it is used in mapreduce_empty_iter which will en up throwing an error in the empty iterator case:

julia> @code_warntype foo(rand(5))
Body::Float64
1 ── %1  = %new(Base.Iterators.Reverse{Array{Float64,1}}, x)::Base.Iterators.Reverse{Array{Float64,1}}
...
9 ── %35 = Base.mapreduce_empty_iter::typeof(Base.mapreduce_empty_iter)
│          invoke %35(%3::Function, %2::Function, %1::Base.Iterators.Reverse{Array{Float64,1}}, $(QuoteNode(Base.HasEltype()))::Base.HasEltype)
└───       $(Expr(:unreachable))

julia> foo(Float64[])
ERROR: ArgumentError: reducing over an empty collection is not allowed
Stacktrace:

Things probably don't get inlined because inference doesn't see a point in inlining things that are guaranteed to throw (except in this case it ruins the escape analysis). It reminds me of #29867.

[stevengj]

Thanks for the tip; that's now fixed for foldr.

[stevengj]

Added an allocation test.

[stevengj]

cc @timholy, not sure if you have any further thoughts about removing the @noinline annotation here.

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @ararslan

[stevengj]

nanosoldier regressions look like unrelated noise. (As far as I can tell, BaseBenchmarks.jl also doesn't call foldr directly, maybe not at all.)

[stevengj]

Okay to merge? @StefanKarpinski?