如果…按照概率进行sorting，sorting的效果如何？
具体来说，如果我有一系列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
看起来很明显，sorting的版本会更快，但是为了可读性或副作用的存在，我们可能想要对它们进行非最优sorting。 在实际运行代码之前，也很难判断CPU如何处理分支预测。
所以在试验过程中，我最终回答了自己的一个具体案例的问题，但是我也希望听到其他意见/见解。
重要的是：这个问题假设if语句可以被任意地重新sorting而不会对程序的行为产生任何其他影响。 在我的回答中，三个条件testing是相互排斥的，不会产生副作用。 当然，如果这些陈述必须以一定的顺序进行评估以达到一些理想的行为，那么效率问题就没有意义了。
作为一般规则，如果不是所有的英特尔CPU都假定远期分支在大多数情况下不是在他们第一次看到它们时就被采用。 看到Godbolt的工作 。
之后，分支进入分支预测caching，过去的行为被用来通知未来的分支预测。
所以在一个紧密的循环中，乱序的影响将会相对较小。 分支预测器将要学习哪一组分支是最有可能的，如果你在循环中有不平凡的工作量，那么小的差异将不会增加太多。
在通用代码中，大多数默认编译器（缺less另一个原因）将大致按照您在代码中订购的方式对生成的机器代码进行sorting。 因此，如果语句失败时是前向分支。
所以你应该按照降低可能性的顺序来命令你的分支，从“第一次遭遇”中得到最好的分支预测。
一个在一系列条件下循环多次的微基准，并且微不足道的工作将由指令计数等等的微小效应支配，而在相对分支预测问题方面则很less。 所以在这种情况下，你必须configuration文件 ，因为经验法则是不可靠的。
最重要的是，vector化和许多其他的优化适用于微小的紧密循环。
所以在一般的代码中，把最可能的代码放在if块中，这样会导致最less的未caching的分支预测未命中。 在严格的循环中，按照一般规则开始，如果您需要了解更多信息，则除了进行configuration外，别无select。
自然，如果一些testing比其他testing便宜的话，这一切都会消失。
我做了以下testing，以计算两个不同的if … else if块的执行时间，一个按概率sorting，另一个按相反的顺序sorting：
#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，结果显示sorting后的版本始终比未sorting版本快大约28％。 Per luk32的评论中，我也改变了两个testing的顺序，这个testing显着不同（22％vs 28％）。 该代码是在Windows 7下运行的英特尔至强E5-2697 v2。 这当然是非常具体的问题，不应该被解释为一个确定的答案。
不，你不应该，除非你确定目标系统受到影响。 默认情况下通过可读性。
我非常怀疑你的结果。 我已经修改了你的例子，所以反转执行更容易。 Ideone相当一贯地表明，逆序更快，尽pipe并不多。 在某些运行中偶尔也会翻转。 我会说结果是不确定的。 科里鲁报告也没有真正的区别。 稍后我可以检查我的odroid xu4上的Exynos5422 CPU。
现代CPU有分支预测器。 有很多逻辑专门用于预取数据和指令，而现代x86 CPU则相当聪明。 一些像ARM或GPU这样的更简单的体系结构可能容易受到这种威胁。 但它确实高度依赖于编译器和目标系统。
我会说分支sorting优化是相当脆弱和短暂的。 只做一些真正微调的步骤。
码：
#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; } }
只是我5美分。 看来，如果陈述应该取决于：
-
每个if语句的概率。
-
迭代次数，所以分支预测器可以踢进去。
-
可能/不太可能的编译器提示，即代码布局。
为了探索这些因素，我对以下function进行了基准testing：
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（）
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; }
ordered_ifs_with_hints（）
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; }
reversed_ifs_with_hints（）
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
但是，4K和8K迭代对于50％概率高度赞同陈述的区别是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
所以，提示也有帮助，但只是一点点。
总体结论是： 总是对代码进行基准testing，因为结果可能会令人惊讶。
希望有所帮助。
基于这里的其他答案，看起来唯一真正的答案是： 这取决于 。 它至less取决于以下（尽pipe不一定按照这个重要性顺序）：
- 每个分支的相对概率。 这是被问到的原始问题。 根据现有的答案，似乎有一些条件下按概率sorting有所帮助，但似乎并非总是如此。 如果相对概率差别不大，那么按照它们的顺序是不会有什么差别的。但是，如果第一个条件发生在99.999％的时间，而下一个是剩下的部分，那么我会假定把最可能的一个放在第一位对时间有利。
- 计算每个分支真/假条件的成本。 如果testing条件的时间成本对于一个分支相对于另一个分支是非常高的，则这可能对时间和效率具有显着的影响。 例如，考虑以一个时间单位计算（例如，检查布尔variables的状态）与另一个需要数十，数百，甚至数百万个时间单位来计算的条件（例如，检查磁盘上的文件或对大型数据库执行复杂的SQL查询）。 假设代码每次都按顺序检查条件，那么更快的条件可能应该是第一的（除非它们依赖于其他先失败的条件）。
- 编译器/解释器一些编译器（或解释器）可能包括一种可能影响性能的另一种优化（其中一些只有在编译和/或执行期间select某些选项时才存在）。 所以除非你使用完全相同的编译器在同一个系统上对两个编译和执行其他相同的代码进行基准testing，其中唯一的区别就是相关分支的顺序，否则你将不得不为编译器的变化留出一些余地。
- 操作系统/硬件如luk32和Yakk所述，各种CPU都有自己的优化（操作系统也一样）。 所以基准再次受到这里变化的影响。
- 代码块执行的频率如果包含分支的块很less被访问（例如，在启动过程中只有一次），那么可能很less涉及到分支的顺序。 另一方面，如果你的代码在你的代码的一个关键部分正在攻击这个代码块，那么sorting可能会很重要（取决于基准）。
要确定的唯一方法是基准你的具体情况，最好在与代码将最终运行的预期系统相同（或非常相似）的系统上。 如果打算在不同硬件，操作系统等的一系列不同系统上运行，那么对多个变体进行基准testing是最好的select。 在一种types的系统上进行一次编码，另一种在另一种types的系统上进行sorting，可能会是一个好主意。
我个人的经验法则（在大多数情况下，没有基准）是根据
- 依赖于先前条件的结果的条件，
- 然后计算条件的成本
- 每个分支的相对概率。
我通常看到的解决高性能代码的方式是保持最易读的顺序，但是向编译器提供提示。 这里是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 。 尝试重新sorting这些if子句只会混淆代码，但是likely()和unlikely()macros实际上通过指出什么是正常情况以及什么是exception来帮助可读性。
这些macros的Linux实现使用GCC特定function 。 看来，铛和英特尔C编译器支持相同的语法，但MSVC没有这样的function 。
还取决于你的编译器和你正在编译的平台。
从理论上讲，最有可能的条件应该是尽可能的减less控制。
通常最可能的情况应该是第一：
if (most_likely) { // most likely instructions } else …
最stream行的asm是基于当条件为真时跳转的条件分支。 那C代码可能会被翻译成这样的伪造：
jump to ELSE if not(most_likely) // most likely instructions jump to end ELSE: …
这是因为跳转使得cpu取消了执行pipe道，并且由于程序计数器改变而停止运行（对于支持pipe道的架构，这些架构实际上很常见）。 然后是关于编译器，这可能会也可能不会应用一些复杂的优化，使统计上最可能的条件得到控制减less跳跃。
我决定使用Lik32代码在我自己的机器上重新运行testing。 我不得不改变，由于我的Windows或编译器认为高分辨率是1ms，使用
mingw32-g ++ .exe -O3 -Wall -std = c ++ 11 -fexceptions -g
vector<int> rand_vec(10000000);
海湾合作委员会对两个原始代码进行了相同的转换。
请注意，只有两个第一个条件才能被testing，因为第三个条件必须是真实的，GCC在这里是一种Sherlock。
相反
.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
所以除了最后一种情况不需要分支预测之外，这并没有给我们多less提示。
现在我尝试了所有6个组合的if，前2是原始的反向和sorting。 高于> = 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.
So the branches will be predicted taken, taken and remainder with
6%+(0.94*)20% mispredicts.
"Sorted"
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
The branches will be predicted with not taken, not taken and Sherlock.
25%+(0.75*)24% mispredicts
Giving 18-23% difference (measured difference of ~9%) but we need to calculate cycles instead of mispredicting %.
Let's assume 17 cycles mispredict penalty on my Nehalem CPU and that each check takes 1 cycle to issue (4-5 instructions) and the loop takes one cycle too. The data dependencies are the counters and the loop variables, but once the mispredicts are out of the way it shouldn't influence the timing.
So for "reverse", we get the timings (this should be the formula used in Computer Architecture: A Quantitative Approach 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
and the same for "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% vs. ~9% measured (close to the measured!?!).
So the obvious of the OP is not obvious.
With these tests, other tests with more complicated code or more data dependencies will certainly be different so measure your case.
Changing the order of the test changed the results but that could be because of different alignments of the loop start which should ideally be 16 bytes aligned on all newer Intel CPUs but isn't in this case.
Put them in whatever logical order you like. Sure, the branch may be slower, but branching should not be the majority of work your computer is doing.
If you are working on a performance critical portion of code, then certainly use logical order, profile guided optimization and other techniques, but for general code, I think its really more of a stylistic choice.
If you already know the relative probability of if-else statement,then for performance purpose it would be better to use the sorted way, as it will only check one condition(the true one).
In an unsorted way the compiler will check all the conditions unnecessarily and will take time.
