assembly - SIMD指令用于浮点相等比较(NaN == NaN)

Question

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

是否有一条指令将两侧的NaN值视为相等？如果不是，提供反射性（即，NaN等于NaN）的变通方法对性能的影响有多大？

我听说，与NaN不等同于IEEE语义的IEEE语义相比，确保反射性会对性能产生重大影响，我想知道这种影响是否会很大。

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

要求


+0和-0必须相等。
NaN必须与自身进行比较。
NaN的不同表示形式应该相等，但是如果对性能的影响太大，则可能会牺牲该要求。
如果两个向量中的所有四个float元素都相同，则结果应为布尔值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组合两个 CMPNLTPS比较（ and？）以达到所需的结果。等效于 AllTrue(!(x < y) and !(y < x))或 AllFalse((x < y) or (y > x)的汇编器。

背景

这个问题的背景是Microsoft计划将Vector类型添加到.NET。我在为自反 .Equals方法争论的地方，需要更清晰地了解此自反等式对IEEE均衡器的性能影响有多大。有关详细信息，请参见programmers.se上的 Should Vector<float>.Equals be reflexive or should it follow IEEE 754 semantics?。

Answer 1

甚至AVX VCMPPS（具有大大增强的谓词选择）也无法为我们提供单指令谓词。您必须至少进行两次比较并合并结果。不过还算不错。


不同的NaN编码不相等：实际上是2个额外的insn（增加了2个uops）。没有AVX：超出此范围后再增加一个movaps。
不同的NaN编码是相等的：实际上有4个额外的insn（加了4个uops）。没有AVX：两个额外的movaps insn


IEEE比较和分支为3微秒：cmpeqps / movmskps /测试和分支。 Intel和AMD都将测试分支与宏融合到单个uop / m-op中。

使用AVX512：逐位NaN可能只是一条额外的指令，因为正常的向量比较和分支可能使用vcmpEQ_OQps / ktest same,same / jcc，因此组合两个不同的掩码reg是免费的（只需将args更改为ktest ）。唯一的成本是额外的vpcmpeqd k2, xmm0,xmm1。

AVX512 any-NaN只是两个额外的指令（2x VFPCLASSPS，第二个指令使用第一个指令的结果作为零掩码。请参见下文）。同样，然后ktest用两个不同的args设置标志。



到目前为止，我最好的主意：ieee_equal || bitwise_equal

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


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


在任何情况下都不存在比较结果为假的情况（因为当任一操作数为NaN时ieee_equal为false：我们希望相等，而不是相等或无序。AVXvcmpps提供两种选择，而SSE仅提供普通选择均等操作。）

我们想知道何时所有元素都相等，因此我们应该从反向比较开始。检查至少一个非零元素比检查所有非零元素要容易。 （即，水平与比较难，水平或比较容易（pmovmskb / test或ptest）。相反的比较是免费的（jnz代替jz）。）保罗R使用的相同技巧。

; 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

对于双精度， ...PS和 pcmpeqQ将相同。

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

使用SSE4.1 PTEST，您可以将 andnps / movmskps / test-and-branch替换为：

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

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

在Intel和AMD CPU上，仍然只有3个微秒（（2ptest + 1jcc）与（pandn + movmsk +融合测试和分支）），但是指令更少。如果要使用 setcc或 cmovcc而不是 jcc，则效率会更高，因为这些宏无法与 test进行宏融合。

自反式比较分支的总计为6 oups（AVX为5），而IEEE比较分支的总计为3 uops。 （ cmpeqps / movmskps /测试和分支。）

PTEST在AMD Bulldozer系列CPU（ 14c on Steamroller）上具有很高的延迟。它们具有两个整数内核共享的一组矢量执行单元。 （这是超线程的替代方法。）这增加了直到可以检测到分支错误预测或数据依赖链的延迟（ cmovcc / setcc）的时间。

PTEST在 ZF时设置 0==(xmm0 AND xmm2)：如果两个元素都不都是 bitwise_equal和IEEE（neq或无序），则设置。即，如果任何元素为 bitwise_equal且同时为 !ieee_equal，则未设置ZF。这仅在一对元素包含按位等于 NaN时才会发生（但在其他元素不相等时可能发生）。

    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 and ZF=1。无论如何，您不太可能只想进行测试，因此在 jnz分支目标中放置 jc可以正常工作。 （如果您只想测试 equal_reflexive和 at_least_one_nan，则其他设置可能会适当地设置标志）。



考虑所有NaN相等，即使不是按位相等：

这与Paul R的回答是相同的想法，但有一个错误修正（将NaN检查与使用AND而不是OR的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

因此，在这种情况下，我们根本不需要 PTEST的 CF结果。我们使用 PCMPEQD时会这样做，因为它没有反数（ cmpunordps具有 cmpordps的方式）。

9个用于Intel SnB系列CPU的融合域uops。 （带有AVX的7：使用非破坏性3操作数指令来避免 movaps。）但是，Skylake SnB系列之前的CPU只能在p1上运行 cmpps，因此，如果吞吐量，则FP-add单元上的瓶颈是一个问题。 Skylake在p0 / p1上运行 cmpps。

andps的编码比 pand短，从Nehalem到Broadwell的Intel CPU只能在port5上运行。可能需要防止它从周围的FP代码中窃取p0或p1周期。否则， pandn可能是一个更好的选择。在AMD BD系列上， andnps始终在ivec域中运行，因此您不能避免int和FP向量之间的绕过延迟（否则，如果您使用 movmskps而不是 ptest可能会希望避免这种情况，在此版本中仅使用 cmpps，而不使用 pcmpeqd）。还要注意，此处为了便于阅读而选择了指令顺序。将FP compare（A，B）放在 ANDPS之前，可以帮助CPU更快地开始该周期。

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

如果向量在内存中，则至少需要使用单独的insn加载它们。另一个仅可以从内存中引用两次。如果未对齐 or the addressing mode can't micro-fuse，这很糟糕，但可能很有用。如果 vcmpps的操作数之一是已知没有任何NaN的向量（例如，零位寄存器），则 vcmpunord_qps xmm2, xmm15, [rsi]将在 [rsi]中找到NaN。

如果我们不想使用 PTEST，则可以通过使用相反的比较，但是将它们与相反的逻辑运算符（AND与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的编码。 （ Try it out。也许我们可以避免使用 POR或 PAND在每个操作数上分别合并 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只是翻转每种情况的最终结果，“奇数输出”仍位于第一行。

如果两个输入都取反（NaN-> non-NaN，反之亦然），我们只能得到想要的结果（如果A和B均为NaN，则为真）。这意味着我们可以在A和B上都执行 cmpordps之后将 pand的想法用作 cmpordps self,self的替代。这没有用：即使我们有AVX但没有AVX2，我们也可以使用 vandps和 vandnps（和 vmovmskps，因为 vptest仅是AVX2）。按位布尔值仅是单周期延迟，不要占用向量FP添加执行端口，该端口已经是此代码的瓶颈。



VFIXUPIMMPS

我花了一段时间阅读手册 grokking its operation。

如果源元素为NaN，则它可以修改目标元素，但这不能以dest元素为条件。

我希望我能想到一种方法 vcmpneqps然后用每个源操作数修复该结果（以消除合并3个 vcmpps指令结果的布尔指令）。我现在相当确定这是不可能的，因为仅仅知道一个操作数是NaN本身还不足以更改 IEEE_equal(A,B)结果。

我认为我们可以使用 vfixupimmps的唯一方法是分别检测每个源操作数中的NaN，就像 vcmpunord_qps一样，但更糟。或作为
真正愚蠢的替换 andps，在先前比较的掩码结果中检测到0或全1（NaN）。



AVX512屏蔽寄存器

使用AVX512屏蔽寄存器可以帮助组合比较结果。大多数AVX512比较指令将结果放入掩码寄存器中，而不是向量reg中的掩码向量中，因此，如果我们要在512b块中进行操作，我们实际上必须以这种方式进行操作。

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

通过将A中的掩码用作B上 vfpclassps的零掩码，我们只需两个指令即可找到两个NaN位置，而不是通常的cmp / cmp / combine。因此，我们保存了 or或 andn指令。顺便说一句，我想知道为什么没有OR-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是不能用作谓词的寄存器，因为该编码方式表示“无掩码”。）

我不确定我们是否可以为每个元素使用 reflexive_equal结果创建单个蒙版，而无需 k...指令在某个点上将两个蒙版组合在一起（例如，用 kandnw代替 ktestw）。掩码仅用作零掩码，不能用作可将结果强制为1的掩码，因此将 vfpclassps结果组合只能作为AND。因此，我认为我们一直坚持使用1-means-both-NaN，这是将其用作 vcmpps的零掩码的错误认识。先执行 vcmpps，然后将掩码寄存器用作 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中添加了 EFLAGS。

但是， kmov确实为您设置了popcnt，bsf或bsr。 （ bsf / jcc不会进行宏保险，因此在搜索循环中，您可能仍想测试/ jcc，并且在发现非零值时仅希望bsf。对tzcnt进行编码的额外字节不会除非您正在做无分支的事情，否则不要买任何东西，因为即使dest寄存器未定义， bsf仍会将ZF设置为零输入。尽管 lzcnt给出了 32 - bsr，所以即使在您知道输入为非零。）

我们还可以使用 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

只有当 kortest的大小与矢量中元素的数量完全匹配时，这种方法才有效。例如256b双精度元素向量仅包含4个元素，但是 kortestb仍根据输入掩码寄存器的低8位设置CF。



仅使用整数运算

除NaN以外，+ /-0是IEEE_equal与bitwise_equal不同的唯一时间。 （除非我丢失了某些东西。使用前请仔细检查此假设！） +0和 -0的所有位均为零，除了 -0设置了符号位（MSB）。

如果我们忽略不同的NaN编码，则除+/- 0情况外，我们想要的结果是bitwise_equal。除了符号位iff A和B均为+/- 0之外， A OR B均为0。根据是否需要覆盖按位，左移1将使其变为全零或非全零。 -相等测试。

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

该算法可能在不提供用于检测NaN的相同矢量FP测试的不同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版本低一两个周期。

我们实际上在这里充分利用了 PTEST的优势：在两个不同的操作数之间使用其ANDN，并在整个过程中使用其相对于零的比较。我们不能用 pandn / movmskps替换它，因为我们需要检查所有位，而不仅仅是每个元素的符号位。

我没有实际测试过，所以即使我的结论是+/- 0是IEEE_equal唯一不同于bitwise_equal（NaN除外）的时间，也可能是错误的。



用仅整数操作处理非按位相同的NaN可能不值得。 The encoding与+/- Inf非常相似，以至于我无法想到不需要几个指令的任何简单检查。 Inf设置了所有指数位，并且尾数全为零。 NaN设置了所有指数位，尾数又为非零有效位（因此有效载荷有23位）。尾数的MSB被解释为 is_quiet标志，以区分信令/静默NaN。另请参阅英特尔手册vol1，表4-3（ Floating-Point Number and NaN Encodings）。

如果不是使用前9位集编码的-Inf，我们可以使用 A > 0x7f800000的无符号比较来检查NaN。 （ 0x7f800000是单精度+ Inf）。但是，请注意 pcmpgtd / pcmpgtq是有符号整数比较。 AVX512F VPCMPUD是无符号比较（目标=屏蔽寄存器）。



OP的想法： !(a<b) && !(b<a)

OP的 !(a<b) && !(b<a)建议无效，也不能对其进行任何修改。您不能仅从两个具有反向操作数的比较中分辨出一个NaN和两个NaN之间的差异。甚至混合谓词也无济于事： VCMPPS谓词无法将一个操作数为NaN与两个操作数为NaN进行区分，或取决于是第一个还是第二个操作数为NaN。因此，将它们组合在一起就不可能获得该信息。

Paul R将向量与自身进行比较的解决方案确实使我们能够检测到NaN，并“手动”处理它们。两个操作数之间的 VCMPPS结果组合不足，但使用 A和 B以外的操作数确实有帮助。 （一个已知的非NaN向量或两次相同的操作数）。



如果不取反，按位NaN代码将查找至少一个元素相等的时间。 （ 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

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);