如何为浮点值实现totalOrder谓词?

问题描述 投票:3回答:1

IEEE 754规范在第5.10节中定义了总顺序,我要在汇编中实现。

the Wikipedia description起,听起来很像可以实现无分支或几乎无分支的实现,但是我一直无法提出一种体面的方法;而且我在主要的编程语言中找不到任何符合规范的实现]

比较两个浮点数时,它充当≤操作,除了totalOrder(−0,+0)¬¬totalOrder(+0,−0)以及同一个浮点数的不同表示形式是有序的乘以它们的指数乘以符号位。然后,通过对-qNaN

首先检查NaN,然后​​跳转到浮点比较或处理NaN情况是否有意义,或者将浮点值移到整数寄存器并在那里进行所有操作是否更有意义?

在x86-64处理器上实现浮点总数的最佳方法是什么?

assembly floating-point x86-64 ieee-754 micro-optimization
1个回答
5
投票

如果将FP位模式作为符号/幅度整数进行比较,这一切都将正常工作,包括-0 < +0和NaN位模式1。这就是为什么像binary64 (double)这样的IEEE格式使用偏差指数并将字段按该顺序放置的原因之一。 (另一个是通过位模式上的doublenextafter方便地实现nextafter的方法。)

可以用2的补码整数比较有效地实现:

    如果两个符号都已清除:非负数则正常工作>>
  • [如果仅将其符号位设置为1:任何负数都小于任何非负数,包括++作为--,所以2的补码-0.0 < +0.0起作用。
  • 如果

    both

  • 都设置了符号位(0x80000000 < 0x00000000):2的补码x <= y是符号/幅度FP (x&y)>>63。在x86 asm中,您可以避免移动,而只需看一下SF,或使用SIMD元素的高位。[在不弄乱x<y情况的情况下处理这个问题是很棘手的:您不能只对x>y符号进行XOR运算就成为==结果;当他们比较相等时,它将翻转它。当两个输入均为负时,会给您x&y,而在其他情况下会给您<。我不确定这是否可用于排序。


    使用<=,您可以在其普通XMM寄存器中对双FP值进行操作,对于32位浮点型,可以对SSE2(针对x86-64进行保证)对<进行操作。 (请注意,与SSE4.2 pcmpgtq相比,pcmpgtd相对较慢:端口更少,等待时间更长。pcmpgtq。例如,在Skylake上,1 p5 uop的延迟为3c,而pcmpgtd和pcmpeqq为1 uop的p0 / p1则为1 uop)周期延迟。)

我们无法仅使用一个pcmpgtd +符号修正来处理按位相等的情况。无论输入是正还是负,https://agner.org/optimize/给出的pcmpgtq结果均为0。根据总顺序将pcmpgtqx1 bitwise_eq x0sign(x0&x1)>表示为0或1表示基于>=的翻转会产生不一致的行为。但是不幸的是,FP比较的<行为意味着我们必须对等于FP的情况进行特殊处理,而不仅仅是FP无序的情况。

[您不需要汇编,只需在C语言中将pun打入<=,以使编译器可能使用-0.0 == +0.0,或将内在函数用于向量regs。

但是,如果您使用的是asm,则可以考虑进行FP比较并在ZF = 1上分支(将其设置为无序或相等)

,然后再执行整数。如果您期望NaN和完全相等(包括uint64_t)很少见,那么这可能会很好。请注意,对于movq rax, xmm0中的无序ZF,CF,PF = 1,1,1。所有x86 FP都直接或通过+-0.0 == -+0.0 /the ucomisd docs/ ucomisd以相同的方式比较设置标志。例如,独立版本可能看起来像这样。 (在内联时进行简化,例如,如果调用者分支,则直接使用fcom而不是fnstsw ax进行分支):

lahf

[使用AVX512VL,jb可以替换所有3个AND / XOR / OR操作;它可以实现3个输入的任意布尔函数。 

setb

没有SSE4.2,或者只是无标量无分支策略,我想到了这个。 (例如,如果值实际上在内存中,那么您只需执行totalOrder: ; 0/1 integer in EAX = (xmm0 <= xmm1 totalOrder) xor eax, eax ucomisd xmm0, xmm1 ; ZF=0 implies PF=0 (ordered) so just check ZF jz .compare_as_integer ; unordered or FP-equal ; else CF accurately reflects the < or > (total) order of xmm0 vs. xmm1 setb al ; or branch with jb ret ;; SSE4.2, using AVX 3-operand versions. Use movaps as needed for non-AVX ### Untested ; Used for unordered or FP-equal, including -0.0 == +0.0 ; but also including -1.0 == -1.0 for example .compare_as_integer: ; should work in general for any sign/magnitude integer vpcmpgtq xmm2, xmm1, xmm0 ; reversed order of comparison: x1>x0 == x0<x1 vpand xmm3, xmm1, xmm0 ; we only care about the MSB of the 64-bit integer vpxor xmm2, xmm3 ; flip if x0 & x1 are negative vpcmpeqq xmm1, xmm0 vpor xmm2, xmm1 ; top bits of XMM2 hold the boolean result for each SIMD element ; suitable for use with blendvpd vmovmskpd eax, xmm2 ; low bit of EAX = valid, high bit might be garbage and eax, 1 ; optional depending on use-case ; EAX=1 if x0 bitwise_eq x1 or sign/magnitude x1 > x0 ret 加载即可,而不是XMM规则中的vpternlogq。)>

vpternlogq

甚至在P6-系列上,对EAX (y_gt_x) ^ (x&y) | y_eq_x进行异或归零,然后用mov和8位movqcompare_as_integer:
    movq     rcx, xmm0
    movq     rsi, xmm1

    xor      eax, eax
    cmp      rcx, rsi
   ; je  bitwise equal special case would simplify the rest
    setl     al                 ; 2's complement x < y
    sete     dl
    and      rcx, rsi           ; maybe something with TEST / CMOVS?
    shr      rcx, 63
    xor      al, cl           ; flip the SETL result if both inputs were negative
    or       al, dl           ; always true on bitwise equal
    ret
写入AL。 (should make it safe to read EAX without a partial-reg stall)。在大多数其他CPU上,唯一的缺点是对RDX的旧值有错误的依赖关系,而我在setl之前没有打破过。如果我先对EDX进行了Xor归零,则可以将xoror转换为EAX。

分支策略可以这样工作:

Why doesn't GCC use partial registers?

如果需要,可以混合并匹配其中的部分;可以沿非等距路径使用AND / SHR / XOR代替sete dl


如果在分支结果的情况下内联,可以在特殊情况处理之前放置common(?)-case(有限且不相等)分支。但是然后特殊情况包括有序xor,因此在ZF = 1上希望进行预测的分支(包括PF = 1无序情况)可能还是个好主意。

or


脚注1:NaN编码作为总订单的一部分

FP值(及其符号/幅度编码)在零附近对称。即使对于NaN,符号位始终是符号位,因此可以用相同的方式进行处理。

    最小幅度当然是+ -0.0:所有指数和尾数位均为零。
  • 子法线具有零指数字段(最小值),表示尾数的前导零。显式部分为非零。大小与尾数呈线性关系。 (零实际上只是一个超常态的特例。)
  • 归一化的数字范围为指数= 1到指数
  • +-无限有指数=全1,尾数= 0
  • +-NaN的指数=全1,尾数=非零
    • 在x86上,sNaN清除的尾数最高位。其余部分是至少具有1个置位的有效载荷(否则它是Inf)。
  • 在x86上,qNaN具有尾数集的最高位。其余就是有效载荷
  • ;; probably slower compare_as_integer_branchy: movq rcx, xmm0 movq rsi, xmm1 xor eax, eax ; mov eax,1 with je to a ret wouldn't avoid partial-register stalls for setl al cmp rcx, rsi je .flip_result ; return 1 setl al ; 2's complement x < y test rcx, rsi js .flip_result ; if (x&y both negative) ret .flip_result: ; not bitwise EQ, and both inputs negative xor al, 1 ret (从test+js链接)显示了在其他两个ISA上的某些sNaN和qNaN编码。一些与x86不同,但是POWER和Alpha的qNaN设置了尾数的MSB,因此它们的整数大小比任何sNaN大。
  • PA-RISC选择了另一种方法,因此针对(过时的)ISA实施总订单谓词将需要针对FP比较无序情况进行额外的工作;如果在进行整数比较之前,如果两个值中的任何一个都是任何一种NaN,则将这两个值中的该位翻转可能会起作用。

    (我之所以这样说,是因为相同的算法可以用在x86上可能不专门使用的高级语言中。但是您可能只想保留它,并始终以相同的方式处理相同的二进制位模式,即使那样表示qNaN


    PS:我知道“ significand”在技术上更正确,但是“ mantissa”的音节较少,我更喜欢它,并且在这种情况下很好理解。]
    © www.soinside.com 2019 - 2024. All rights reserved.