具体来说,如果我有一系列if
...else 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
语句可以任意重新排序,而对程序的行为没有任何其他影响。在我的回答中,这三个条件测试是互斥的,不会产生副作用。当然,如果必须以某种顺序对语句进行评估才能实现某些所需的行为,那么效率问题就不那么重要了。
通常,大多数(如果不是全部)英特尔CPU都假定在第一次看到前向分支时就不会采用它们。参见Godbolt的作品。
之后,分支进入分支预测缓存,并且过去的行为用于通知将来的分支预测。
因此,在一个紧密的循环中,错误排序的影响将相对较小。分支预测器将要学习哪一组分支最有可能,如果循环中的工作量非常少,那么细小的差别就不会太多。
在一般代码中,默认情况下(出于另一个原因)大多数编译器将按与在代码中对其排序的方式大致相同的顺序对生成的机器代码进行排序。因此,if语句在失败时是前向分支。
因此,您应该按照降低可能性的顺序对分支进行排序,以便从“首次相遇”中获得最佳的分支预测。
在一组条件下紧密循环多次并完成琐碎工作的微基准测试将主要受指令数量等的微小影响所支配,而很少涉及相对分支预测问题。因此,在这种情况下,您必须进行剖析,因为经验法则是不可靠的。
最重要的是,矢量化和许多其他优化适用于微小的紧密循环。
因此,在一般代码中,将最可能的代码放入if
块中,这将导致最少的未缓存分支预测未命中。在紧密的循环中,请遵循一般规则开始,如果您需要了解更多信息,除了进行概要分析之外别无选择。
当然,如果某些测试比其他测试便宜得多,那么所有这些都会消失。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句