小编典典

按概率排序 if...else if 语句有什么影响?

all

具体来说,如果我有一系列ifelse if语句,并且我事先知道每个语句将评估为的相对概率,true那么按概率顺序对它们进行排序会在执行时间上有多大差异?例如,我应该更喜欢这个:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

对此?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

很明显,排序后的版本会更快,但是为了可读性或副作用的存在,我们可能希望对它们进行非最优排序。在您实际运行代码之前,也很难判断 CPU
在分支预测方面的表现如何。

因此,在对此进行试验的过程中,我最终针对特定案例回答了我自己的问题,但是我也想听听其他意见/见解。

重要提示:这个问题假设if语句可以任意重新排序,而不会对程序的行为产生任何其他影响。在我的回答中,三个条件测试是互斥的,不会产生副作用。当然,如果必须按特定顺序评估语句以实现某些期望的行为,那么效率问题就没有实际意义。


阅读 76

收藏
2022-07-12

共1个答案

小编典典

作为一般规则,大多数(如果不是全部)英特尔 CPU 都假定在第一次看到前向分支时不会采用它们。参见Godbolt
的作品

之后,分支进入分支预测缓存,过去的行为用于通知未来的分支预测。

所以在一个紧密的循环中,错误排序的影响会相对较小。分支预测器将了解哪组分支最有可能,如果您在循环中有大量工作,那么微小的差异不会加起来太多。

在一般代码中,大多数编译器默认情况下(缺少另一个原因)将大致按照您在代码中对其进行排序的方式对生成的机器代码进行排序。因此,如果语句在失败时是前向分支。

因此,您应该按照可能性递减的顺序对分支进行排序,以便从“第一次遇到”中获得最佳分支预测。

一个在一组条件下紧密循环多次并完成微不足道的工作的微基准测试将受到指令数等微小影响的支配,而在相关分支预测问题方面几乎没有影响。因此,在这种情况下,您
必须 profile ,因为经验法则不可靠。

最重要的是,矢量化和许多其他优化适用于微小的紧密循环。

因此,在一般代码中,将最可能的代码放在if块中,这将导致最少的未缓存分支预测未命中。在紧凑的循环中,遵循一般规则开始,如果您需要了解更多信息,您别无选择,只能进行概要分析。

当然,如果某些测试比其他测试便宜得多,这一切都会消失。

2022-07-12