如果按照概率排序if...else if语句会产生什么影响？

Question

具体而言，如果我有一系列的if...else if语句，并且我事先知道每个语句相对于其它语句被执行的概率，那么按照概率排序在执行时间上会有多大差异？例如，我应该更喜欢这样吗：

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

---

你可能想要添加一条注释，说明这些条件是互斥的，否则这两个版本就不等价了。 - 463035818_is_not_a_number

有趣的是，一道自问自答的问题在一个小时内得到了20多个赞，而答案质量却相对较差。不是在指责提问者，但点赞者应当注意跟风。这个问题可能很有趣，但结果值得怀疑。 - luk32

我认为这可以被描述为一种“短路计算”，因为命中一个比较将否定其他比较。当一个快速的比较（例如布尔运算）可以防止我进入一个可能涉及资源密集型字符串操作、正则表达式或数据库交互的不同比较时，我个人更喜欢采用这样的实现方式。 - MonkeyZeus

有些编译器可以收集分支统计信息，并将其反馈回编译器，以使其能够进行更好的优化。 - user1084944

如果您关注性能问题，建议使用“性能指导优化”（Profile Guided Optimization），并将手动调试的结果与编译器生成的结果进行比较。 - Justin

Answer 1

作为一般规则，如果不是全部，那么大多数英特尔CPU都假定在第一次看到它们时，前向分支不被采取。请参阅 Godbolt的工作。

之后，分支会进入一个分支预测缓存中，并使用过去的行为来指导未来的分支预测。

因此，在紧密循环中，错序的效果将相对较小。分支预测器将学习哪一组分支最有可能出现，如果您在循环中有非微不足道的工作量，则小差异不会累积太多。

在一般代码中，大多数编译器默认情况下（缺少其他原因）会将生成的机器代码按照您在代码中指定的顺序粗略排序。因此，如果语句失败，则if语句是前向分支。

因此，您应该按照减少可能性的顺序排列分支，以从“第一次遇见”获得最佳分支预测。

在一个微型基准测试中，它紧密地循环许多次以满足一组条件并进行微不足道的工作，这将由指令计数等微小效果所主导，并且相对分支预测问题很少。因此，在这种情况下，您必须进行性能分析，因为经验法则可能不可靠。

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

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

当然，如果某些测试比其他测试便宜得多，则所有这些都将被抛到一边。

- Yakk - Adam Nevraumont

---

值得考虑的是测试本身的成本：如果某个测试只比另一个测试略微更有用，但成本却高了很多，那么最好先进行另一个测试，因为不进行昂贵的测试所节省下来的费用可能会超过从分支预测中节省下来的费用等其他方面的节约。 - psmears

你提供的链接并不支持你的结论“一般情况下，大多数英特尔CPU假定前向分支在第一次看到它们时不会被执行”。事实上，这只对相对较为晦涩的Arrendale CPU成立，而该链接中展示的结果也是针对该CPU的。主流的Ivy Bridge和Haswell的结果则完全不支持该结论。Haswell对于未见过的分支非常接近“总是预测跳过”，而Ivy Bridge则不太清楚。 - BeeOnRope

通常认为，CPU不再像过去那样使用静态预测。事实上，现代的英特尔可能正在使用类似于概率TAGE预测器的东西。您只需将分支历史记录哈希到各种历史记录表中，并选择与最长历史记录匹配的表。它使用“标记”来尝试避免别名，但标记只有几位。如果您在所有历史长度上都错过了，可能会进行一些默认预测，这并不一定取决于分支方向（在Haswell上，我们可以明确地说它不是）。 - BeeOnRope

Answer 2

我设计了以下测试来计时执行两个不同的 if...else if 代码块，一个按概率排序，另一个按相反顺序排序:

我设计了以下测试来比较两个不同的 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;
}

使用带有/O2选项的MSVC2017，结果显示排序版本的速度始终比未排序版本快约28%。根据luk32的评论，我还交换了两个测试的顺序，这会产生明显的差异（22% vs 28%）。该代码在装有Intel Xeon E5-2697 v2的Windows 7下运行。当然，这非常依赖于具体问题，不能解释为最终答案。

- Carlton

---

OP应该小心，因为更改if...else if语句可能会对代码中的逻辑流程产生重大影响。unlikely检查可能不经常出现，但在检查其他条件之前先检查unlikely条件可能是业务需求。 - Luke T Brooks

30%更快？你的意思是它不需要执行大约这么多额外的if语句，速度就会快30％吗？这似乎是一个相当合理的结果。 - UKMonkey

你是如何对其进行基准测试的？使用了哪个编译器、CPU等等？我很确定这个结果不具备可移植性。 - luk32

这个微基准测试的问题在于当你反复循环时，CPU会计算出哪个分支最有可能并将其缓存。如果这些分支没有在一个小而紧密的循环中被检查，分支预测缓存可能没有它们，如果CPU猜错了且没有分支预测缓存指导，则成本可能会高得多。 - Yakk - Adam Nevraumont

这个基准测试并不太可靠。使用gcc 6.3.0编译：g++ -O2 -march=native -std=c++14 确实会给排序后的条件语句带来轻微的优势，但大多数情况下，两次运行之间的百分比差异约为5%。有几次它实际上更慢了（由于方差）。我相当确定按照这种方式排序 if 条件语句不值得担心；PGO 可能会完全处理任何此类情况。 - Justin

Answer 3

只是我的五分钱。 看起来if语句的排序效果应该取决于以下因素：

1. 每个if语句的概率。

2. 迭代次数，以便分支预测器发挥作用。

3. 可能/不可能的编译提示，即代码布局。

为了探索这些因素，我对以下函数进行了基准测试：

ordered_ifs()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] < check_point) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] == check_point) // very unlikely
        s += 1;
}

reversed_ifs()

反转if语句

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] == check_point) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] < check_point) // highly likely
        s += 3;
}

带提示的有序if语句()

for (i = 0; i < data_sz * 1024; i++) {
    if (likely(data[i] < check_point)) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
}

带提示的反转if语句()

for (i = 0; i < data_sz * 1024; i++) {
    if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (likely(data[i] < check_point)) // highly likely
        s += 3;
}

数据

数据数组包含0到100之间的随机数:

const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];

static void data_init(int data_sz)
{
    int i;
        srand(0);
    for (i = 0; i < data_sz * 1024; i++)
        data[i] = rand() % RANGE_MAX;
}

结果

以下结果是基于 Intel i5 @3.2 GHz 和 G++ 6.3.0。第一个参数是 check_point（即高度可能的 if 语句的百分比），第二个参数是 data_sz（即迭代次数）。

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/75/4                    4326 ns       4325 ns     162613
ordered_ifs/75/8                   18242 ns      18242 ns      37931
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612
reversed_ifs/50/4                   5342 ns       5341 ns     126800
reversed_ifs/50/8                  26050 ns      26050 ns      26894
reversed_ifs/75/4                   3616 ns       3616 ns     193130
reversed_ifs/75/8                  15697 ns      15696 ns      44618
reversed_ifs/100/4                  3738 ns       3738 ns     188087
reversed_ifs/100/8                  7476 ns       7476 ns      93752
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/75/4         3165 ns       3165 ns     218492
ordered_ifs_with_hints/75/8        13785 ns      13785 ns      50574
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205
reversed_ifs_with_hints/50/4        6573 ns       6572 ns     105629
reversed_ifs_with_hints/50/8       27351 ns      27351 ns      25568
reversed_ifs_with_hints/75/4        3537 ns       3537 ns     197470
reversed_ifs_with_hints/75/8       16130 ns      16130 ns      43279
reversed_ifs_with_hints/100/4       3737 ns       3737 ns     187583
reversed_ifs_with_hints/100/8       7446 ns       7446 ns      93782

分析

1. 顺序很重要

针对4K次迭代和(几乎)100%的高喜欢语句概率，差异巨大，达到223%：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

对于4K次迭代和50%的高度喜欢语句的概率，差异约为14％：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. 迭代次数很重要

在（几乎）100%的高度喜欢语句的概率下，4K和8K迭代之间的差异大约是两倍（正如预期的那样）：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

但是，在高度喜欢的陈述有50%概率时，4K和8K迭代之间的差异是5.5倍：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

为什么会这样呢？因为分支预测错误。以下是每种情况下的分支预测错误次数：

ordered_ifs/100/4    0.01% of branch-misses
ordered_ifs/100/8    0.01% of branch-misses
ordered_ifs/50/4     3.18% of branch-misses
ordered_ifs/50/8     15.22% of branch-misses

在我的i5上，分支预测对于不太可能的分支和大数据集表现失常。

3. 提示有所帮助

对于4K次迭代，50％概率的结果略微变差，接近100％概率的结果略微改善：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687

但是对于8000次迭代，结果总是稍微好一些：

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/100/8                   3381 ns       3381 ns     207612
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205

所以，这些提示也是有帮助的，但仅仅是一点点。

总结就是：始终要对代码进行基准测试，因为结果可能会出乎意料。

希望有所帮助。

- Andriy Berestovskyy

---

i5 Nehalem？i5 Skylake？仅仅说“i5”并不是很具体。此外，我假设您使用了g++ -O2或-O3 -fno-tree-vectorize，但您应该明确说明。 - Peter Cordes

有趣的是，对于有序和反转的 with_hints 仍然不同。如果您在某个地方链接到源代码会很好。（例如，一个Godbolt链接，最好是完整链接，这样链接缩短就不会失效。） - Peter Cordes

分支预测器能够在4K输入数据大小下进行良好的预测，即能够通过记住循环中跨度为数千的分支结果来“打破”基准测试，这证明了现代分支预测器的强大。请记住，在某些情况下，预测器对齐方式非常敏感，因此很难对某些更改得出强有力的结论。例如，您注意到不同情况下提示的行为相反，但这可能是由于提示随机更改了代码布局，从而影响了预测器。 - BeeOnRope

@PeterCordes 我的主要观点是，虽然我们可以尝试预测变化的结果，但在变化之前和之后最好还是测量性能... 而且你是对的，我应该提到它是使用 -O3 进行优化的，并且处理器是 i5-4460 @ 3.20GHz。 - Andriy Berestovskyy

Answer 4

除非您确信目标系统受到影响，否则不应该这样做。默认情况下，请以可读性为准。

我非常怀疑您的结果。我稍微修改了您的示例，以便更容易地反转执行。 Ideone 显示反向顺序通常更快，但差别不大。在某些运行中，甚至会偶尔翻转。我认为结果并不确定。coliru 也没有报告任何实际差异。我稍后可以在我的 odroid xu4 上检查 Exynos5422 CPU。

问题在于现代 CPU 具有分支预测器。有很多逻辑专门用于预取数据和指令，而现代 x86 CPU 在这方面相当聪明。一些较轻的架构，如 ARM 或 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;
    }
}

- luk32

---

当我交换排序和反向排序的if块的顺序时，我得到了与您的代码中相同的约30％的性能差异。我不确定为什么Ideone和coliru没有显示任何差异。 - Carlton

当然很有趣。我会尝试获取其他系统的一些数据，但可能需要一天时间来玩弄它。这个问题很有趣，特别是考虑到你的结果，但它们如此惊人，我不得不进行交叉检查。 - luk32

如果问题是“影响是什么？”，答案不能是“没有”！ - PJTraill

是的。但我没有收到有关原始问题更新的通知。它使答案制定过时了。抱歉。稍后我会编辑内容，指出它回答了原始问题并展示了一些证明原始观点的结果。 - luk32

这值得重复强调：“默认情况下，以可读性为准。”编写易读的代码通常比试图通过使代码难以解析来获得微小的性能提升（在绝对意义上）更容易取得更好的结果。 - Andrew Brēza

Answer 5

根据这里的其他答案，看起来唯一真正的答案是：取决于情况。至少以下几点会影响结果（重要性的顺序不一定如下）：

• 每个分支的相对概率。 这是最初提出的问题。 根据现有答案，似乎在某些条件下按概率排序有所帮助，但并非总是如此。 如果相对概率差异不大，则它们的排列顺序可能没有任何区别。 但是，如果第一个条件99.999％的时间都发生，并且下一个条件是剩余时间的一小部分，则我认为将最可能的条件放在第一位在时间上会更有利。
• 计算每个分支的真/假条件的成本。 如果测试条件的时间成本对某个分支而言比其他分支高得多，则这可能会对时序和效率产生重大影响。例如，考虑需要1个时间单位计算的条件（例如检查布尔变量的状态），与需要数十、数百、数千甚至数百万个时间单位计算的条件（例如检查磁盘上文件的内容或针对大型数据库执行复杂的SQL查询）。 假设代码每次按顺序检查条件，则应该首先检查更快的条件（除非它们依赖于其他条件先失败）。
• 编译器/解释器 某些编译器（或解释器）可能包括各种优化，可以影响性能（其中一些仅在编译和/或执行期间选择某些选项时才存在）。 因此，除非您在同一系统上使用完全相同的编译器基于相同代码进行两次编译和执行，唯一不同之处是所讨论的分支的顺序，否则您必须对编译器差异给予一定的容差。
• 操作系统 / 硬件 如luk32和Yakk所述，各种CPU具有自己的优化（操作系统也是如此）。 因此，基准测试在这里也会受到变化的影响。
• 代码块执行频率 如果包含分支的代码块很少被访问（例如在启动期间仅一次），那么放置分支的顺序可能无关紧要。另一方面，如果你的代码在关键部分频繁地执行该代码块，那么顺序可能很重要（取决于基准测试结果）。

唯一确定的方法是对你特定的情况进行基准测试，最好在与最终运行代码的系统相同或非常相似的系统上进行。如果它打算在多个不同硬件、操作系统等变化的系统上运行，那么最好在多个变化中进行基准测试，以确定哪个是最佳的。甚至可以考虑在一个类型的系统上用一种顺序编译代码，在另一个类型的系统上用另一种顺序编译代码。

在没有基准测试的情况下，我的个人经验法则是按照以下顺序排序：

1. 依赖先前条件结果的条件，
2. 计算条件的成本，然后
3. 每个分支的相对概率。

- Ampersat

Answer 6

通常我看到的高性能代码解决方案是保持最易读的顺序，但提供给编译器一些提示。以下是来自Linux内核的一个例子：

if (likely(access_ok(VERIFY_READ, from, n))) {
    kasan_check_write(to, n);
    res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
    memset(to + (n - res), 0, res);

这里的假设是访问检查将会通过，而且没有在res中返回任何错误。试图重新排列这些if语句中的任意一个都会使代码变得混乱，但是likely()和unlikely()宏实际上通过指出什么是正常情况和异常情况来帮助可读性。

这些宏的Linux实现使用GCC特定特征。似乎clang和Intel C编译器支持相同的语法，但MSVC没有这样的特性。

- jpa

---

如果您能解释一下likely()和unlikely()宏的定义，并包括相关编译器功能的一些信息，那将更有帮助。请注意，翻译后的内容应保持与原文相同的含义，通俗易懂即可，不需要添加解释或其他内容。 - Nate Eldredge

据我所知，这些提示仅会改变代码块的内存布局以及是否跳转。这可能具有性能优势，例如需要（或不需要）读取内存页面。但这不会重新排列长列表中else-if条件的评估顺序。 - Hagen von Eitzen

@HagenvonEitzen 嗯，是的，这是一个很好的观点。如果编译器不足够聪明以知道条件是互斥的，那么它不能影响else if的顺序。 - jpa

Answer 7

还取决于您使用的编译器和编译平台。

理论上，最可能的情况应该使控制尽可能少地跳转。

通常，最可能的情况应该放在第一位：

if (most_likely) {
     // most likely instructions
} else …

最常见的汇编语言是基于条件分支，即当条件为真时跳转。以下是该 C 代码可能被转换成的伪汇编代码：

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…

这是因为跳转会使CPU取消执行流水线并停滞，因为程序计数器发生了变化（对于支持流水线的架构非常普遍）。 然后是关于编译器的问题，它可能会或可能不会应用一些复杂的优化来使得控制条件的统计最有可能的情况尽可能少地跳跃。

- NoImaginationGuy

---

你说条件分支发生在条件为真时，但“伪汇编”示例显示相反的情况。此外，不能说条件跳转（更不用说所有跳转）会阻塞流水线，因为现代CPU通常具有分支预测功能。实际上，如果分支被预测为被采取，但最终未被采取，则流水线将被阻塞。我仍然会尝试按概率降序排列条件，但编译器和CPU对此的处理方式高度依赖于具体实现。 - Arne Vogel

我写成了“not(most_likely)”这样，如果most_likely是true，控制流就会继续执行而不跳出。 - NoImaginationGuy

“最受欢迎的汇编语言基于条件分支，当条件为真时跳转”...那会是哪些ISA呢？这显然不适用于x86和ARM。对于基本的ARM CPU（以及非常古老的x86 CPU），即使对于复杂的bps，它们通常仍然假定前向分支不被采取，而后向分支总是被采取，因此相反的说法是正确的。 - Voo

我尝试过的编译器（https://godbolt.org/g/oVCKe8）大多都使用了我上面提到的简单测试方法。请注意，`clang`实际上对于`test2`和`test3`采用了不同的方法：由于启发式算法表明`<0或==0测试很可能是错误的，它决定在两个路径上克隆函数的其余部分，因此它能够使condition == false成为默认路径。这只有在函数的其余部分很短的情况下才可行：在test4`中，我添加了一个操作，它又回到了我上面概述的方法。 - BeeOnRope

@ArneVogel - 正确预测的分支不会完全阻塞现代CPU的流水线，但它们通常仍然比未被采取的分支差得多：(1)它们意味着控制流不连续，所以jmp之后的指令都是无用的，因此浪费了获取/解码带宽。(2)即使有预测，现代大核心每个周期只执行一次获取，因此它将硬性限制为每个周期1个已采取的分支（另一方面，现代英特尔可以每个周期执行2个未采取的分支）(3)对于已采取的连续分支，分支预测更难处理，在快速+慢速预测器的情况下... - BeeOnRope

Answer 8

我决定在自己的机器上使用Lik32代码重新运行测试。由于我的Windows或编译器认为高分辨率是1毫秒，所以我不得不对其进行更改，使用mingw32-g++.exe -O3 -Wall -std=c++11 -fexceptions -g。

vector<int> rand_vec(10000000);

GCC对原始代码进行了相同的转换。

请注意，只有前两个条件被测试，因为第三个条件必须始终为真，GCC在这里就像夏洛克一样。

反转

.L233:
        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L219
.L293:
        mov     edx, DWORD PTR [rsp+104]
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
.L217:
        add     rax, 4
        cmp     r14, rax
        je      .L292
.L219:
        mov     edx, DWORD PTR [rax]
        cmp     edx, 94
        jg      .L293 // >= 95
        cmp     edx, 19
        jg      .L218 // >= 20
        mov     edx, DWORD PTR [rsp+96]
        add     rax, 4
        add     edx, 1 // < 20 Sherlock
        mov     DWORD PTR [rsp+96], edx
        cmp     r14, rax
        jne     .L219
.L292:
        call    std::chrono::_V2::system_clock::now()

.L218: // further down
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
        jmp     .L217

And sorted

        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L226
.L296:
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
.L224:
        add     rax, 4
        cmp     r14, rax
        je      .L295
.L226:
        mov     edx, DWORD PTR [rax]
        lea     ecx, [rdx-20]
        cmp     ecx, 74
        jbe     .L296
        cmp     edx, 19
        jle     .L297
        mov     edx, DWORD PTR [rsp+104]
        add     rax, 4
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
        cmp     r14, rax
        jne     .L226
.L295:
        call    std::chrono::_V2::system_clock::now()

.L297: // further down
        mov     edx, DWORD PTR [rsp+96]
        add     edx, 1
        mov     DWORD PTR [rsp+96], edx
        jmp     .L224

因此，这并没有告诉我们太多信息，除了最后一个案例不需要分支预测。

现在，我尝试了所有6种if的组合，前两个是原始的reverse和sorted。高值是>=95，低值是<20，中间值是20-94，每个循环迭代10000000次。

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

1900020, 7498968, 601012

Process returned 0 (0x0)   execution time : 2.899 s
Press any key to continue.

为什么顺序是高、低、中，然后才是更快的（略微）？

因为最不可预测的是最后一个，因此永远不会通过分支预测器运行。

          if (i >= 95) ++nHigh;               // most predictable with 94% taken
          else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
          else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.

因此，这些分支将被预测为“taken”、“taken”和“remainder”，误判率为6% +（0.94 *）20％。

“排序”

          if (i >= 20 && i < 95) ++nMid;  // 75% not taken
          else if (i < 20) ++nLow;        // 19/25 76% not taken
          else if (i >= 95) ++nHigh;      //Least likely branch

这些分支将被预测为无跳转、无跳转和Sherlock。

25%+(0.75*)24% 预测错误。

导致18-23%的差异（测量差异约为9%），但我们需要计算周期而不是预测错误百分比。

假设我的Nehalem CPU上有17个周期的预测惩罚，并且每个检查需要1个周期来发出（4-5个指令），循环也需要一个周期。数据依赖关系是计数器和循环变量，但一旦预测错误消除，它不应影响时间。

因此对于“reverse”，我们得到了计时方程（我记得这应该是《计算机体系结构：量化方法》中使用的公式）。

mispredict*penalty+count+loop
0.06*17+1+1+    (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+  (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration

对于“sorted”也是如此。

0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1)  (= 0.06*4=0.24)
= 8.26

(8.26-7.24)/8.26 = 13.8%，与测量值接近（接近于测量值？！）。

因此，OP的显而易见并不显而易见。

使用这些测试，其他具有更复杂代码或更多数据依赖性的测试肯定会有所不同，因此请测量您的情况。

更改测试顺序会更改结果，但这可能是由于循环开始的不同对齐方式造成的，在所有新的Intel CPU上理想情况下应该是16字节对齐，但在这种情况下不是。

- Surt

Answer 9

按照你喜欢的任何逻辑顺序放置它们。当然，分支可能会更慢，但分支不应该是计算机正在执行的大部分工作。

如果你正在处理性能关键的代码部分，那么一定要使用逻辑顺序、基于配置文件的优化和其他技术，但对于普通代码来说，我认为这更多地是一种风格选择。

- Jack

---

分支预测失误很耗费资源。在微基准测试中，它们的代价被低估了，因为x86有一个庞大的分支预测表。对相同条件进行紧密循环会导致CPU比您更清楚哪个最有可能发生。但是，如果您的代码中到处都是分支，您的分支预测缓存可能会用尽插槽，CPU就会假设默认情况。知道默认猜测可以节省整个代码库中的周期。 - Yakk - Adam Nevraumont

@Yakk Jack的答案是唯一正确的。如果您的编译器能够进行优化，请不要进行降低可读性的优化。如果编译器已经为您执行了常量折叠、死代码消除、循环展开或其他任何优化，那么您也不需要再次执行这些操作，对吧？编写您的代码，使用基于分析的优化（它旨在解决此问题，因为程序员很难猜测），然后查看您的编译器是否对其进行了优化。最终，您不希望在性能关键代码中有任何分支。 - Christoph Diegelmann

@Christoph 我不会包含我知道已经失效的代码。当我知道对于某些迭代器来说，i++ 很难优化为 ++i 时，我不会使用 i++，因为这样会导致性能下降。这是为了避免悲观情况；将最可能的块作为默认习惯放在前面不会导致可读性降低（实际上可能有所帮助！），同时产生分支预测友好的代码（从而给您一个统一的小性能提升，无法通过后期微调获得）。 - Yakk - Adam Nevraumont

Answer 10

如果您已经了解了if-else语句的相对概率，那么出于性能考虑最好使用排序方式，因为它只会检查一个条件（即真实的条件）。

在未排序的情况下，编译器会不必要地检查所有条件并花费时间。

- aditya rawat