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

Question

具体来说，如果我有一系列 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 语句可以任意重新排序，而不会对程序的行为产生任何其他影响。在我的回答中，三个条件测试是互斥的，不会产生副作用。当然，如果必须按特定顺序评估语句以实现某些期望的行为，那么效率问题就没有实际意义。

原文由 Carlton 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

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

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

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

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

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

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

原文由 Yakk - Adam Nevraumont 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我做了以下测试来计时两个不同的 if … else if 块的执行，一个按概率顺序排序，另一个按相反顺序排序：

 #include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    long long sortedTime = 0;
    long long reverseTime = 0;

    for (int n = 0; n != 500; ++n)
    {
        //Generate a vector of 5000 random integers from 1 to 100
        random_device rnd_device;
        mt19937 rnd_engine(rnd_device());
        uniform_int_distribution<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> start, end;

        //Sort the conditional statements in order of increasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 95) ++nHigh;               //Least likely branch
            else if (i < 20) ++nLow;
            else if (i >= 20 && i < 95) ++nMid; //Most likely branch
        }
        end = chrono::high_resolution_clock::now();
        reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

        //Sort the conditional statements in order of decreasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 20 && i < 95) ++nMid;  //Most likely branch
            else if (i < 20) ++nLow;
            else if (i >= 95) ++nHigh;      //Least likely branch
        }
        end = chrono::high_resolution_clock::now();
        sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

将 MSVC2017 与 /O2 结合使用，结果显示排序后的版本始终比未排序的版本快约 28%。根据 luk32 的评论，我还切换了两个测试的顺序，这产生了明显的差异（22% 对 28%）。该代码在 Intel Xeon E5-2697 v2 上的 Windows 7 下运行。当然，这是非常具体的问题，不应被解释为结论性的答案。

原文由 Carlton 发布，翻译遵循 CC BY-SA 3.0 许可协议