# Performance of findmax vs. raw loop

**URL:** <https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305>\
**Category:** General Usage\
**Created:** [July 18, 2020, 7:19pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305 "2020-07-18T19:19:03Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 18, 2020, 7:19pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/1 "2020-07-18T19:19:03Z")

</div>

I’m curious if there is a high level concept to find maximum element and index in mapped array, which has similar performance to raw loop. I’m comparing `f4` and `f5`:

```julia
using BenchmarkTools, Random, StaticArrays, LinearAlgebra

points = rand(MersenneTwister(12345), SVector{2, Float32}, 10_000)

function f4(p)
  total = 0.
  det0 = det([p[1] p[end]])
  d0 = p[end] - p[1]

  (vmax, imax) = findmax(map(x -> abs(det([x d0]) + det0), p))
  total += vmax + p[imax][1] + p[imax][2]

  return total
end

function f5(p)
  total = 0.
  det0 = det([p[1] p[end]])
  d0 = p[end] - p[1]
  vmax = -Inf
  imax = 0

  for i in eachindex(p)
    if abs(det([p[i] d0]) + det0) > vmax
      vmax = abs(det([p[i] d0]) + det0)
      imax = i
    end
  end

  total += vmax + p[imax][1] + p[imax][2]

  return total
end

println(f4(points))
println(f5(points))

println("$VERSION f4: $(minimum(@benchmark f4($points)))")
println("$VERSION f5: $(minimum(@benchmark f5($points)))")

```

and raw loop in `f5` is much faster:

```julia
1.5.0-rc1.0 f4: TrialEstimate(27.355 μs)
1.5.0-rc1.0 f5: TrialEstimate(22.350 μs)

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [July 18, 2020, 7:24pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/2 "2020-07-18T19:24:35Z")

</div>

`f4` allocates an array.  
There should be (but doesn’t seem to be – I think it’s an open issue or PR) a version `findmax(f, v)`.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [July 18, 2020, 7:43pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/3 "2020-07-18T19:43:06Z")

</div>

[https://github.com/JuliaLang/julia/issues/27613](https://github.com/JuliaLang/julia/issues/27613)

EDIT:  
and [https://github.com/JuliaLang/julia/pull/35316](https://github.com/JuliaLang/julia/pull/35316)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 18, 2020, 7:56pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/4 "2020-07-18T19:56:08Z")

</div>

Performance of `findmax` aside, you are calculating

> [@pauljurczak](#):
>
> `abs(det([p[i] d0]) + det0)`

_twice_ per iteration in your loop, which seems unnecessary.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 18, 2020, 8:39pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/5 "2020-07-18T20:39:49Z")

</div>

That was intentional. This should be the easiest trick in compiler optimization book to handle, but reality is slightly different:

```julia
function f5(p)
  total = 0.
  det0 = det([p[1] p[end]])
  d0 = p[end] - p[1]
  vmax = -Inf
  imax = 0

  for i in eachindex(p)
    if abs(det([p[i] d0]) + det0) > vmax
      vmax = abs(det([p[i] d0]) + det0)
      imax = i
    end
  end

  total += vmax + p[imax][1] + p[imax][2]

  return total
end

function f6(p)
  total = 0.
  det0 = det([p[1] p[end]])
  d0 = p[end] - p[1]
  vmax = -Inf
  imax = 0

  for i in eachindex(p)
    v = abs(det([p[i] d0]) + det0)

    if v > vmax
      vmax = abs(det([p[i] d0]) + det0)
      imax = i
    end
  end

  total += vmax + p[imax][1] + p[imax][2]

  return total
end

```

Julia 1.5.0 does well:

```julia
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ ./julia -O3 --math-mode=fast ~/st/julia/bench7.jl
v"1.5.0-rc1.0" f5: 24.597 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f6: 24.611 μs 0 bytes 1.7352712154388428

```

Julia 1.4.2 not so much:

```julia
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ julia -O3 --math-mode=fast ~/st/julia/bench7.jl
v"1.4.2" f5: 22.356 μs 0 bytes 1.7352712154388428
v"1.4.2" f6: 29.043 μs 0 bytes 1.7352712154388428

```

although it optimizes `f5` better.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 18, 2020, 8:46pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/6 "2020-07-18T20:46:17Z")

</div>

> [@pauljurczak](#):
>
> That was intentional. This should be the easiest trick in compiler optimization book to handle

Oh, absolutely not. I would never expect the compiler to optimize that away when working with arrays.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 18, 2020, 9:20pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/7 "2020-07-18T21:20:59Z")

</div>

> [@DNF](#):
>
> I would never expect the compiler to optimize that away when working with arrays.

Why not? There is no side effects here, it should be easy to prove that these two copies of `abs(det([p[i] d0]) + det0)` have the same value. Modern C++ compilers are unlikely to fail to elide the second evaluation.

I took another look at measurements and with bounds checking disabled both Julia versions evaluate this expression only once:

```julia
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ ./julia -O3 --math-mode=fast --check-bounds=no ~/st/julia/bench7.jl
v"1.5.0-rc1.0" f5: 25.152 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f6: 25.154 μs 0 bytes 1.7352712154388428
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ julia -O3 --math-mode=fast --check-bounds=no ~/st/julia/bench7.jl
v"1.4.2" f5: 24.592 μs 0 bytes 1.7352712154388428
v"1.4.2" f6: 24.594 μs 0 bytes 1.7352712154388428

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 18, 2020, 9:22pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/8 "2020-07-18T21:22:27Z")

</div>

Some different process could mutate the array.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 18, 2020, 9:25pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/9 "2020-07-18T21:25:54Z")

</div>

Good point, but somehow the compiler didn’t take this possibility into account in my example. Is there an option to state that explicitly, e.g. from now on this container is read only?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 18, 2020, 9:47pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/10 "2020-07-18T21:47:39Z")

</div>

Not sure.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 18, 2020, 9:48pm UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/11 "2020-07-18T21:48:53Z")

</div>

It looks like Julia 1.5.0-rc1.0 has a performance regression on these tests. Not a lot on Intel Skylake (see above), but much worse on Intel Haswell:

```julia
v"1.4.2" f5: 22.148 μs 0 bytes 1.7352712154388428
v"1.4.2" f6: 22.144 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f5: 25.204 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f6: 25.199 μs 0 bytes 1.7352712154388428

```

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [July 19, 2020, 12:57am UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/12 "2020-07-19T00:57:58Z")

</div>

Note that starting Julia with `--math-mode=fast` is playing with fire:

```julia
> julia -O3 --math-mode=ieee -E "sinpi(0.15)"
0.45399049973954675
> julia -O3 --math-mode=fast -E "sinpi(0.15)"
0.0

```

From the definition of `f6`:

```julia
  for i in eachindex(p)
    v = abs(det([p[i] d0]) + det0)

    if v > vmax
      vmax = abs(det([p[i] d0]) + det0)
      imax = i
    end
  end

```

You didn’t actually reduce how often you’re calling `det`.

> [@pauljurczak](#):
>
> Good point, but somehow the compiler didn’t take this possibility into account in my example. Is there an option to state that explicitly, e.g. from now on this container is read only?

If you want to use `LLVM.jl`, you can. But it helps in situations like when you’re writing to one array and loading from another, it can tell the compiler that the write isn’t changing the load. That could allow it to reorder these reads and writes, and (for example) take advantage SIMD.

I would be very surprised if it helps in your example, however.  
The array allocations are not inlined:

```julia
julia> @code_native debuginfo=:none syntax=:intel Array{Float64}(undef, 3)
        .text
        push rax
        movabs rdi, offset jl_system_image_data
        movabs rax, offset jl_alloc_array_1d
        call rax
        pop rcx
        ret
        nop dword ptr [rax]

julia> @code_native debuginfo=:none syntax=:intel Array{Float64}(undef, 3, 4)
        .text
        push rax
        movabs rdi, offset jl_system_image_data
        movabs rax, offset jl_alloc_array_2d
        call rax
        pop rcx
        ret
        nop dword ptr [rax]

julia> @code_native debuginfo=:none syntax=:intel Array{Float64}(undef, 3, 4, 5)
        .text
        push rax
        movabs rdi, 139781825231120
        movabs rax, offset jl_alloc_array_3d
        call rax
        pop rcx
        ret
        nop dword ptr [rax]

```

So what is actually going on is opaque to the compiler.

This may change some day. [Keno said](https://discourse.julialang.org/t/why-is-julias-generated-assembly-more-complicated-than-swifts-for-a-simple-function/35549/13):

> [@Why is Julia's generated assembly more complicated than Swift's for a simple function?](https://discourse.julialang.org/t/why-is-julias-generated-assembly-more-complicated-than-swifts-for-a-simple-function/35549/13):
>
> Adding constant prop for arrays like this would be quite easy, but would have significant compile time cost, so we don’t do that. If you want to manually opt into that kind of thing you can use StaticArrays (or tuples as was previously mentioned). We are planning a bit of an Array overhaul for 2.0, at which point Array may be closer to StaticArrays and this kind of optimization may happen, but for now, `Array` is just the wrong data structure for what you’re looking for here.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [July 19, 2020, 1:23am UTC](https://discourse.julialang.org/t/performance-of-findmax-vs-raw-loop/43305/13 "2020-07-19T01:23:24Z")

</div>

> [@Elrod](#):
>
> Julia with `--math-mode=fast` is playing with fire

This is way off! I don’t think there is a similar problem with simple non accumulating +, -, \*, /.

> [@Elrod](#):
>
> You didn’t actually reduce how often you’re calling `det` .

It must have been one of the modern life distractions. The results are more convoluted now. Intel Skylake:

```julia
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ julia -O3 --math-mode=fast --check-bounds=no ~/st/julia/bench7.jl
v"1.4.2" f5: 25.152 μs 0 bytes 1.7352712154388428
v"1.4.2" f6: 22.888 μs 0 bytes 1.7352712154388428
paul@desktop:~/Apps/julia-1.5.0-rc1/bin$ ./julia -O3 --math-mode=fast --check-bounds=no ~/st/julia/bench7.jl
v"1.5.0-rc1.0" f5: 25.153 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f6: 25.168 μs 0 bytes 1.7352712154388428

```

Intel Haswell:

```julia
paul@extra:~/apps/julia-1.5.0-rc1/bin$ cset shield --exec julia -- -O3 --math-mode=fast --check-bounds=no bench7.jl
v"1.4.2" f5: 22.182 μs 0 bytes 1.7352712154388428
v"1.4.2" f6: 25.185 μs 0 bytes 1.7352712154388428
paul@extra:~/apps/julia-1.5.0-rc1/bin$ cset shield --exec ./julia -- -O3 --math-mode=fast --check-bounds=no bench7.jl
v"1.5.0-rc1.0" f5: 25.203 μs 0 bytes 1.7352712154388428
v"1.5.0-rc1.0" f6: 25.227 μs 0 bytes 1.7352712154388428

```

I can’t believe it got slower in some cases. Here is the new `f6`:

```julia
function f6(p)
  total = 0.
  det0 = det([p[1] p[end]])
  d0 = p[end] - p[1]
  vmax = -Inf
  imax = 0

  for i in eachindex(p)
    v = abs(det([p[i] d0]) + det0)

    if v > vmax
      vmax = v
      imax = i
    end
  end

  total += vmax + p[imax][1] + p[imax][2]

  return total
end

```