与不使用 if 的测试相比，if 语句的效率如何？ (C++)

Question

我需要一个程序来获取两个数字中较小的一个，我想知道使用标准“如果 x 小于 y”是否

int a, b, low;
if (a < b) low = a;
else low = b;

比这个更有效率或更低：（

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

或者将 int delta = a - b 位于顶部，并用它重新替换 a - b 的实例）。

我只是想知道其中哪一个更有效（或者如果差异太小而无法相关），以及 if-else 语句与一般替代方案的效率。

Answer 1

更新的答案采用编译器矢量化的当前（2018）状态。请参阅 danben 的回答，了解矢量化不是问题的一般情况。

TLDR 摘要：避免 if 有助于矢量化。

由于 SIMD 过于复杂，无法在某些元素上进行分支，而在其他元素上则不允许，因此任何包含 if 语句的代码都将无法进行矢量化，除非编译器知道可以将其重写为无分支操作集。我不知道有任何编译器将其作为矢量化过程的集成部分（Clang 独立执行其中一些操作，但不是专门帮助矢量化 AFAIK）

使用 OP 提供的示例：

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

许多编译器可以将其矢量化为某种东西大约相当于：

__m128i low128i(__m128i a, __m128i b){
  __m128i diff, tmp;
  diff = _mm_sub_epi32(a,b);
  tmp = _mm_srai_epi32(diff, 31);
  tmp = _mm_and_si128(tmp,diff);
  return _mm_add_epi32(tmp,b);
}

这种优化需要以允许的方式布局数据，但它可以扩展到带有avx2的__m256i或带有avx512的__m512i（甚至进一步展开循环以利用额外的寄存器）或其他架构上的其他 simd 指令。另一个优点是这些指令都是低延迟、高吞吐量指令（延迟约为 1，吞吐量倒数在 0.33 到 0.5 范围内 - 相对于非向量化代码来说非常快）

我看不出编译器为什么要这样做无法将 if 语句优化为向量化条件移动（除了相应的 x86 操作仅在内存位置上工作并且吞吐量较低，而其他架构（如 ARM）可能完全缺乏它），但它可以em> 可以通过执行以下操作来完成：

void lowhi128i(__m128i *a, __m128i *b){ // does both low and high
  __m128i _a=*a, _b=*b;
  __m128i lomask =  _mm_cmpgt_epi32(_a,_b),
  __m128i himask =  _mm_cmpgt_epi32(_b,_a);
  _mm_maskmoveu_si128(_b,lomask,a);
  _mm_maskmoveu_si128(_a,himask,b);
}

但是，与上面的示例相比，由于内存读取和写入以及较低的吞吐量（更高/更差的倒数吞吐量），这会产生更高的延迟。

Answer 2

除非您真的想提高效率，否则我认为您不需要担心这一点。

我的简单想法是 if 会更快，因为它比较一件事，而其他代码正在执行多项操作。但我再次认为差异是微乎其微的。

Answer 3

如果它是针对 Gnu C++ 的，请尝试这个，

int min = i <? j;

我还没有对其进行分析，但我认为它绝对是最值得击败的。

Answer 4

理由担心此类事情。）

（免责声明：以下内容涉及通常没有必要的非常低级的优化。如果您继续阅读，您就放弃了抱怨计算机速度快的权利，并且没有任何 消除 if 语句的优点是可以避免分支预测惩罚。

分支预测惩罚通常仅在分支不易预测时才成为问题。当分支几乎总是被采用/不被采用时，或者它遵循简单的模式时，很容易预测该分支。例如，循环语句中的分支除了最后一次外每次都会进行，因此很容易预测。但是，如果您有这样的代码

a = random() % 10
if (a < 5)
  print "Less"
else
  print "Greater"

，则该分支不容易预测，并且经常会产生与清除缓存和回滚在分支的错误部分执行的指令相关的预测损失。

避免此类惩罚的一种方法是使用三元 (?:) 运算符。在简单的情况下，编译器将生成条件移动指令而不是分支。

因此

int a, b, low;
if (a < b) low = a;
else low = b;

，

int a, b, low;
low = (a < b) ? a : b

在第二种情况下，不需要分支指令。此外，它比你的琐碎实现更清晰、更具可读性。

当然，这是一个微观优化，不太可能对您的代码产生重大影响。

Answer 5

在 gcc 4.3.4、amd64（core 2 duo）、Linux 上编译：

int foo1(int a, int b)
{
    int low;
    if (a < b) low = a;
    else low = b;
    return low;
}

int foo2(int a, int b)
{
    int low;
    low = b + ((a - b) & ((a - b) >> 31));
    return low;
}

我得到：

foo1:
    cmpl    %edi, %esi
    cmovle  %esi, %edi
    movl    %edi, %eax
    ret

foo2:
    subl    %esi, %edi
    movl    %edi, %eax
    sarl    $31,  %eax
    andl    %edi, %eax
    addl    %esi, %eax
    ret

...我很确定这不会计入分支预测，因为代码不会跳转。此外，非 if 语句版本长了 2 个指令。我想我会继续编码，让编译器完成它的工作。

Answer 6

简单答案：一个条件跳转将比两个减法、一个加法、一个按位与和一个移位运算的组合更有效。 在这一点上我已经受过充分的教育（请参阅评论）我什至不再有足够的信心说它通常更有效。

务实的答案：无论哪种方式，您为额外的 CPU 周期支付的费用都不会像程序员为弄清楚第二个示例在做什么而花费的时间一样多。程序的可读性第一，效率第二。

Answer 7

最大的问题是您的第二个示例无法在 64 位计算机上运行。

然而，即使忽略这一点，现代编译器也足够聪明，可以在每种可能的情况下考虑无分支预测，并比较估计的速度。因此，您的第二个示例将实际上很可能更慢

if 语句和使用三元运算符之间没有区别，因为即使大多数愚蠢的编译器也足够聪明来识别这种特殊情况。

---

[编辑]因为我认为这是一个非常有趣的话题，所以我写了关于它的博客文章。

Answer 8

与任何低级优化一样，在目标 CPU/主板设置上对其进行测试。

在我的编译器（x86_64 上的 gcc 4.5.1）上，第一个示例变为

cmpl    %ebx, %eax
cmovle  %eax, %esi

第二个示例变为

subl    %eax, %ebx
movl    %ebx, %edx
sarl    $31, %edx
andl    %ebx, %edx
leal    (%rdx,%rax), %esi

不确定第一个示例是否在所有情况下都更快，但我敢打赌它是。

Answer 9

无论哪种方式，汇编都只会是一些指令，并且无论哪种方式，执行这些指令都需要皮秒。

我会分析该应用程序，并将您的优化工作集中在更有价值的事情上。

此外，这种类型的优化节省的时间不值得任何试图维护它的人浪费的时间。

对于像这样的简单语句，我发现三元运算符非常直观：

low = (a < b) ? a : b;

清晰简洁。

Answer 10

对于如此简单的事情，为什么不直接尝试一下呢？

一般来说，您首先会进行分析，将其识别为热点，尝试更改并查看结果。

我编写了一个简单的程序，将两种传入随机数的技术（这样我们看不到完美的分支预测）与 Visual C++ 2010 进行比较。在我的机器上进行 100,000,000 次迭代时，两种方法之间的差异是什么？总共不到 50 毫秒，if 版本往往更快。查看代码生成器，编译器成功地将简单的 if 转换为 cmovl 指令，完全避免了分支。

Answer 11

当您遇到真正有点棘手的黑客行为时，需要警惕的一件事是它们如何与内联后发生的编译器优化交互。例如，可读过程

int foo (int a, int b) {
   return ((a < b) ? a : b);
}

在任何情况下都可能被编译成非常有效的东西，但在某些情况下它可能甚至更好。举个例子，假设有人写了

int bar = foo (x, x+3);

After inlined，编译器会识别出 3 是正数，然后可能会利用有符号溢出未定义的事实来完全消除测试，得到

int bar = x;

很多不太清楚编译器应如何在这种情况下优化您的第二个实现。当然，这是一个相当人为的示例，但类似的优化实际上在实践中很重要。当然，当性能至关重要时，您不应该接受糟糕的编译器输出，但明智的做法是，在使用下一个经过惊人改进的编译器版本不会出现的代码之前，先看看是否能找到能够产生良好输出的清晰代码。能够优化至死。

Answer 12

我要指出的一件事是，我没有注意到提到这样的优化很容易被其他问题所淹没。例如，如果您在两个大型数字数组（或更糟糕的是，分散在内存中的数字对）上运行此例程，则在当今的 CPU 上获取值的成本很容易使 CPU 的执行管道停顿。

Answer 13

我只是想知道其中哪一个
会更有效率（或者如果
差异微乎其微
相关），以及效率
if-else 语句与替代语句
一般来说。

台式机/服务器 CPU 针对流水线进行了优化。第二个理论上更快，因为 CPU 不必分支并且可以利用多个 ALU 并行计算表达式的各个部分。更多具有混合独立操作的非分支代码最适合此类 CPU。 （但即使如此，现在也被现代的“条件”CPU 指令所否定，这些指令也允许使第一个代码无分支。）

在嵌入式 CPU 上，分支通常成本较低（相对于其他一切），而且它们也没有许多备用 ALU 来评估乱序操作（即它们是否支持乱序执行）。代码/数据越少越好——缓存也很小。 （我什至在嵌入式应用程序中看到了冒泡排序的使用：该算法使用最少的内存/代码，并且对于少量信息来说足够快。）

重要提示：不要忘记编译器优化。使用许多技巧，编译器有时可以自行删除分支：内联、常量传播、重构等。

但最后我想说的是，是的，差异很小。从长远来看，可读的代码会获胜。

从 CPU 方面的进展情况来看，现在投入时间使代码具有多线程和 OpenCL 功能会更有价值。

Answer 14

为什么if中的low = a;和else中的low = a;？而且，为什么是31？如果 31 与 CPU 字大小有关，那么如果代码要在不同大小的 CPU 上运行怎么办？

if..else 方式看起来更具可读性。我希望程序对于人类来说就像对于编译器一样可读。

Answer 15

使用 gcc -o foo -g -p -O0 的配置文件结果，Solaris 9 v240

 %Time Seconds Cumsecs  #Calls   msec/call  Name
  36.8    0.21    0.21 8424829      0.0000  foo2
  28.1    0.16    0.37       1    160.      main
  17.5    0.10    0.4716850667      0.0000  _mcount
  17.5    0.10    0.57 8424829      0.0000  foo1
   0.0    0.00    0.57       4      0.      atexit
   0.0    0.00    0.57       1      0.      _fpsetsticky
   0.0    0.00    0.57       1      0.      _exithandle
   0.0    0.00    0.57       1      0.      _profil
   0.0    0.00    0.57    1000      0.000   rand
   0.0    0.00    0.57       1      0.      exit

代码：

int
foo1 (int a, int b, int low)        
{
   if (a < b) 
      low = a;   
   else 
      low = b;         
   return low;
}

int                       
foo2 (int a, int b, int low)
{
   low = (a < b) ? a : b;
   return low;
}


int main()
{
    int low=0;
    int a=0;
    int b=0;
    int i=500;
    while (i--)
    {
       for(a=rand(), b=rand(); a; a--)
       {
           low=foo1(a,b,low);
           low=foo2(a,b,low);
       }        
    }
    return 0;
}

根据数据，在上述环境中，没有发现与此处所述的几个信念完全相反的事实。请注意“在此环境中”如果构造比三元更快？ ：构建

Answer 16

我不久前写过三元逻辑模拟器，这个问题对我来说是可行的，因为它直接影响我的解释器执行速度；我需要尽快模拟大量的三元逻辑门。

在二进制编码三进制系统中，一个 trit 被打包在两位中。最高有效位表示负数，最低有效位表示正数。情况“11”不应发生，但必须正确处理并威胁为 0。

考虑内联 int bct_decoder( unsigned bctData ) 函数，该函数应将格式化的 trit 返回为常规整数 -1、0 或1;据我观察，有 4 种方法：我将它们称为“cond”、“mod”、“math”和“lut”；让我们研究一下它们

首先是基于 jz|jnz 和 jl|jb 条件跳转，因此 cond。它的性能一点也不好，因为依赖于分支预测器。更糟糕的是 - 它会变化，因为不知道是否会有一个或两个先验分支。这是一个例子：

inline int bct_decoder_cond( unsigned bctData ) {
   unsigned lsB = bctData & 1;
   unsigned msB = bctData >> 1;
   return
       ( lsB == msB ) ? 0 : // most possible -> make zero fastest branch
       ( lsB > msB ) ? 1 : -1;
}

这是最慢的版本，在最坏的情况下它可能涉及 2 个分支，这是二进制逻辑失败的地方。在我的 3770k 上，它对随机数据的平均速度约为 200MIPS。 （这里和之后 - 每个测试都是随机填充的 2mb 数据集上 1000 次尝试的平均值）

下一个依赖于模运算符，其速度介于第一和第三之间，但绝对更快 - 600 MIPS：

inline int bct_decoder_mod( unsigned bctData ) {
    return ( int )( ( bctData + 1 ) % 3 ) - 1;
}

下一个是无分支方法，它只涉及数学，因此数学；它根本不假设跳转指令：

inline int bct_decoder_math( unsigned bctData ) {
    return ( int )( bctData & 1 ) - ( int )( bctData >> 1 );
}

这做了应该做的事情，并且表现得非常好。相比之下，性能估计为 1000 MIPS，比分支版本快 5 倍。由于缺乏本机 2 位有符号 int 支持，分支版本可能会变慢。但在我的应用程序中，它本身就是一个很好的版本。

如果这还不够，那么我们可以更进一步，有一些特别的东西。接下来是查找表方法：

inline int bct_decoder_lut( unsigned bctData ) {
    static const int decoderLUT[] = { 0, 1, -1, 0 };
    return decoderLUT[ bctData & 0x3 ];
}

在我的例子中，一个 trit 仅占用 2 位，因此 lut 表只有 2b*4 = 8 字节，值得尝试。它适合缓存，工作速度极快，速度为 1400-1600 MIPS，这是我的测量精度下降的地方。这就是快速数学方法的 1.5 倍加速。这是因为您只有预先计算的结果和单个 AND 指令。遗憾的是，缓存很小，并且（如果您的索引长度大于几位）您根本无法使用它。

所以我想我回答了你的问题，关于分支/无分支代码是什么样的。答案要好得多，并且有详细的示例、真实世界的应用和真实的性能测量结果。