在模运算和赋值操作之前使用`if`语句是否多余?

46

考虑下面的代码:

unsigned idx;
//.. some work with idx
if( idx >= idx_max )
    idx %= idx_max;

可以简化为只有第二行:

idx %= idx_max;

并且将会达到相同的结果。


我遇到过几次下面的代码:

unsigned x;
//... some work with x
if( x!=0 )
  x=0;

可以简化为

x=0;

问题:

  • 是否有必要使用if语句?特别是在ARM Thumb指令集下。
  • 这些if语句能否省略?
  • 编译器会进行哪些优化?

13
这些片段并不等价。"仅保留第二行即可简化,且会获得相同的结果"是错误的。 - ThingyWotsit
2
代码片段并不能清楚地表达你想要询问的问题。 - ShahzadIftikhar
2
我认为这两个引号并不等同。它们都阐述了一个问题:看似(或实际上)多余的if结构以及使用它们的可能原因。 - Yunnosch
5
请考虑当“idx”的值较大、相等和小于“idx_max”时会发生什么。 - ThingyWotsit
1
这应该是两个不同的问题。 - Daniel Daranas
显示剩余7条评论
4个回答

66
如果你想了解编译器在做什么,你需要查看一些汇编代码。我推荐这个网站(我已经输入了问题中的代码):https://godbolt.org/g/FwZZOb
第一个例子更有趣。
int div(unsigned int num, unsigned int num2) {
    if( num >= num2 ) return num % num2;
    return num;
}

int div2(unsigned int num, unsigned int num2) {
    return num % num2;
}

生成:

div(unsigned int, unsigned int):          # @div(unsigned int, unsigned int)
        mov     eax, edi
        cmp     eax, esi
        jb      .LBB0_2
        xor     edx, edx
        div     esi
        mov     eax, edx
.LBB0_2:
        ret

div2(unsigned int, unsigned int):         # @div2(unsigned int, unsigned int)
        xor     edx, edx
        mov     eax, edi
        div     esi
        mov     eax, edx
        ret

基本上,编译器出于特定且合理的原因将不会优化该分支。如果整数除法与比较大致相同的代价,那么该分支就将是毫无意义的。但是整数除法(通常与模操作一起执行)实际上是非常昂贵的:http://www.agner.org/optimize/instruction_tables.pdf。这些数字在架构和整数大小方面差异很大,但通常的延迟时间可以从15个到接近100个周期。

通过在执行模操作之前进行分支,您实际上可以节省很多工作量。请注意:编译器在汇编级别也不会将没有分支的代码转换为分支。因为分支也有一个缺点:如果最终仍需要使用模操作,那么您浪费了一些时间。

在不知道 idx < idx_max 相对频率的情况下,无法进行合理的优化决策。因此,编译器(gcc 和 clang 做的一样)选择以相对透明的方式映射代码,将此选择交给开发人员处理。

因此,该分支可能是一个非常合理的选择。

第二个分支应该完全没有意义,因为比较和赋值的代价是相当的。尽管如此,您可以在链接中看到,如果编译器具有对变量的引用,它们仍将不执行此优化。如果值是局部变量(就像您演示的代码中那样),则编译器将优化该分支。

总之,第一段代码可能是一个合理的优化,而第二段代码可能只是一个疲惫的程序员。


2
@NirFriedman,您的回答比我想象的还要清晰明了。再次感谢您的时间。 - kyb
2
请注意,您更改了原始帖子的含义,因此可能会添加错误。原始问题使用“unsigned”,而您使用了“signed int”,因此div和div2是不同的函数:负数会产生不同的结果。 - Giacomo Catenazzi
@GiacomoCatenazzi 没错,说得好,将类型更改为无符号并不会在汇编方面有任何重大影响。 - Nir Friedman
1
好的。谢谢。 - Kyle Strand
1
@CodyGray 实际上有几十甚至几百行代码可以进行比较。从这个答案中得出的算术结果:https://dev59.com/iWgu5IYBdhLWcg3wkH6P 表明,完美预测和随机(50-50)预测之间存在大约7.5个周期的差异(即错失15个周期)。对于我见过的每种架构,整数除法的成本都显著高于15个周期。 - Nir Friedman
显示剩余12条评论

6
有一些情况,写入已经拥有的值可能比读取变量、发现它已经拥有所需值并跳过写操作更慢。一些系统具有处理器缓存,将所有写请求立即发送到内存中。虽然这样的设计在今天并不普遍,但它们曾经很常见,因为它们可以提供完全读/写缓存所能提供的性能提升的大部分,但成本只是全部缓存的一小部分。
类似上面的代码也可能适用于某些多CPU的情况。最常见的情况是,运行在两个或更多CPU核心上的代码将重复命中变量。在具有强内存模型的多核缓存系统中,想要写入变量的核心必须首先与其他核心协商,以获取包含它的缓存行的独占所有权,并且下次任何其他核心想要读取或写入它时,必须再次进行协商才能放弃此类控制。这样的操作很容易非常昂贵,而且即使每次写入只是存储存储已经拥有的值,成本也必须承担。然而,如果位置变为零并且永远不会再次写入,则两个核心都可以同时持有缓存行以进行非独占只读访问,并且永远不必��次协商它。
在几乎所有多CPU可能命中变量的情况下,变量至少应被声明为volatile。唯��的例外情况,可能适用于这里的情况是,在main()开始后发生的对变量的所有写操作将存��相同的值,并且无论一个CPU的任何存储是否在另一个CPU中可见,代码都会正确运行。如果多次执行某些操作会很浪费但并没有什么害处,并且变量的目的是表示是否需要执行此操作,则很多实现可以生成比使用volatile限定符更好的代码,前提是它们不尝试通过使写操作无条件来提高效率。
顺便说一句,如果通过指针访问该对象,上述代码可能有另一个可能的原因:如果函数设计为接受const对象(其中某个字段为零),或非const对象(该对象应将该字段设置为零),则可能需要类似上述的代码才能确保两种情况下均具有定义行为。

然后还有装载链接条件存储,与比较交换不同的是,在“无用”的写入后会失败。 - Ben Voigt
如果硬件连接到内存地址,则“volatile”限定符通常需要与除指针转换常量之外的任何lvalue一起使用,以获得有用的语义(尽管标准可能允许实现假设在缺少“volatile”限定符的情况下可以合并对“(*(uint32_t *)0xF0001208)”的操作,但足够多的硬件供应商在其头文件中省略了“volatile”限定符,因此这样的“优化”在大多数情况下都应该被认为是不明智的默认选择)。 - supercat
同意,除非volatile生效,否则“无用”的写操作可能不会真正发生。 - Ben Voigt
2
在几乎所有多个CPU可能会访问变量的情况下,该变量应至少被声明为volatile。我认为这是完全错误的:只有当该变量可以被非C++进程写入时才应使用volatile。 - Nir Friedman
关于编译器的假设,不去争论它是否不幸,现实是它们确实对未定义行为进行疯狂的优化,因此告诉人们去做可能导致未定义行为的事情(比如,在多线程情况下尝试使用 volatile)并不是一个好建议。 - Nir Friedman
显示剩余10条评论

2

关于第一个代码块:这是基于Chandler Carruth对Clang的建议进行微优化(更多信息请参见此处),但是它不一定以这种形式(使用if而不是三元运算符)或在任何给定编译器上都是有效的微优化。

取模是一项相当昂贵的操作,如果代码经常执行并且有强烈的统计倾向于条件的一侧,CPU的分支预测(在现代CPU上)将显着降低分支指令的成本。


1

在我的看法中,使用if语句似乎不是一个好主意。

你是正确的。无论 idx >= idx_max 是否成立,在执行 idx %= idx_max 后,它都将小于 idx_max。如果 idx < idx_max,那么无论是否跟随if语句,它都不会改变。

虽然你可能认为绕过取模运算可以节省时间,但我想说的是,当分支被执行时,现代CPU的流水线必须重置,这会花费相对较多的时间。最好不要执行分支,而是执行整数除法,其花费的时间大致相同。

编辑:事实证明,与分支相比,取模运算相当缓慢,正如其他人在此处建议的那样。以下是一位研究这个问题的人的讲解: CppCon 2015: Chandler Carruth "Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!"(在另一个SO问题的链接中建议)。

这个人编写编译器,认为去掉分支会更快;但是他的基准测试证明他错了。即使只有20%的情况需要分支,加入分支也能提高速度。
不使用if的另一个原因:少一行要维护的代码,别人也不用费力思考它的含义。上面链接中的人实际上创建了一个“更快的模数”宏。在我看来,对于性能关键型应用程序,这种方式或内联函数是最好的选择,因为没有分支会使你的代码更易懂,但执行速度很快。
最后,上面视频中的人计划将此优化通知编译器编写者。因此,如果代码中没有加入if,它们可能会为你添加if。因此,当这种情况发生时,仅mod就可以了。

然而,缓存争用可能比流水线刷新更加昂贵。 - Ben Voigt
一个整数取模运算,其中两个输入都不是在编译时已知的,代价非常昂贵。像往常一样,这取决于具体的架构,但它可能超过100个周期。我很难相信一个简单的分支会如此昂贵。 - Nir Friedman
@NirFriedman 它可能超过100个周期,但根据Intel的说法,这需要Silvermont微架构上的64位值(38-123个周期延迟)。Goldmont微架构上的32位值是12-25个周期延迟(而32位的Silvermont只有26-38个周期)。我认为这很容易在分支错误预测范围内。至于Arm,我不清楚。 - Martin Bonner supports Monica
@MartinBonner 这是一个很好的观点,感谢您澄清(我没有很好地阅读一些表格),但是a)整数除法的平均值仍然要高得多,b)您希望分支预测器至少赢得一半的时间,对吧?你会希望的;-)。我也不确定对于超短分支,您是否需要支付全部惩罚。毕竟,仅有一行之后的所有后续代码都是相同的。总体而言,我认为这种情况可能需要精心制作的微基准测试。 - Nir Friedman
分支预测器每次都可能出错,但实际上“大约一半”是最坏情况。短分支失误的问题在于不仅需要撤销单个错误指令,还需要撤销几条已经开始执行的指令。可以参考经典的“为什么处理排序向量更快”的答案。 - Martin Bonner supports Monica
@MartinBonner 有趣的是,我从那个问题中进行了算术运算,并得出结论,排序后的数据每次迭代大约比未排序的数据快3纳秒。将时钟速度乘以2.5 GHz,我们可以得出完美预测与随机预测之间相差大约7.5个时钟周期,或者说一个缺失值大约相当于15个时钟周期。至少在某些体系结构上,它肯定比我想象的要接近。我可能需要运行这个微基准测试并更新我的答案。 - Nir Friedman

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接