# Builtin argmin is slower than manual

**URL:** <https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127>\
**Category:** Performance\
**Created:** [November 14, 2020, 2:27am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127 "2020-11-14T02:27:53Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![endremborza](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/endremborza/32/19312_2.png) [@endremborza](https://discourse.julialang.org/u/endremborza)\
**Post date:** [November 14, 2020, 2:27am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/1 "2020-11-14T02:27:53Z")

</div>

I don’t understand how this is possible. I tried it many times, targmin always wins, and by quite a significant margin (1.5.2)

```julia
using BenchmarkTools

function targmin(a)
    m = Inf
    ind = 0
    for i in 1:length(a)
        if a[i] < m
            m = a[i]
            ind = i
        end
    end
    ind
end

a = rand(10 ^ 8);

println(argmin(a) == targmin(a))

@btime argmin(a)
@btime targmin(a)

```

> true  
> 382.492 ms (1 allocation: 16 bytes)  
> 182.026 ms (1 allocation: 16 bytes)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 14, 2020, 8:10am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/2 "2020-11-14T08:10:11Z")

</div>

I can replicate this on `master`. It would be great to get to the bottom of this — ideally with a fix, but at least opening an issue.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 14, 2020, 9:19am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/3 "2020-11-14T09:19:41Z")

</div>

Note that your code assumes that `eltype(a)` is comparable to `Float64`, since `m` is `Inf` in the first iteration. That might not necessarily be the case. You’re also assuming 1-based indexing, `eachindex` would be better.

That said, I think the crux of the matter is that [`argmin` does `findmin`](https://github.com/JuliaLang/julia/blob/506fbdf81dcd771528da410369b9138624dff496/base/reducedim.jl#L1078), which itself calls `findminmax!` (seemingly very complex function)

Additionally, `argmin` allows for reduction across arbitrary dimensions, your `targmin` always reduces over the whole array.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2020, 9:21am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/4 "2020-11-14T09:21:27Z")

</div>

The core of `argmin` is:

[https://github.com/JuliaLang/julia/blob/ba06f439d187ff98530487508fd9844fce6a9e49/base/array.jl#L2205-L2226](https://github.com/JuliaLang/julia/blob/ba06f439d187ff98530487508fd9844fce6a9e49/base/array.jl#L2205-L2226)

It does some extra stuff to handle `NaN` etc and it is generic on the type of the array. But maybe it could be optimized as well (the code in question is quite old), for example, is both the `m != m` and `ai != ai` needed in every loop iteration?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 14, 2020, 9:25am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/5 "2020-11-14T09:25:18Z")

</div>

Oh wow, that code is ages old!

Those checks are needed to ensure the same behaviour as `min` and `max` for NaN, [I think](https://github.com/JuliaLang/julia/commit/6210e241f189e3d067a6b1c900360c3f38189a47).

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2020, 9:32am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/6 "2020-11-14T09:32:01Z")

</div>

> [@Sukera](#):
>
> Those checks are needed to ensure the same behaviour as `min` and `max` for NaN, [I think](https://github.com/JuliaLang/julia/commit/6210e241f189e3d067a6b1c900360c3f38189a47).

Yeah, I commented on the NaN handling but it does for exampe `m != m` over and over in the loop, even if `m` hasn’t changed.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 14, 2020, 9:35am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/7 "2020-11-14T09:35:01Z")

</div>

I wonder why the “change in iteration protocol” commit didn’t change to the new for loop as well and instead did it manually?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2020, 9:50am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/8 "2020-11-14T09:50:39Z")

</div>

Probably because you want to peel off the first value to use as the initial minimum.

How about:

```julia
findmax(a) = _findmax(a, :)

function _findmax(a, ::Colon)
    p = pairs(a)
    y = @inbounds iterate(p)
    if y === nothing
        throw(ArgumentError("collection must be non-empty"))
    end
    (mi, m), s = y
    isnan(m) && return m, mi
    i = mi
    while true
        y = @inbounds iterate(p, s)
        y === nothing && break
        (i, ai), s = y
        isnan(ai) && return ai, i
        # Neither `m` nor `ai` can be NaN here so can use `<` instead of `isless`.
        # Edit: not true, consider 0.0 < -0-0 == false
        if m < ai
            m, mi = ai, i
        end
    end
    return m, mi
end

```

does anyone see any problems with that?

Edit, the `isnan` should be changed back to `ai != ai` to handle missing…  
Edit Edit: actually, findmax is already broken with respect to `missing`

```julia
julia> findmax([missing, 1])
ERROR: TypeError: non-boolean (Missing) used in boolean context

```

Edit Edit Edit: My code fails to handle signed zero I think.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 14, 2020, 10:05am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/9 "2020-11-14T10:05:47Z")

</div>

You would not _need_ to bail out early at all, `isless` already treats `NaN` the way you want

```julia
          while true
               y = iterate(p, s)
               y === nothing && break
               (i, ai), s = y
               if isless(m, ai)
                   m = ai
                   mi = i
               end
           end

```

```julia
julia> findmax([1, NaN, 2])
(NaN, 2)

```

Not sure if you should have a branch just for finding `NaN`s faster at all.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2020, 10:09am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/10 "2020-11-14T10:09:41Z")

</div>

> [@mschauer](#):
>
> Not sure if you should have a branch just for finding `NaN` s faster at all.

But early exit is nice in case you have a NaN at the beginning, or?

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 14, 2020, 10:14am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/11 "2020-11-14T10:14:11Z")

</div>

There are many early exits you could imagine, e.g. `typemax(T)` where `T <: Union{Int32, Int64, Int128}` etc., the `NaN` early exit seems to be of less use. And here luckily

```julia
julia> isless(NaN, NaN)
false

```

so you actually find the first `NaN` as promised.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2020, 10:25am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/12 "2020-11-14T10:25:35Z")

</div>

Yeah, that’s true.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 14, 2020, 10:26am UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/13 "2020-11-14T10:26:14Z")

</div>

PS: This behaviour is also not very convincing to me:

```julia
julia> struct LargerThanNaN
       end

julia> Base.isless(_, ::LargerThanNaN) = true

julia> findmax([1, NaN, LargerThanNaN()])
(NaN, 2)

```

---

<div class="post-metadata">

**Author:** ![malacroi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/malacroi/32/19745_2.png) [@malacroi](https://discourse.julialang.org/u/malacroi)\
**Post date:** [November 14, 2020, 3:57pm UTC](https://discourse.julialang.org/t/builtin-argmin-is-slower-than-manual/50127/14 "2020-11-14T15:57:27Z")

</div>

IEEE specifies that `NaN` is supposed to propagate to indicate an error in an earlier computation. We’re not returning `NaN` because it’s the maximum (or minimum), but because it flags an illegal operation in a preceding computation.

Personally, since `m < NaN` is `false`, I would never want `NaN` as the result of `maximum` (or `minimum` for that matter), but that’s so 2008 of me. As of 2019, we should really be specifying whether we want `maximum` or `maximumNumber` to clarify our intent as to whether we want errors to propagate or be discarded.

How fun it is that Julia predates the latest floating point standard.