如果。。。否则，是否按概率进行陈述？

Question

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

Answer 1

不，您不应该这样做，除非您确实确定目标系统受到影响。默认情况下，按可读性进行。

我非常怀疑你的结果。我对您的示例进行了一些修改，因此反转执行更容易。Ideone相当一致地表明，倒序速度更快，但并不多。在某些跑步中，甚至偶尔也会出现这种情况。我想说，结果是不确定的。科里鲁也没有报告真正的区别。稍后，我可以检查odroid xu4上的Exynos5422 CPU。

问题是，现代CPU有分支预测器。有很多逻辑专门用于预取数据和指令，而现代x86 CPU在这方面相当智能。一些更轻薄的架构（如ARMs或GPU）可能容易受到此影响。但它实际上高度依赖于编译器和目标系统。

我想说的是，分支排序优化是非常脆弱和短暂的。只作为一些真正的微调步骤。

代码：

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

using namespace std;

int main()
{
    //Generate a vector of 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;

    //Count the number of values in each of three different ranges
    //Run the test a few times
    for (int n = 0; n != 10; ++n) {

        //Run the test again, but now sort the conditional statements in reverse-order of likelyhood
        {
          nLow = nMid = nHigh = 0;
          auto 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
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }

        {
          //Sort the conditional statements in order of likelyhood
          nLow = nMid = nHigh = 0;
          auto 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
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}

Answer 2

我做了以下测试来计时两个不同的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%）。该代码在英特尔至强E5-2697 v2的Windows 7下运行。当然，这是非常特定于问题的，不应被解释为结论性答案。

Answer 3

一般来说，大多数（如果不是所有的话）英特尔CPU都会假定在第一次看到前向分支时不会执行前向分支。参见Godbolt的作品。

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

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

在一般代码中，大多数编译器在默认情况下（没有其他原因）会按照您在代码中的排序方式大致排序生成的机器代码。因此，if语句在失败时是转发分支。

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

在一组条件上紧密循环多次并做琐碎工作的微基准将被指令计数等的微小影响所主导，并且几乎没有相对分支预测问题。因此在这种情况下，您必须分析，因为经验法则不可靠。

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

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

当然，如果一些html" target="_blank">测试比其他测试便宜得多，这一切都会被抛诸脑后。