与不使用if的测试相比,if语句的效率如何? (C ++)
我需要一个程序来获取两个数字中较小的数字,我想知道是否使用标准“如果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语句与一般的替代方案的效率。
(免责声明:以下内容涉及非常低级别的优化,这些优化通常不是必需的。如果您继续阅读,您放弃了投诉计算机速度快的权利,并且没有任何理由担心这类事情。)
消除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
在第二种情况下,不需要分支指令。 此外,它比您的比特笨重的实现更清晰,更易读。
当然,这是一种微优化,不太可能对您的代码产生重大影响。
简单的答案:一个条件跳转比两个减法,一个加法,一个按位和一个移位操作组合起来更有效。 我已经在这一点上受到了充分的学习(见评论),我甚至不再自信地说它通常更有效率。
实用的答案:无论哪种方式,你都没有为程序员弄清楚第二个例子正在做什么所花费的额外CPU周期。 程序的可读性首先,效率第二。
在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个指令。 我想我会继续编码,让编译器完成它的工作。
与任何低级优化一样,在目标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
不确定第一个在所有情况下是否更快,但我敢打赌它是。
最大的问题是你的第二个例子不适用于64位机器 。
然而,即使忽略了这一点,现代编译器也足够聪明,可以在每种情况下考虑无分支预测,并比较估计的速度。 所以,你的第二个例子很可能实际上更慢
if语句和使用三元运算符之间没有区别,因为即使是大多数愚蠢的编译器都足够聪明,可以识别这种特殊情况。
[编辑]因为我认为这是一个非常有趣的话题,所以我写了一篇博文 。
无论哪种方式,程序集只会是一些指令,无论哪种方式执行这些指令都需要皮秒。
我会将应用程序简介为优化工作,以实现更有价值的工作。
此外,这种类型的优化所节省的时间不值得任何试图维护它的人浪费时间。
对于像这样的简单语句,我发现三元运算符非常直观:
low = (a < b) ? a : b;
简洁明了。
对于像这样简单的事情,为什么不试验并尝试呢?
通常,您首先进行配置,将其识别为热点,尝试更改并查看结果。
我编写了一个简单的程序,用于比较使用Visual C ++ 2010传递随机数的两种技术(因此我们看不到完美的分支预测)。我的机器上100,000,000次迭代的方法之间的区别? 总计不到50毫秒,if版本往往更快。 查看codegen,编译器成功地将simple if转换为cmovl指令,完全避免了分支。
有一件事我会指出,我没有注意到这样的优化很容易被其他问题所淹没。 例如,如果您在两个大数字数组上运行此例程(或者更糟糕的是,数据对分散在内存中),那么在今天的CPU上获取值的成本很容易使CPU的执行管道停滞。
我只是想知道哪一个更有效(或者如果差异是微不足道的相关),以及if-else语句与一般的替代方案的效率。
桌面/服务器CPU针对流水线进行了优化。 其次在理论上更快,因为CPU不必分支并且可以利用多个ALU并行地评估表达式的部分。 具有混合独立操作的更多非分支代码最适合此类CPU。 (但即便如此,现在的“条件”CPU指令也可以否定它,它允许使第一个代码无分支。)
在嵌入式CPU上分支,如果通常更便宜(相对于其他所有),也没有很多备用ALU来无序地评估操作(即如果它们支持无序执行)。 更少的代码/数据更好 – 缓存也很小。 (我甚至在嵌入式应用程序中看到了buble-sort的使用:该算法使用最少的内存/代码,并且足够快以获取少量信息。)
重要提示:不要忘记编译器优化。 使用许多技巧,编译器有时可以自行删除分支:内联,不断传播,重构等。
但最后我会说是的,相关的差异是微不足道的。 从长远来看,可读代码获胜。
在CPU前端的方式上,现在投入时间使代码具有multithreading和OpenCL能力是更有意义的。
当你进入真正有点繁琐的黑客攻击时,要注意的一件事是他们如何与内联后发生的编译器优化进行交互。 例如,可读程序
int foo (int a, int b) { return ((a < b) ? a : b); }
在任何情况下都可能被编译成非常有效的东西,但在某些情况下它可能会更好。 例如,假设某人写作
int bar = foo (x, x+3);
在内联之后,编译器将识别出3
是正的,然后可以利用未定义签名溢出的事实来完全消除测试,以获得
int bar = x;
在这种情况下,编译器应该如何优化第二个实现是不太清楚的。 当然,这是一个相当人为的例子,但类似的优化实际上在实践中很重要。 当然,当性能至关重要时,你不应该接受错误的编译器输出,但是在你诉诸代码之前看看是否可以找到产生良好输出的清晰代码可能是明智的,因为编译器的下一个,惊人的改进版本不会能够优化到死亡。
为什么low = a;
在if
和low = a;
在else
? 而且,为什么31
? 如果31与CPU字大小有关,那么如果代码要在不同大小的CPU上运行怎么办?
if..else方式看起来更具可读性。 我喜欢程序对人类可读,对编译器也是如此。
使用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; }
根据数据,在上述环境中,与此处所述的几种信念完全相反的情况并非如此。 注意'在这个环境中'如果构造比三元更快? :构造
我不久前写过三元逻辑模拟器,这个问题对我来说是可行的,因为它直接影响了我的解释器执行速度; 我被要求尽快模拟吨和吨的三元逻辑门。
在二进制编码三元系统中,一个trit以两位打包。 最重要的比特意味着消极,最不重要意味着正数。 情况“11”不应该发生,但必须正确处理并威胁为0。
考虑inline 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位signed 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
指令。 遗憾的是,缓存很小(如果你的索引长度大于几位),你根本就无法使用它。
所以我想我回答了你的问题,关于什么可以分支/无分支代码。 答案更好,具有详细的样本,实际应用和真实的性能测量结果。
更新了当前(2018)编译器矢量化状态的答案。 有关矢量化不是问题的一般情况,请参阅danben的答案 。
TLDR摘要 :避免s可以帮助进行矢量化。
因为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或__m512i扩展到__m256i,使用avx512(甚至可以进一步展开循环以利用其他寄存器)或其他simd指令其他架构。 另一个优点是这些指令都是低延迟,高吞吐量指令(延迟为~1,倒数吞吐量在0.33到0.5范围内 – 因此相对于非向量化代码非常快)
我认为没有理由为什么编译器无法将if语句优化为矢量化条件移动(除了相应的x86操作仅适用于内存位置并且具有低吞吐量而其他架构如arm可能完全缺乏它)但是它可以通过做类似的事情:
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); }
然而,由于存储器读取和写入以及与上述示例相比较低的吞吐量(更高/更差的倒数吞吐量),这将具有更高的延迟。
除非你真的试图降低效率,否则我认为这不是你需要担心的事情。
我的简单想法是if会更快,因为它比较一件事,而另一部分代码正在做几个操作。 但同样,我想,差异是微不足道的。
如果是Gnu C ++,试试这个
int min = i j;
我没有描述它,但我认为它绝对是一个可以击败的人。