提问者:小点点

浮点相等比较的SIMD指令(NaN==NaN)


哪条指令将用于比较由4 * 32位浮点值组成的两个128位向量?

是否有一条指令将两边的 NaN 值视为相等?如果不是,提供反身性(即 NaN 等于 NaN)的解决方法对性能的影响有多大?

我听说,与IEEE语义相比,确保自反性会对性能产生重大影响,在IEEE语义中,NaN不等于它本身,我想知道这种影响会有多大。

我知道在处理浮点值时,您通常希望使用epsilon比较而不是精确质量。但是这个问题是关于精确相等比较的,例如,您可以使用它来消除哈希集中的重复值。

三、要求

    0
  • -0 必须相等。
  • NaN 必须与自身相等。
  • NaN 的不同表示形式应该是相等的,但如果性能影响太大,则可能会牺牲该要求。
  • 结果应该是布尔值,如果所有四个浮点元素在两个向量中都相同,则为 true,如果至少有一个元素不同,则为 false。其中 true 由标量整数 1 表示,false 表示为 0

测试用例

(NaN, 0, 0, 0) == (NaN, 0, 0, 0) // for all representations of NaN
(-0,  0, 0, 0) == (+0,  0, 0, 0) // equal despite different bitwise representations
(1,   0, 0, 0) == (1,   0, 0, 0)
(0,   0, 0, 0) != (1,   0, 0, 0) // at least one different element => not equal 
(1,   0, 0, 0) != (0,   0, 0, 0)

我实现这个的想法

我认为可以使用组合两个NotLessThan比较(CMPNLPS?)以获得所需的结果。汇编程序等效于AllTrue(!(x

背景

这个问题的背景是微软计划在. NET中增加一个Vector类型,这里我讨论的是一个反身的< code >。Equals方法,并且需要更清楚地了解这个自反Equals对IEEE equals的性能影响有多大。参见应<代码>向量


共2个答案

匿名用户

即使是AVX VCMPPS(它大大增强了谓词的选择)也没有为此提供一个指令谓词。您必须至少进行两次比较并将结果合并。不过也不算太糟。

>

  • 不同的NaN编码并不相等:实际上是2个额外的insn(增加2个uops)。没有AVX:除此之外还有一个额外的movaps

    不同的NaN编码是相同的:实际上是4个额外的insns(加上4个UOP)。不带AVX:两个额外的< code>movaps insn

    IEEE比较和分支是3个uops:cmpeqps/movmskps/test和分支。Intel和AMD都将测试进行了宏融合,并将其分支为单个uop/m-op。

    对于AVX512:按位NaN可能只是一条额外的指令,因为正常向量比较和分支可能使用vcmpEQ_OQps/ktest相同,相同/jcc,所以组合两个不同的掩码寄存器是免费的(只需将参数更改为kest)。唯一的成本是额外的vpcmpeqd k2、xmm0、xmm1

    AVX512 any-NaN只是两个额外的指令(2x VFPCLASSPS,第二个使用第一个的结果作为零掩码。见下文)。同样,然后使用两个不同的参数进行ktest以设置标志。

    如果我们放弃考虑不同的NaN编码彼此相等:

    • 按位相等捕获两个相同的NaN
    • IEEE equal捕捉0==-0情况

    不存在任何比较给出假阳性的情况(因为当任何一个操作数为NaN时< code>ieee_equal为假:我们想要的只是相等,而不是相等或无序。AVX vcmpps提供了这两个选项,而SSE只提供了简单的相等操作。)

    我们想知道当所有元素都相等时,所以我们应该从倒置比较开始。检查至少一个非零元素比检查所有元素是否为非零更容易。(即水平 AND 很难,水平 OR 很容易(pmovmskb / testptest)。采取相反的比较意义是免费的(jnz 而不是 jz)。这与保罗·

    ; inputs in xmm0, xmm1
    movaps    xmm2, xmm0    ; unneeded with 3-operand AVX instructions
    
    cmpneqps  xmm2, xmm1    ; 0:A and B are ordered and equal.  -1:not ieee_equal.  predicate=NEQ_UQ in VEX encoding expanded notation
    pcmpeqd   xmm0, xmm1    ; -1:bitwise equal  0:otherwise
    
    ; xmm0   xmm2
    ;   0      0   -> equal   (ieee_equal only)
    ;   0     -1   -> unequal (neither)
    ;  -1      0   -> equal   (bitwise equal and ieee_equal)
    ;  -1     -1   -> equal   (bitwise equal only: only happens when both are NaN)
    
    andnps    xmm0, xmm2    ; NOT(xmm0) AND xmm2
    ; xmm0 elements are -1 where  (not bitwise equal) AND (not IEEE equal).
    ; xmm0 all-zero iff every element was bitwise or IEEE equal, or both
    movmskps  eax, xmm0
    test      eax, eax      ; it's too bad movmsk doesn't set EFLAGS according to the result
    jz no_differences
    

    对于双精度,。。。PSpcmpeqQ的工作原理相同。

    如果不相等代码继续找出哪个元素不相等,则对movmskps结果进行位扫描将为您提供第一个差异的位置。

    使用SSE4.1 PTEST,您可以将< code > and NPS /< code > movmskps /test-and-branch替换为:

    ptest    xmm0, xmm2   ; CF =  0 == (NOT(xmm0) AND xmm2).
    jc no_differences
    

    我希望这是大多数人第一次看到PTESTCF结果对任何事情都有用。:)

    它仍然是英特尔和AMD CPU上的三个uop((2ptest 1jcc)vs(Pandn movmsk fused-test

    这使得反身比较和分支总共有 6 个 uops(AVX 为 5 个),而 IEEE 比较和分支总共有 3 个 uops。(CMPEQPS / MOVMSKPS / test-and-branch.)

    PTEST 在 AMD 推土机系列 CPU 上具有非常高的延迟(Steamroller 上的 14c)。它们有一个由两个整数内核共享的矢量执行单元集群。(这是超线程的替代方法。这增加了检测到分支错误预测的时间,或者数据依赖链(cmovcc / setcc)的延迟。

    当< code>0==(xmm0和xmm2)时,PTEST设置< code>ZF:如果没有元素同时为< code>bitwise_equal和IEEE (neq或unordered),则设置该值。也就是说,如果任何元素是< code>bitwise_equal,同时也是< code >,则ZF是未设置的!ieee_equal。只有当一对元素包含按位相等的“非”时,才会发生这种情况(但当其他元素不相等时,也会发生这种情况)。

        movaps    xmm2, xmm0
        cmpneqps  xmm2, xmm1    ; 0:A and B are ordered and equal.
        pcmpeqd   xmm0, xmm1    ; -1:bitwise equal
    
        ptest    xmm0, xmm2
        jc   equal_reflexive   ; other cases
    
    ...
    
    equal_reflexive:
        setnz  dl               ; set if at least one both-nan element
    

    没有条件可以测试 CF=1 和关于 ZF 的任何内容。ja 测试 CF=0 和 ZF=1。无论如何,您不太可能只想对其进行测试,因此在 jc 分支目标中放置 jnz 可以正常工作。(如果您只想测试 AND equal_reflexive AND at_least_one_nan,则不同的设置可能会适当地设置标志)。

    这与Paul R的答案相同,但有一个错误修复(使用AND而不是OR将NaN检查与IEEE检查结合起来)

    ; inputs in xmm0, xmm1
    movaps      xmm2, xmm0
    cmpordps    xmm2, xmm2      ; find NaNs in A.  (0: NaN.  -1: anything else).  Same as cmpeqps since src and dest are the same.
    movaps      xmm3, xmm1
    cmpordps    xmm3, xmm3      ; find NaNs in B
    orps        xmm2, xmm3      ; 0:A and B are both NaN.  -1:anything else
    
    cmpneqps    xmm0, xmm1      ; 0:IEEE equal (and ordered).  -1:unequal or unordered
    ; xmm0 AND xmm2  is zero where elements are IEEE equal, or both NaN
    ; xmm0   xmm2 
    ;   0      0     -> equal   (ieee_equal and both NaN (impossible))
    ;   0     -1     -> equal   (ieee_equal)
    ;  -1      0     -> equal   (both NaN)
    ;  -1     -1     -> unequal (neither equality condition)
    
    ptest    xmm0, xmm2        ; ZF=  0 == (xmm0 AND xmm2).  Set if no differences in any element
    jz   equal_reflexive
    ; else at least one element was unequal
    
    ;     alternative to PTEST:  andps  xmm0, xmm2 / movmskps / test / jz
    

    所以在这种情况下,我们毕竟不需要PTESTCF结果。我们在使用PCMPEQD时会这样做,因为它没有逆(cmpunartps的方式有cmpordps)。

    9个用于英特尔SnB系列CPU的融合域uop。(7与AVX:使用非破坏性的3操作数指令来避免movap。)然而,Skylake SnB系列之前的CPU只能在p1上运行cmpps,因此如果吞吐量是一个问题,这个瓶颈会在FP-add单元上运行。Skylake在p0/p1上运行cmpps

    andps的编码比pand短,从Nehalem到Broadwell的Intel CPU只能在端口5上运行。这可能是为了防止它从周围的FP代码中窃取p0或p1周期。否则,pandn可能是更好的选择。在AMD BD系列上,无论如何,andnps都在ivec域中运行,因此您不会避免int和FP向量之间的旁路延迟(如果您使用movmskps而不是ptest(在这个版本中,仅使用cmpps,而不是pcmpeqd),则可能会管理此延迟)。还要注意,这里选择的指令顺序是为了便于阅读。将FP比较(A,B)放在更早的位置,在ANDPS之前,可能有助于CPU更快地开始该循环。

    如果重复使用一个操作数,则应该可以重复使用其自NaN查找结果。新操作数仍然需要自己的NaN检查,并与重用的操作数进行比较,因此我们只保存一个movaps/cmpps

    如果向量在内存中,则至少需要用单独的加载insn加载其中一个向量。另一个只能从内存中引用两次。如果它未对齐或寻址模式无法微型熔断,这很糟糕,但可能有用。如果vcmpps的一个操作数是已知没有任何NaN的向量(例如,零寄存器),vcmpunord_qps-xmm2、xmm15、[rsi]将在[rsi]中找到NaN。

    如果我们不想使用< code>PTEST,我们可以通过使用相反的比较,但是用相反的逻辑运算符(AND vs. OR)将它们组合起来,得到相同的结果。

    ; inputs in xmm0, xmm1
    movaps      xmm2, xmm0
    cmpunordps  xmm2, xmm2      ; find NaNs in A (-1:NaN  0:anything else)
    movaps      xmm3, xmm1
    cmpunordps  xmm3, xmm3      ; find NaNs in B
    andps       xmm2, xmm3      ; xmm2 = (-1:both NaN  0:anything else)
    ; now in the same boat as before: xmm2 is set for elements we want to consider equal, even though they're not IEEE equal
    
    cmpeqps     xmm0, xmm1      ; -1:ieee_equal  0:unordered or unequal
    ; xmm0   xmm2 
    ;  -1      0     -> equal   (ieee_equal)
    ;  -1     -1     -> equal   (ieee_equal and both NaN (impossible))
    ;   0      0     -> unequal (neither)
    ;   0     -1     -> equal   (both NaN)
    
    orps        xmm0, xmm2      ; 0: unequal.  -1:reflexive_equal
    movmskps    eax, xmm0
    test        eax, eax
    jnz  equal_reflexive
    

    真正比较的所有结果是NaN的编码。(试试看。也许我们可以避免使用PORPAND单独组合每个操作数上来自cmpps的结果?

    ; inputs in A:xmm0 B:xmm1
    movaps      xmm2, xmm0
    cmpordps    xmm2, xmm2      ; find NaNs in A.  (0: NaN.  -1: anything else).  Same as cmpeqps since src and dest are the same.
    ; cmpunordps wouldn't be useful: NaN stays NaN, while other values are zeroed.  (This could be useful if ORPS didn't exist)
    
    ; integer -1 (all-ones) is a NaN encoding, but all-zeros is 0.0
    cmpunordps  xmm2, xmm1
    ; A:NaN B:0   ->  0   unord 0   -> false
    ; A:0   B:NaN ->  NaN unord NaN -> true
    
    ; A:0   B:0   ->  NaN unord 0   -> true
    ; A:NaN B:NaN ->  0   unord NaN -> true
    
    ; Desired:   0 where A and B are both NaN.
    

    CMPORDPS XMM2,XMM1只是翻转每个案例的最终结果,“奇人出局”仍然在第1行。

    我们只能得到我们想要的结果(如果A和B都是NaN),如果两个输入都反转(NaN-

    我花了一段时间摸索手动操作。

    如果源元素是NaN,它可以修改目标元素,但这不能以关于目标元素的任何内容为条件。

    我希望我能想出一种方法来vcmpneqps,然后用每个源操作数修正一次结果(以消除合并3个vcmpps指令结果的布尔指令)。我现在很确定这是不可能的,因为知道一个操作数是NaN本身是不够的,所以不需要更改IEEE_equal(a,B)结果。

    我认为我们可以使用vfixupimmps的唯一方法是分别检测每个源操作数中的NaN,例如vcmpunord_qps,但更糟。或者作为和ps的一个非常愚蠢的替代品,检测之前比较的掩码结果中的0或所有1(NaN)。

    使用AVX512掩码寄存器可以帮助组合比较结果。大多数AVX512比较指令将结果放入掩码寄存器,而不是矢量寄存器中的掩码矢量,因此如果我们想在512b块中进行操作,我们实际上必须这样做。

    VFPCLASSPS k2 {k1}, xmm2, imm8 写入掩码寄存器,可选择由不同的掩码寄存器屏蔽。通过仅设置 imm8 的 QNaN 和 SNaN 位,我们可以得到向量中 NaN 位置的掩码。通过设置所有其他位,我们可以得到相反的结果。

    通过使用来自A的掩码作为B上的vfpclassps的零掩码,我们可以仅使用2条指令来找到两个NaN位置,而不是通常的cmp/cmp/combine。因此,我们保存一个和n指令。顺便说一下,我想知道为什么没有OR-NOT操作。可能它比AND-NOT出现的频率更低,或者他们只是不想在指令集中出现porn

    yasm和nasm都不能组装这个,所以我甚至不确定语法是否正确!

    ; I think this works
    
    ;  0x81 = CLASS_QNAN|CLASS_SNAN (first and last bits of the imm8)
    VFPCLASSPS    k1,     zmm0, 0x81 ; k1 = 1:NaN in A.   0:non-NaN
    VFPCLASSPS    k2{k1}, zmm1, 0x81 ; k2 = 1:NaNs in BOTH
    ;; where A doesn't have a NaN, k2 will be zero because of the zeromask
    ;; where B doesn't have a NaN, k2 will be zero because that's the FPCLASS result
    ;; so k2 is like the bitwise-equal result from pcmpeqd: it's an override for ieee_equal
    
    vcmpNEQ_UQps  k3, zmm0, zmm1
    ;; k3= 0 only where IEEE equal (because of cmpneqps normal operation)
    
    ;  k2   k3   ; same logic table as the pcmpeqd bitwise-NaN version
    ;  0    0    ->  equal   (ieee equal)
    ;  0    1    ->  unequal (neither)
    ;  1    0    ->  equal   (ieee equal and both-NaN (impossible))
    ;  1    1    ->  equal   (both NaN)
    
    ;  not(k2) AND k3 is true only when the element is unequal (bitwise and ieee)
    
    KTESTW        k2, k3    ; same as PTEST: set CF from 0 == (NOT(k2) AND k2)
    jc .reflexive_equal
    

    我们可以重复使用相同的掩码寄存器作为第二个 vfpclassps insn 的零掩码和目的地,但我使用了不同的寄存器,以防我想在注释中区分它们。此代码至少需要两个掩码寄存器,但没有额外的矢量寄存器。我们也可以使用 k0 而不是 k3 作为 vcmpps 的目的地,因为我们不需要将其用作谓词,只需用作 dest 和 src。(k0 是不能用作谓词的寄存器,因为该编码意味着“无屏蔽”。

    我不确定我们是否可以为每个元素创建一个结果为< code>reflexive_equal的单个掩码,而不使用< code>k...在某些时候组合两个掩码的指令(例如< code>kandnw而不是< code>ktestw)。掩码只能用作零掩码,而不能用作强制结果为1的一掩码,因此组合< code > VFP classs 结果只能用作AND。因此,我认为我们陷入了1-means-both-NaN,这是将它用作< code>vcmpps的零掩码的错误想法。首先执行< code>vcmpps,然后使用mask寄存器作为< code>vfpclassps的目标和谓词,也没有帮助。合并屏蔽代替零屏蔽可以实现这一目的,但写入屏蔽寄存器时不可用。

    ;;; Demonstrate that it's hard (probably impossible) to avoid using any k... instructions
    vcmpneq_uqps  k1,    zmm0, zmm1   ; 0:ieee equal   1:unequal or unordered
    
    vfpclassps    k2{k1}, zmm0, 0x81   ; 0:ieee equal or A is NaN.  1:unequal
    vfpclassps    k2{k2}, zmm1, 0x81   ; 0:ieee equal | A is NaN | B is NaN.  1:unequal
    ;; This is just a slow way to do vcmpneq_Oqps: ordered and unequal.
    
    vfpclassps    k3{k1}, zmm0, ~0x81  ; 0:ieee equal or A is not NaN.  1:unequal and A is NaN
    vfpclassps    k3{k3}, zmm1, ~0x81  ; 0:ieee equal | A is not NaN | B is not NaN.  1:unequal & A is NaN & B is NaN
    ;; nope, mixes the conditions the wrong way.
    ;; The bits that remain set don't have any information from vcmpneqps left: both-NaN is always ieee-unequal.
    

    如果 ktest 最终像 ptest 一样是 2 个 uops,并且不能宏融合,那么 kmov eax、k2 / test-and-branch 可能会比 ktest k1,k2 / jcc 便宜。希望它只是一个uop,因为掩码寄存器更像是整数寄存器,并且可以从一开始就设计为内部“接近”标志。ptest 仅在 SSE4.1 中添加,经过许多代设计,矢量和 EFLAG 之间没有交互。

    不过,KMOV确实为您设置了popcnt,BSF或BSR。(BSF/JCC 不进行宏融合,因此在搜索循环中,您可能仍然需要测试/JCC,并且仅在找到非零时才使用 BSF。编码 tzcnt 的额外字节不会给你买任何东西,除非你正在做一些无分支的事情,因为 bsf 仍然将 ZF 设置为零输入,即使目标寄存器未定义。不过,LZCNT 给出 32 - BSR,因此即使您知道输入不为零,它也很有用。

    我们也可以使用< code>vcmpEQps并以不同的方式组合我们的结果:

    VFPCLASSPS      k1,     zmm0, 0x81 ; k1 = set where there are NaNs in A
    VFPCLASSPS      k2{k1}, zmm1, 0x81 ; k2 = set where there are NaNs in BOTH
    ;; where A doesn't have a NaN, k2 will be zero because of the zeromask
    ;; where B doesn't have a NaN, k2 will be zero because that's the FPCLASS result
    vcmpEQ_OQps     k3, zmm0, zmm1
    ;; k3= 1 only where IEEE equal and ordered (cmpeqps normal operation)
    
    ;  k3   k2
    ;  1    0    ->  equal   (ieee equal)
    ;  1    1    ->  equal   (ieee equal and both-NaN (impossible))
    ;  0    0    ->  unequal (neither)
    ;  0    1    ->  equal   (both NaN)
    
    KORTESTW        k3, k2  ; CF = set iff k3|k2 is all-ones.
    jc .reflexive_equal
    

    例如,双精度元素的256b向量只有4个元素,但是kortestb仍然根据输入掩码寄存器的低8位设置CF。

    除了 NaN 之外,/-0 是 IEEE_equal 与 bitwise_equal 不同的唯一时间。(除非我错过了什么。使用前请仔细检查此假设! 0 和 -0 的所有位均为零,但 -0 设置了符号位(MSB)。

    如果我们忽略不同的NaN编码,那么bitwise_equal就是我们想要的结果,除了/- 0的情况。< code>A或B将为0,除了符号位当A和B为/- 0时。左移一位使其全零或非全零,这取决于我们是否需要覆盖按位相等测试。

    这比 cmpneqps 多使用一条指令,因为我们使用 por / paddD 模拟我们需要的功能。(或 pslld 一个,但这长了一个字节。它确实在与 pcmpeq 不同的端口上运行,但您需要考虑周围代码的端口分布,以将其考虑在决策中。

    此算法在不提供相同矢量 FP 测试来检测 NaN 的不同 SIMD 架构上可能很有用。

    ;inputs in xmm0:A  xmm1:B
    movaps    xmm2, xmm0
    pcmpeqd   xmm2, xmm1     ; xmm2=bitwise_equal.  (0:unequal -1:equal)
    
    por       xmm0, xmm1
    paddD     xmm0, xmm0     ; left-shift by 1 (one byte shorter than pslld xmm0, 1, and can run on more ports).
    
    ; xmm0=all-zero only in the +/- 0 case (where A and B are IEEE equal)
    
    ; xmm2     xmm0          desired result (0 means "no difference found")
    ;  -1       0        ->      0          ; bitwise equal and +/-0 equal
    ;  -1     non-zero   ->      0          ; just bitwise equal
    ;   0       0        ->      0          ; just +/-0 equal
    ;   0     non-zero   ->      non-zero   ; neither
    
    ptest     xmm2, xmm0         ; CF = ( (not(xmm2) AND xmm0) == 0)
    jc  reflexive_equal
    

    延迟比上面的cmpneqps版本低一到两个周期。

    我们在这里真正充分利用了<code>PTEST</code>:在两个不同的操作数之间使用其ANDN,并使用其与零的比较。我们不能用pandn/movmskps替换它,因为我们需要检查所有的位,而不仅仅是每个元素的符号位。

    我还没有实际测试过这一点,所以即使我的结论是 /-0 是唯一的时间IEEE_equal与bitwise_equal(NaN 除外)不同,也可能是错误的。

    用纯整数操作处理非位相同的NaN可能不值得。编码与 /-Inf如此相似,以至于我想不出任何不需要几个指令的简单检查。inf设置了所有的指数位,并且尾数为全零。NaN设置了所有的指数位,尾数为非零,又名有意义(因此有23位有效负载)。尾数的MSB被解释为is_quiet标志,以区分信令/安静的NaN。另请参见英特尔手册vo1,表4-3(浮点数和NaN编码)。

    如果不是-Inf使用前9位集编码,我们可以使用A的无符号比较来检查NaN

    OP的建议!(一个

    保罗·R将一个向量与其自身进行比较的解决方案确实让我们检测到哪里有nan,并“手动”处理它们。两个操作数之间的< code>VCMPPS结果组合是不够的,但使用除< code>A和< code>B之外的操作数会有所帮助。(要么是一个已知的非NaN向量,要么是同一个操作数两次)。

    如果没有反转,则按位NaN代码会查找何时至少有一个元素相等。(对于< code>pcmpeqd没有相反的情况,所以我们不能使用不同的逻辑运算符,并且仍然得到全等于的测试):

    ; inputs in xmm0, xmm1
    movaps   xmm2, xmm0
    cmpeqps  xmm2, xmm1    ; -1:ieee_equal.  EQ_OQ predicate in the expanded notation for VEX encoding
    pcmpeqd  xmm0, xmm1    ; -1:bitwise equal
    orps     xmm0, xmm2
    ; xmm0 = -1:(where an element is bitwise or ieee equal)   0:elsewhere
    
    movmskps eax, xmm0
    test     eax, eax
    jnz at_least_one_equal
    ; else  all different
    

    < code>PTEST这样没有用,因为与OR结合是唯一有用的东西。

    // UNFINISHED start of an idea
    bitdiff = _mm_xor_si128(A, B);
    signbitdiff = _mm_srai_epi32(bitdiff, 31);   // broadcast the diff in sign bit to the whole vector
    signbitdiff = _mm_srli_epi32(bitdiff, 1);    // zero the sign bit
    something = _mm_and_si128(bitdiff, signbitdiff);
    

  • 匿名用户

    这里有一个可能的解决方案-但效率不高,需要6条指令:

    __m128 v0, v1; // float vectors
    
    __m128 v0nan = _mm_cmpeq_ps(v0, v0);                   // test v0 for NaNs
    __m128 v1nan = _mm_cmpeq_ps(v1, v1);                   // test v1 for NaNs
    __m128 vnan = _mm_or_si128(v0nan, v1nan);              // combine
    __m128 vcmp = _mm_cmpneq_ps(v0, v1);                   // compare floats
    vcmp = _mm_and_si128(vcmp, vnan);                      // combine NaN test
    bool cmp = _mm_testz_si128(vcmp, vcmp);                // return true if all equal
    

    请注意,上面的所有逻辑都是颠倒的,这可能会使代码有点难以理解(< code >或实际上是< code >和,反之亦然)。