Perf improvement suggestion for simple extrema

General Usage Performance
1

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
2 
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
3

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.

4

It has been an open secret for some time that extrema is slow in a number of scenarios. See Extrema is slower than maximum + minimum · Issue #31442 · JuliaLang/julia · GitHub

2 Likes
5

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