订购if ... else if语句的概率有什么影响？ [英] What is the effect of ordering if...else if statements by probability?

问题描述

具体来说，如果我有一系列如果 ... 否则如果语句，我事先知道每个语句将评估为 true 的相对概率，它按概率顺序对它们进行排序的执行时间有多大差异？例如，我应该更喜欢这个：

Specifically, if I have a series of if...else if statements, and I somehow know beforehand the relative probability that each statement will evaluate to true, how much difference in execution time does it make to sort them in order of probability? For example, should I prefer this:

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在分支预测方面的表现如何。

It seems obvious that the sorted version would be faster, however for readability or the existence of side-effects, we might want to order them non-optimally. It's also hard to tell how well the CPU will do with branch prediction until you actually run the code.

因此，在试验过程中，我最终回答了问题。关于特定案例的我自己的问题，但是我也希望听到其他意见/见解。

So, in the course of experimenting with this, I ended up answering my own question for a specific case, however I'd like to hear other opinions/insights as well.

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

Important: this question assumes that the if statements can be arbitrarily reordered without having any other effects on the behavior of the program. In my answer, the three conditional tests are mutually exclusive and produce no side effects. Certainly, if the statements must be evaluated in a certain order to achieve some desired behavior, then the issue of efficiency is moot.

推荐答案

作为一般规则，大多数（如果不是所有）英特尔CPU都假设前向分支不会在他们第一次看到它们时采用。请参阅 Godbolt的工作。

As a general rule, most if not all Intel CPUs assume forward branches are not taken the first time they see them. See Godbolt's work.

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

After that, the branch goes into a branch prediction cache, and past behavior is used to inform future branch prediction.

因此，在紧密的循环中，错误的影响正在进行相对较小。分支预测器将学习哪一组分支最有可能，如果你在循环中有非常重要的工作量，那么小的差异就不会增加太多。

So in a tight loop, the effect of misordering is going to be relatively small. The branch predictor is going to learn which set of branches is most likely, and if you have non-trivial amount of work in the loop the small differences won't add up much.

在一般代码中，默认情况下大多数编译器（缺少其他原因）将按照您在代码中订购的方式大致订购生产的机器代码。因此，如果语句在失败时是前向分支。

In general code, most compilers by default (lacking another reason) will order the produced machine code roughly the way you ordered it in your code. Thus if statements are forward branches when they fail.

因此，您应该按照从第一次遇到获得最佳分支预测的可能性降低的顺序对您的分支进行排序。

So you should order your branches in the order of decreasing likelihood to get the best branch prediction from a "first encounter".

微基准测试在一系列条件下多次循环，并且微不足道的工作将受到指令数量等微小影响的支配，而且很少相对分支预测问题。因此，在这种情况下，必须配置文件，因为经验法则不可靠。

A microbenchmark that loops tightly many times over a set of conditions and does trivial work is going to dominated by tiny effects of instruction count and the like, and little in the way of relative branch prediction issues. So in this case you must profile, as rules of thumb won't be reliable.

除此之外，矢量化和许多其他优化适用于微小的紧密循环。

On top of that, vectorization and many other optimizations apply to tiny tight loops.

所以在一般代码中，如果块，将最可能的代码放在中，并且将导致最少的未缓存分支预测未命中。在紧密循环中，按照一般规则开始，如果您需要了解更多，除了简介之外别无选择。

So in general code, put most likely code within the if block, and that will result in the fewest un-cached branch prediction misses. In tight loops, follow the general rule to start, and if you need to know more you have little choice but to profile.

如果有些测试比其他测试便宜得多，那么这一切都会消失。

Naturally this all goes out the window if some tests are far cheaper than others.

这篇关于订购if ... else if语句的概率有什么影响？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！