Perf improvement suggestion for simple extrema

While working on large arrays (images) searching for the fastest min/max and extrema I struggled to findout that recent fast minimum and maximum implementation use reduce. However extrema can be improved

julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Xeon(R) E-2186M  CPU @ 2.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 6

julia> x=rand(Float32,1000000);
julia> @btime extrema($x)
  2.187 ms (0 allocations: 0 bytes)
(5.9604645f-7, 0.9999994f0)
julia> function minmax(x)
       """
       Find min and max values in an Array, 3x faster than extrema
       """
               a = b = x[1]
               for i in 2:length(x)
                       if x[i] > b 
                               b = x[i]
                       elseif x[i] < a 
                               a = x[i]
                       end
               end
               a, b
       end
minmax (generic function with 1 method)
julia> @btime minmax($x)
  681.715 μs (0 allocations: 0 bytes)
(5.9604645f-7, 0.9999994f0)

Hope it can be of some use

1 Like
julia> methods(extrema)
# 8 methods for generic function "extrema":
[1] extrema(s::BitSet) in Base at bitset.jl:418
[2] extrema(r::AbstractRange) in Base at range.jl:579
[3] extrema(x::Real) in Base at operators.jl:486
[4] extrema(A::AbstractArray; dims) in Base at multidimensional.jl:1531
[5] extrema(itr) in Base at operators.jl:451
[6] extrema(f, x::Real) in Base at operators.jl:487
[7] extrema(f, A::AbstractArray; dims) in Base at multidimensional.jl:1542
[8] extrema(f, itr) in Base at operators.jl:468

there isnt any optimized implementation of extrema(x::AbstractArray), so its good to do. the only thing that makes me worried is how to manage not standard indices

1 Like

I don’t know if extrema ignores NaN values but the loop version here ignores. So, in reality, you may have one more check and branching.

It has been an open secret for some time that extrema is slow in a number of scenarios. See https://github.com/JuliaLang/julia/issues/31442

2 Likes

When extrema hits NaN it returns NaN of array eltype.
My simple function is easy to modify to skip NAN values by inserting
isnan(I[i]) && continue
as first test and not much impact on perf