PROSAGA码农传奇-嵌入式C/C++-是否有无分支方法可以快速找到两个双精度浮点值的最小值/最大值？

<div class =“post-text”itemprop =“text”>
  
    是的，有办法计算两个的最大值或最小值
     <code>
 double
 </code>
    s没有任何分支。这样做的C ++代码如下所示：
  
   <pre>
 <code>
 #include <algorithm>

double FindMinimum(double a, double b)
{
    return std::min(a, b);
}

double FindMaximum(double a, double b)
{
    return std::max(a, b);
}

</code>
 </pre>
  
    我打赌你以前见过这个。为免你不相信这是无网格的，
    <a href =“https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:c% 2B％2B，源：“++++％23include +％3Calgorithm％3E％0A 0A％++++双+ FindMinimum（双+ A，+双+ b）％0A ++++％7B％0A ++++++ ++ +返回的std ::分钟（A，+ b）％3B％0A ++++％7D％0A 0A％++++双+ FindMaximum（双+ A，+双+ b）％0A ++++％7B％0A +++ +++++返回+的std ::最大值（A，+ b）％3B％0A ++++％7D '），L：' 5' ，N： '0'，O：'C％2B％2B +源+ 231％ ”，T： '0'））中，k：31.467710371819962，L： '4'，M：100，N： '0'，O： ''，S：0，T： '0'），（G：！ （（G：（（H：编译器，I：（编译器：clang700，过滤器：（b： '0'，二进制： '1'，commentOnly： '0'，还原函数： '0'，指示： '0'中，执行： '1'，英特尔： '0'，libraryCode： '1'，修剪： '1'），fontScale：0.8957951999999999，郎：C％2B％2B，库：（），选择：！ - O2 + - fverbose-ASM '来源：1），L： '5'，N： '0'，O：' 的x86-64 +铛+ 7.0.0 +（编辑+ 231％，+ +编译器231％）+ C％2B％ 2B”，T： '0'）），报头:(）中，k：64.41182865840402，L： '4'，M：22.5，N： '0'，O： ''，S：0，T： '0' ），（G：（（H：编译器，I：（编译器：G83，过滤器：（b： '0'，二进制： '1'，commentOnly： '0'，还原函数： '0'，指示：“0 '执行： '1'，英特尔： '0'，libraryCode： '1'，修剪：' 1 '），朗：C％2B％2B，库：（），选择：！ - O2 + -fverbose-ASM '来源：1），L： '5'，N： '0'，O：' x86的64 + GCC + 8.3 +（编者+％231，+编译+％232）+ C％2B％2B 'T： '0'）），报头:(），L： '4'，M：25.963673057517656，N：' 0' ，O： ''，S：0，T： '0'），（G：（（H：编译器，I：（编译器：vcpp_v19_16_x64，过滤器：（b： '0'，二进制： '1' ，commentOnly： '0'，还原函数： '0'，指示： '0'，执行： '1'，英特尔： '0'，libraryCode： '1'，修剪： '1'），郎：C％2B％如图2B所示，库：（），选择：/ O2，来源：1），L： '5'，N： '0'，O：'64 + MSVC + v19.16 +（编者+％231，+编译+％233 ）+ C％2B％2B 'T： '0'）），报头:(），L： '4'，M：51.53632694248234，N： '0'，O： ''，S：0，T：' 0 '））中，k：68.53228962818004，L：' 3' ，N： '0'，O： ''，T： '0'）），L： '2'，N： '0'，O： '' ，t：'0'）），版本：4“rel =”nofollow noreferrer“>
      检查拆卸
    </A>
    ：
  
   <pre>
 <code>
 FindMinimum(double, double):
 minsd xmm1, xmm0
 movapd xmm0, xmm1
 ret

FindMaximum(double, double):
    maxsd   xmm1, xmm0
    movapd  xmm0, xmm1
    ret

</code>
 </pre>
  
    这就是你从所有针对x86的流行编译器中获得的。使用SSE2指令集，特别是
     <code>
 minsd
 </code>
    /
     <code>
 maxsd
 </code>
     指令，无分支地评估两个双精度浮点值的最小值/最大值。
  
  
    所有64位x86处理器都支持
    <a href="https://en.wikipedia.org/wiki/SSE2" rel="nofollow noreferrer">
      SSE2
    </A>
    ;它是AMD64扩展所必需的。即使大多数没有64位的x86处理器也支持SSE2。它于2000年发布。你必须回到很长的路才能找到一台不支持SSE2的处理器。但是，如果你这样做呢？好吧，即使在那里，
    <a href =“https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:c% 2B％2B，源：“++++％23include +％3Calgorithm％3E％0A 0A％++++双+ FindMinimum（双+ A，+双+ b）％0A ++++％7B％0A ++++++ ++ +返回的std ::分钟（A，+ b）％3B％0A ++++％7D％0A 0A％++++双+ FindMaximum（双+ A，+双+ b）％0A ++++％7B％0A +++ +++++返回+的std ::最大值（A，+ b）％3B％0A ++++％7D '），L：' 5' ，N： '0'，O：'C％2B％2B +源+ 231％ ”，T： '0'））中，k：31.467710371819962，L： '4'，M：100，N： '0'，O： ''，S：0，T： '0'），（G：！ （（G：（（H：编译器，I：（编译器：clang700，过滤器：（b： '0'，二进制： '1'，commentOnly： '0'，还原函数： '0'，指示： '0'中，执行： '1'，英特尔： '0'，libraryCode： '1'，修剪： '1'），fontScale：0.8957951999999999，郎：C％2B％2B，库：（），选择：！ - O2 + - fverbose-ASM + -mno-SSE + -m32' ，来源：1），L： '5'，N： '0'，O：'的x86-64 +铛+ 7.0.0 +（编辑+ 231％，+ +编译器231％ ）+ C％2B％2B”，T： '0'）），报头:(）中，k：64.41182865840402，L： '4'，M：22.5，N： '0'，O： ''，S：0 ，T： '0'），（G：（（H：编译器，I：（编译器：G83，过滤器：（b： '0'，二进制： '1'，commentOnly： '0'，还原函数：'0 ”，指示： '0'，执行： '1'，英特尔： '0'，libraryCo DE： '1'，修剪： '1'），郎：C％2B％2B，库：（），选项： ' - O2 + -fverbose-ASM + -mno-SSE + -m32'，源：1）中，l ： '5'，N： '0'，O： '的x86-64 + GCC + 8.3 +（编者+％231，+编译+％232）+ C％2B％2B'，T： '0'）），报头： （）中，l： '4'，M：25.963673057517656，N： '0'，O： ''，S：0，T： '0'），（G：（（H：编译器，I：（编译器： vcpp_v19_16_x86，过滤器：（b： '0'，二进制： '1'，commentOnly： '0'，还原函数： '0'，指示： '0'，执行： '1'，英特尔： '0'，libraryCode：” 1' ，修剪： '1'），郎：C％2B％2B，库：（），选项： '/ O2 + /拱：IA32'，来源：1），L： '5'，N：'0 ”，O： '86 + MSVC + v19.16 +（编辑+ 231％，+ +编译器233％）+ C％2B％2B'，T： '0'）），报头:(），L： '4'，米：51.53632694248234，N： '0'，O： ''，S：0，T： '0'））中，k：68.53228962818004，L： '3'，N： '0'，O： ''，T： '0'）），l：'2'，n：'0'，o：''，t：'0'）），版本：4“rel =”nofollow noreferrer“>
      你在大多数流行的编译器上获得无代码代码
    </A>
    ：
  
   <pre>
 <code>
 FindMinimum(double, double):
 fld QWORD PTR [esp + 12]
 fld QWORD PTR [esp + 4]
 fucomi st(1)
 fcmovnbe st(0), st(1)
 fstp st(1)
 ret

FindMaximum(double, double):
    fld      QWORD PTR [esp + 4]
    fld      QWORD PTR [esp + 12]
    fucomi   st(1)
    fxch     st(1)
    fcmovnbe st(0), st(1)
    fstp     st(1)
    ret

</code>
 </pre>
  
    该
     <code>
 fucomi
 </code>
     指令执行比较，设置标志，然后执行
     <code>
 fcmovnbe
 </code>
     指令根据这些标志的值执行条件移动。这完全是无分支的，并且依赖于1995年使用Pentium Pro引入x86 ISA的指令，自Pentium II以来支持所有x86芯片。
  
    唯一的编译器
    
      惯于
    
     这里生成无分支代码是MSVC，因为
    <a href="https://stackoverflow.com/questions/13661285/generating-cmov-instructions-using-microsoft-compilers/41144749#41144749">
      它没有利用
       <code>
 FCMOVxx
 </code>
       指令
    </A>
    。相反，你得到：
  
   <pre>
 <code>
 double FindMinimum(double, double) PROC
 fld QWORD PTR [a]
 fld QWORD PTR [b]
 fcom st(1) ; compare "b" to "a"
 fnstsw ax ; transfer FPU status word to AX register
 test ah, 5 ; check C0 and C2 flags
 jp Alt
 fstp st(1) ; return "b"
 ret
Alt:
 fstp st(0) ; return "a"
 ret
double FindMinimum(double, double) ENDP

double FindMaximum(double, double) PROC
    fld     QWORD PTR [b]
    fld     QWORD PTR [a]
    fcom    st(1)            ; compare "b" to "a"
    fnstsw  ax               ; transfer FPU status word to AX register
    test    ah, 5            ; check C0 and C2 flags
    jp      Alt
    fstp    st(0)            ; return "b"
    ret
Alt:
    fstp    st(1)            ; return "a"
    ret
double FindMaximum(double, double) ENDP

</code>
 </pre>
  
    注意分支
     <code>
 JP
 </code>
     指令（如果设置了奇偶校验位，则跳转）该
     <code>
 FCOM
 </code>
     指令用于进行比较，它是基本x87 FPU指令集的一部分。不幸的是，这会在FPU状态字中设置标志，因此为了分支这些标志，需要提取它们。这就是目的
     <code>
 FNSTSW
 </code>
     指令，将x87 FPU状态字存储到通用目的
     <code>
 AX
 </code>
     注册（它也可以存储到内存中，但是为什么？）。那么代码
     <code>
 TEST
 </code>
    s相应的位，并相应地分支以确保返回正确的值。除了分支之外，检索FPU状态字也将相对较慢。这就是Pentium Pro推出的原因
     <code>
 FCOM
 </code>
     说明。
  
  
    但是，确实如此
    
      不会
    
     通过使用bit-twiddling操作来确定min / max，您将能够提高任何代码的速度。有两个基本原因：
  
  <OL>
    <LI>
      
        生成低效代码的唯一编译器是MSVC，并且没有好的方法来强制它生成您想要的指令。虽然MSVC支持32位x86目标的内联汇编，
        <a href="https://stackoverflow.com/questions/3323445/what-is-the-difference-between-asm-asm-and-asm/35959859#35959859">
          在寻求性能改进时，这是一个愚蠢的差事
        </A>
        。我也会引用自己的话：
      
      <BLOCKQUOTE>
        
          内联汇编以相当重要的方式破坏优化器，因此除非您正在编写
          
            重大
          
           内联汇编中的代码，不太可能有大幅的净性能增益。此外，Microsoft的内联汇编语法非常有限。它在很大程度上简化了灵活性。特别是，没有办法指定
          
            输入
          
           值，因此您将来自内存的输入加载到寄存器中，并且调用者被迫将输入从寄存器溢出到内存中进行准备。这就产生了一种我喜欢称之为“一个完整的随机播放”的现象，或简称为“慢速代码”。在可接受慢代码的情况下，不要放入内联汇编。因此，最好（至少在MSVC上）找出如何编写C / C ++源代码，以说服编译器发出所需的目标代码。即使你只能得到
          
            关
          
           对于理想的输出，这仍然比使用内联汇编所支付的罚款要好得多。
        
      </BLOCKQUOTE>
    </LI>
    <LI>
      
        为了访问浮点值的原始位，您必须进行域转换，从浮点到整数，然后再回到浮点。那很慢，
        
          特别
        
         没有SSE2，因为从x87 FPU获取值到ALU中的通用整数寄存器的唯一方法是间接通过内存。
      
    </LI>
  </醇>
  
    无论如何你想要采用这种策略，但是要对它进行基准测试，你可以利用浮点值按字典顺序排列的事实。
    <a href="https://en.wikipedia.org/wiki/IEEE_754" rel="nofollow noreferrer">
      IEEE 754
    </A>
     表示，除了符号位。所以，既然你假设两个值都是正数：
  
   <pre>
 <code>
 FindMinimumOfTwoPositiveDoubles(double a, double b):
 mov rax, QWORD PTR [a]
 mov rdx, QWORD PTR [b]
 sub rax, rdx ; subtract bitwise representation of the two values
 shr rax, 63 ; isolate the sign bit to see if the result was negative
 ret

FindMaximumOfTwoPositiveDoubles(double a, double b):
    mov   rax, QWORD PTR [b]    ; \ reverse order of parameters
    mov   rdx, QWORD PTR [a]    ; /  for the SUB operation
    sub   rax, rdx
    shr   rax, 63
    ret

</code>
 </pre>
  
    或者，为了避免内联汇编：
  
   <pre>
 <code>
 bool FindMinimumOfTwoPositiveDoubles(double a, double b)
{
 static_assert(sizeof(a) == sizeof(uint64_t),
 "A double must be the same size as a uint64_t for this bit manipulation to work.");
 const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
 const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
 return ((aBits - bBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}

bool FindMaximumOfTwoPositiveDoubles(double a, double b)
{
 static_assert(sizeof(a) == sizeof(uint64_t),
 "A double must be the same size as a uint64_t for this bit manipulation to work.");
 const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
 const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
 return ((bBits - aBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}

</code>
 </pre>
  
    请注意有
    
      严重
    
     警告这个实现。特别是，如果两个浮点值具有不同的符号，或者两个值都为负，它将会中断。如果两个值都为负，则可以修改代码以翻转其符号，进行比较，然后返回相反的值。要处理两个值具有不同符号的情况，可以添加代码以检查符号位。
  
   <pre>
 <code>
 // ...

// Enforce two's-complement lexicographic ordering.
 if (aBits < 0)
 {
 aBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - aBits);
 }
 if (bBits < 0)
 {
 bBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - bBits);
 }

// ...

</code>
 </pre>
  
    处理负零也将是一个问题。 IEEE 754表示+0.0等于？0.0，因此您的比较函数必须决定是否要将这些值视为不同，或者将特殊代码添加到确保负零和正零的比较例程被视为等价。
  
  
    添加所有这些特殊情况代码将
    
      当然
    
     将性能降低到我们将通过一个简单的浮点比较来实现收支平衡，并且最终可能会变慢。
  
</DIV>