performance regression for `min_fast` and `Float16` on master

[matthias314]

Current master is almost 6x slower than before:

julia> v = rand(Float16, 2^10);
julia> @btime @fastmath foldl(min, $v)
  1.103 μs (0 allocations: 0 bytes)   # 1.9.0-beta4
  6.352 μs (0 allocations: 0 bytes)   # 1.10.0-DEV.680

max_fast is not affected, nor are Float32 and Float64.

Julia Version 1.10.0-DEV.680
Commit e2390597241 (2023-03-01 10:07 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i3-10110U CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 1 on 4 virtual cores

[christiangnrd]

I tested this on:

• M2 Max MacOS
• M1 MacOS
• Raspberry Pi 4 RPi OS
• Ryzen 3700X Linux
• Ryzen 3700X Windows
• i9-12900 Linux

And I am pretty sure this an x64 architecture-specific bug because I was able to reproduce the regression on AMD and Intel processors on both Linux and Windows. With the ARM processors on both MacOS and Linux, I saw a significant performance improvement anywhere from 3x (rpi) to 30x (M1 and M2).

[giordano]

With the ARM processors on both MacOS and Linux, I saw a significant performance improvement anywhere from 3x (rpi) to 30x (M1 and M2).

Between which versions? A speedup might be masked by #43327 on M1/M2 which have native Float16, but that doesn't apply to the Raspberry Pi, I think.

[gbaraldi]

Ok, this is a very odd failure. Look at the following non optimized IRs
On 1.9 we generate

    %5 = fcmp olt half %0, %1, !dbg !7
; └└
; ┌ @ essentials.jl:575 within `ifelse`
   %6 = zext i1 %5 to i8, !dbg !14
   %7 = trunc i8 %6 to i1, !dbg !14
   %8 = xor i1 %7, true, !dbg !14
   %9 = select i1 %8, half %1, half %0, !dbg !14
; └
  ret half %9, !dbg !13

But on master we generate

   %5 = fcmp fast olt half %0, %1, !dbg !7
; └└
; ┌ @ essentials.jl:586 within `ifelse`
   %6 = zext i1 %5 to i8, !dbg !12
   %7 = trunc i8 %6 to i1, !dbg !12
   %8 = xor i1 %7, true, !dbg !12
   %9 = select i1 %8, half %1, half %0, !dbg !12
; └
  ret half %9, !dbg !11

Note the fast on fcmp

After optimization we get
1.9

define half @julia_min_fast_597(half %0, half %1) #0 {
top:
; ┌ @ essentials.jl:575 within `ifelse`
   %2 = fpext half %0 to float
   %3 = fpext half %1 to float
   %4 = fcmp olt float %2, %3
   %5 = select i1 %4, half %0, half %1
; └
  ret half %5
}

master

define half @julia_min_fast_303(half %0, half %1) #0 {
top:
; ┌ @ essentials.jl:586 within `ifelse`
   %2 = call fast half @llvm.minnum.f16(half %0, half %1)
; └
  ret half %2
}

And it seems that the codegen for @llvm.minnum.f16 isn't as good as ours.

[gbaraldi]

Native code
1.9

   pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register %rbp
        movl    %esi, %eax
        movzwl  %di, %ecx
        vmovd   %ecx, %xmm0
        vcvtph2ps       %xmm0, %xmm0
        movzwl  %ax, %ecx
        vmovd   %ecx, %xmm1
        vcvtph2ps       %xmm1, %xmm1
        vucomiss        %xmm0, %xmm1
        cmoval  %edi, %eax
                                        # kill: def $ax killed $ax killed $eax
        popq    %rbp
        .cfi_def_cfa %rsp, 8
        retq

master

        push    rbp
        .cfi_def_cfa_offset 16
        .cfi_offset rbp, -16
        mov     rbp, rsp
        .cfi_def_cfa_register rbp
        movzx   eax, di
        vmovd   xmm0, eax
        vcvtph2ps       xmm0, xmm0
        movzx   eax, si
        vmovd   xmm1, eax
        vcvtph2ps       xmm1, xmm1
        vminss  xmm2, xmm1, xmm0
        vcmpunordss     xmm0, xmm0, xmm0
        vblendvps       xmm0, xmm2, xmm1, xmm0
        vcvtps2ph       xmm0, xmm0, 4
        vmovd   eax, xmm0
                                        # kill: def $ax killed $ax killed $eax
        pop     rbp
        .cfi_def_cfa rsp, 8
        ret

@oscardssmith

[christiangnrd]

Between which versions? A speedup might be masked by #43327 on M1/M2 which have native Float16, but that doesn't apply to the Raspberry Pi, I think.

I was comparing between 1.9.0-rc1 on all of them and 1.10.0-DEV.753 for some and DEV.759 for others.

[gbaraldi]

Just for reference, that optimization done above makes this code very much faster on Float32.

[christiangnrd]

3ff718650875b3783176d6bdc5e7b271ec573561 is the first bad commit
commit 3ff718650875b3783176d6bdc5e7b271ec573561
Author: Chris Elrod <elrodc@gmail.com>
Date:   Tue Dec 27 05:26:37 2022 -0500

    Define `gt_fast` and `ge_fast` (#47972)
    
    The important thing here is that `>` is used in `max_fast`, `min_fast`, and `minmax_fast`.
    These functions did not SIMD in reductions because `>` didn't have an associated fast op.
    This PR fixes that.

 base/fastmath.jl | 4 ++++
 1 file changed, 4 insertions(+)

[giordano]

CC @chriselrod

[chriselrod]

Just for reference, that optimization done above makes this code very much faster on Float32.

Yes, with 2^10 elements without the PR:

julia> @btime foldl(@fastmath(min), $v32)
  954.714 ns (0 allocations: 0 bytes)
0.0009765625f0

With the PR:

julia> @btime foldl(@fastmath(min), $v32)
  47.266 ns (0 allocations: 0 bytes)
0.00048828125f0

Bad codegen of @llvm.minnum.f16 sounds like an LLVM issue.
If you don't have hardware with native support, I suggest manually converting to Float32 and then truncating when done.

julia> @btime foldl(min, $v)
  1.314 μs (0 allocations: 0 bytes)
Float16(0.0004883)

julia> @btime foldl(@fastmath(min), $v)
  4.861 μs (0 allocations: 0 bytes)
Float16(0.0004883)

julia> @btime Float16(foldl(@fastmath(min), Iterators.map(Float32,$v)))
  69.507 ns (0 allocations: 0 bytes)
Float16(0.0004883)

This will yield much better performance on Julia master than you can get on 1.9.

I assume if you do have hardware support, LLVM's @llvm.minnum.f16 will actually do a good job.