# Minimum of a column of a matrix

**URL:** <https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958>\
**Category:** New to Julia\
**Created:** [August 6, 2021, 6:28pm UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958 "2021-08-06T18:28:10Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![stephenll](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephenll/32/28751_2.png) [@stephenll](https://discourse.julialang.org/u/stephenll)\
**Post date:** [August 6, 2021, 6:28pm UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/1 "2021-08-06T18:28:10Z")

</div>

Is the following the best (minimize allocations and speed) way to get the minimum of the second column of a matrix?

```julia
minimum(@view x[:,2])

```

Seems reasonable but checking to see if I am missing something.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 6, 2021, 6:46pm UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/2 "2021-08-06T18:46:23Z")

</div>

Yeah. That’s good.

---

<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:** [August 7, 2021, 12:48am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/3 "2021-08-07T00:48:14Z")

</div>

```julia
using LoopVectorization, BenchmarkTools
function vminimum(x)
    acc = typemax(eltype(x))
    @turbo for i in eachindex(x)
        acc = min(acc, x[i])
    end
    acc
end
x = rand(128,3);
@btime minimum(@view $x[:,2])
@btime vreduce(min, @view $x[:,2])
@btime vminimum(@view $x[:,2])

```

I get:

```julia
julia> @btime minimum(@view $x[:,2])
  247.608 ns (0 allocations: 0 bytes)
0.010916262944919874

julia> @btime vreduce(min, @view $x[:,2])
  12.258 ns (0 allocations: 0 bytes)
0.010916262944919874

julia> @btime vminimum(@view $x[:,2])
  12.527 ns (0 allocations: 0 bytes)
0.010916262944919874

julia> versioninfo()
Julia Version 1.8.0-DEV.310
Commit cb30aa7a08* (2021-08-06 03:11 UTC)
Platform Info:
  OS: Linux (x86_64-redhat-linux)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, tigerlake)

```

`mimimum` has much lower compile time latency.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 7, 2021, 12:50am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/4 "2021-08-07T00:50:04Z")

</div>

Why is this faster than `minimum` is just Julia missing `@inbounds`?

---

<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:** [August 7, 2021, 12:50am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/5 "2021-08-07T00:50:24Z")

</div>

LLVM doesn’t know how to SIMD `min`.  
But it does help a lot:

```julia
julia> function minimum_simd(x)
           acc = typemax(eltype(x))
           @inbounds @simd for i in eachindex(x)
               acc = Base.FastMath.min_fast(acc, x[i])
           end
           acc
       end
minimum_simd (generic function with 1 method)

julia> @btime minimum_simd(@view $x[:,2])
  66.216 ns (0 allocations: 0 bytes)
0.010916262944919874

```

ASM:  
`vminimum`:

```nohighlight
L160:
        vminpd zmm7, zmm7, zmmword ptr [rax + 8*rdx - 448]
        vminpd zmm6, zmm6, zmmword ptr [rax + 8*rdx - 384]
        vminpd zmm4, zmm4, zmmword ptr [rax + 8*rdx - 320]
        vminpd zmm2, zmm2, zmmword ptr [rax + 8*rdx - 256]
        vminpd zmm5, zmm5, zmmword ptr [rax + 8*rdx - 192]
        vminpd zmm3, zmm3, zmmword ptr [rax + 8*rdx - 128]
        vminpd zmm1, zmm1, zmmword ptr [rax + 8*rdx - 64]
        vminpd zmm0, zmm0, zmmword ptr [rax + 8*rdx]
        add rdx, 64
        cmp rdi, rdx
        jne L160

```

`minimum_simd`, not actually simd or unrolled:

```nohighlight
L48:
        vminsd xmm0, xmm0, qword ptr [rcx + 8*rdx]
        inc rdx
        cmp rax, rdx
        jne L48

```

Thus relative performance gets worse for larger yet still pre-memory-bound arrays:

```julia
julia> x = rand(512,3);

julia> @btime minimum_simd(@view $x[:,2])
  395.990 ns (0 allocations: 0 bytes)
0.002170067911323348

julia> @btime vminimum(@view $x[:,2])
  23.335 ns (0 allocations: 0 bytes)
0.002170067911323348

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 7, 2021, 1:03am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/6 "2021-08-07T01:03:26Z")

</div>

We really should fix this. Does it require LLVM changes to fix?

---

<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:** [August 7, 2021, 1:19am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/7 "2021-08-07T01:19:02Z")

</div>

```julia
julia> minimum_simd(x)
remark: simdloop.jl:75:0: loop not vectorized: value that could not be identified as reduction is used outside the loop
remark: simdloop.jl:75:0: loop not vectorized
0.004311995252092693

```

I don’t know LLVM’s internals, but maybe there’s just a list of reductions somewhere, and `min` and `max` are missing an entry?  
[Godbolt](https://godbolt.org/z/7dr9jcboK), showing GCC can do it.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [August 7, 2021, 2:29am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/8 "2021-08-07T02:29:11Z")

</div>

Could there be a `VectorizedArray` that implements `@turbo` versions of Base functions?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 7, 2021, 2:55am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/9 "2021-08-07T02:55:50Z")

</div>

In this specific example, it seems like we could do it for regular old `Array`s once we fix an LLVM bug. That said, in general, this should be pretty easy to write.

---

<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:** [August 7, 2021, 3:21am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/10 "2021-08-07T03:21:41Z")

</div>

[StrideArrays.jl](https://github.com/chriselrod/StrideArrays.jl) is still a bit of a WIP, but it’s trying to do that:

```julia
julia> using StrideArrays

julia> x = StrideArray{Float64}(undef, (128, 3)); x .= rand.();

julia> xstatic = @StrideArray rand(128,3);

julia> xpartiallystatic = StrideArray{Float64}(undef, (StaticInt(128), 3)); xpartiallystatic .= rand.();

julia> y = rand(128,3);

julia> @btime minimum(@view $y[:,2])
  355.231 ns (0 allocations: 0 bytes)
0.017097150232982306

julia> @btime minimum(@view $x[:,2])
  16.872 ns (0 allocations: 0 bytes)
0.4937004891138578

julia> @btime minimum(@view $xstatic[:,2])
  11.496 ns (0 allocations: 0 bytes)
0.00474131798286026

julia> @btime minimum(@view $xpartiallystatic[:,2])
  18.281 ns (0 allocations: 0 bytes)
0.7472262476315941

```

---

<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:** [August 7, 2021, 3:30am UTC](https://discourse.julialang.org/t/minimum-of-a-column-of-a-matrix/65958/11 "2021-08-07T03:30:42Z")

</div>

> [@Oscar\_Smith](#):
>
> In this specific example, it seems like we could do it for regular old `Array` s once we fix an LLVM bug.

Still looking at LLVM src, but so far I [found this for AArch64](https://llvm.org/doxygen/AArch64TargetTransformInfo_8cpp_source.html#l01872):

```cpp
bool AArch64TTIImpl::isLegalToVectorizeReduction(
     const RecurrenceDescriptor &RdxDesc, ElementCount VF) const {
   if (!VF.isScalable())
     return true;
  
   Type *Ty = RdxDesc.getRecurrenceType();
   if (Ty->isBFloatTy() || !isElementTypeLegalForScalableVector(Ty))
     return false;
  
   switch (RdxDesc.getRecurrenceKind()) {
   case RecurKind::Add:
   case RecurKind::FAdd:
   case RecurKind::And:
   case RecurKind::Or:
   case RecurKind::Xor:
   case RecurKind::SMin:
   case RecurKind::SMax:
   case RecurKind::UMin:
   case RecurKind::UMax:
   case RecurKind::FMin:
   case RecurKind::FMax:
     return true;
   default:
     return false;
   }
 }

```

`FMin` and `FMax` are listed among legal reductions.  
It doesn’t vectorize on my M1.

```asm
L36:
        ldr d1, [x9], #8
        fcmp d0, d1
        fcsel d0, d0, d1, mi
        subs x8, x8, #1 ; =1
        b.ne L36

```

To actually track things down efficiently would probably require using something like gdb to try and step through what it’s doing?