小开

我做了下面的测试来计算两个不同的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下运行。当然，这是一个非常具体的问题，不应被解释为一个结论性的答案。

小开

也取决于您的编译器和您编译的平台。

理论上，最可能的条件应该使控制跳跃尽可能少。

通常，最可能的条件应该是第一个：

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

最流行的ASM基于条件真的时跳转的条件分支。该C代码可能会被转换为这样的伪ASM：

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

这是因为跳转会使CPU取消执行流水线并停止，因为程序计数器发生了变化（对于支持真正常见的流水线的体系结构）。然后是关于编译器，它可能会也可能不会应用一些复杂的优化，关于统计上最可能的条件，以使控制进行更少的跳转。

小开

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

我非常怀疑你的结果。，我稍微修改了一下你的例子，所以反向执行更容易。伊代奥内相当一致地表明，反向顺序更快，尽管不是很快。在某些运行中，甚至这偶尔会翻转。我想说结果是不确定的。科利鲁报告也没有真正的差异。稍后我可以在我的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;
}
}

小开

把它们按你喜欢的逻辑顺序排列。当然，分支可能会慢一些，但分支不应该是您的计算机正在做的大部分工作。

如果您正在处理代码的性能关键部分，那么当然要使用逻辑顺序、配置文件引导优化和其他技术，但对于一般代码，我认为它实际上更多的是一种风格选择。

小开

最佳答案

作为一般规则，大多数（如果不是全部）Intel CPU假设第一次看到它们时不执行正向分支。参见戈德波特的作品。

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

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

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

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

在一组条件上循环多次并执行琐碎工作的微基准测试将受到指令计数等的微小影响，并且很少出现相对分支预测问题。所以在这种情况下，你必须配置文件，因为经验法则并不可靠。

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

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

当然，如果某些测试比其他测试便宜得多，这一切都会被抛到九霄云外。

小开

根据这里的其他一些答案，看起来唯一真正的答案是：视情况而定。它至少取决于以下几点（尽管不一定按此重要性顺序排列）：

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

确定的唯一方法是对您的特定情况进行基准测试，最好是在与代码最终运行的预期系统相同（或非常相似）的系统上。如果打算在一组具有不同硬件、操作系统等的不同系统上运行，则最好对多个变体进行基准测试，以确定哪个是最好的。在一种类型的系统上使用一种排序来编译代码，而在另一种类型的系统上使用另一种排序来编译代码，这甚至可能是一个好主意。

我个人的经验法则（在大多数情况下，在没有基准的情况下）是根据以下内容订购：

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

小开

对于高性能代码，我通常认为解决这个问题的方法是保持最具可读性的顺序，但向编译器提供提示。下面是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和英特尔C编译器似乎支持相同的语法，但MSVC没有这样的功能。

小开

我决定使用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的组合，前2个是原始的反向和排序。高为>=95，低为<；20，MID为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和Remains

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

分支将用Not Taken、Not Taken和Sherlock进行预测。

25%+（0.75*）24%预测错误

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

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

因此，对于“反向”，我们得到了计时（这应该是计算机体系结构中使用的公式：定量方法IIRC）。

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

“已排序”也是如此

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%vs.约9%测量值（接近测量值！？！）。

所以OP的明显之处并不明显。

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

改变测试的顺序改变了结果，但这可能是因为循环开始的不同对齐，理想情况下，在所有较新的Intel CPU上应该是16字节对齐，但在这种情况下不是这样。

小开

只是我的5分钱。对if语句进行排序的效果似乎取决于：

每个IF语句的概率。

迭代次数，因此分支预测器可以启动。

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

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

有序_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;
}

反向_IFS（）

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;
}

带_提示的有序_IFS_（）

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;
}

带_提示的反向_IFS_（）

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;
}

结果

以下是英特尔I5@3.2 GHz和G++6.3.0的结果。第一个参数是检查_点（即，高度可能的IF语句的以%%为单位的概率），第二个参数是数据_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

但对于8K迭代，结果总是稍好一些：

---------------------------------------------------------------------
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

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

总体结论为：始终对代码进行基准测试，因为结果可能会令人惊讶。

希望对你有帮助。

小开

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

以未排序的方式，编译器将检查所有不必要的条件，并且将花费时间。

如果..，订购会有什么影响？Else If语句的概率？