Potential performance improvements to Base minimum and maximum on arrays of integers

[brenhinkeller]

While trying to time some other things I recently noticed that a naive @inbounds for loop minimum function, e.g.

function f_minimum(A::Array{<:Integer})
    result = A[1]
    @inbounds for i=2:length(A)
        if A[i] < result
            result = A[i]
        end
    end
    return result
end

seems to significantly (up to a factor of five) outperform Base.minimum on arrays of integers:

julia> x = rand(Int, 10_000);
julia> using BenchmarkTools
julia> @btime minimum($x)
  5.440 μs (0 allocations: 0 bytes)
-9222934526579860823
julia> @btime f_minimum($x)
  1.578 μs (0 allocations: 0 bytes)
-9222934526579860823

This holds true over all the array sizes I tested, and for both Int s and UInt s from 8 to 64 bits.
Int64_minimum.pdf
UInt64_minimum.pdf

If the assumption I made about the array indices (to avoid redundantly comparing the first element to itself) is considered bad form even for plain Arrays, then you can still obtain a substantial performance improvement over Base with something more along the lines of

function f_minimum(A)
    result = first(A)
    for x in A
        if x < result
            result = x
        end
    end
    return result
end

Notably, it's much harder to beat Base for Floats, except for arrays of fewer than 1000 elements.

Float64_minimum.pdf

Thanks to @giordano @mcabbott @jakobnissen for discussion on Slack. If there's some consensus on the right way to proceed I'd be happy to try to make a PR, if the correct solution isn't too far out of my depth.

[brenhinkeller]

I should note that all times above are on Julia 1.5.0beta1
The relevant section of Base, as pointed out by @jakobnissen and @mcabbott :

julia/base/reduce.jl

Line 605 in 70d8497

function mapreduce_impl(f, op::Union{typeof(max), typeof(min)},

[brenhinkeller]

To copy over a bit more from the Slack thread before it's lost to the black hole, @mcabbott pointed out another implementation

function eachindex_minimum(A)
    result = typemax(eltype(A))
    @inbounds for i in eachindex(A)
        result = min(result, A[i])
    end
    return result
end

which turns out to be reproducibly a bit faster still,

as well as an interesting disparity between foldl and reduce which could perhaps be an issue of its own right:

julia> @btime reduce(min, $x)
  5.429 μs (0 allocations: 0 bytes)
-9221648205490468088

julia> @btime foldl(min, $x)
  1.528 μs (0 allocations: 0 bytes)
-9221648205490468088

[tkf]

The difference between reduce and foldl is expected because reduce(min, x) uses the same implementation as minimum(x).

[brenhinkeller]

Since foldl is described by ? as "Like reduce, but with guaranteed left associativity", does that mean there's performance being left on the table in the implementation of reduce?

[tkf]

I guess you can define (say) _mapreduce(::typeof(identity), ::Union{typeof(max), typeof(min)}, ::AbstractArray{<:Integer}) while using the same unrolling technique (but ignoring the NaN/missing checks).