具体来说,如果我有一系列 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
语句可以任意重新排序,而不会对程序的行为产生任何其他影响。在我的回答中,三个条件测试是互斥的,不会产生副作用。当然,如果必须按特定顺序评估语句以实现某些期望的行为,那么效率问题就没有实际意义。
作为一般规则,大多数(如果不是全部)英特尔 CPU 都假定在第一次看到前向分支时不会采用它们。请参阅Godbolt's work。
之后,分支进入分支预测缓存,过去的行为用于通知未来的分支预测。
所以在一个紧密的循环中,错误排序的影响会相对较小。分支预测器将了解哪组分支最有可能,并且如果您在循环中有大量工作,那么微小的差异不会加起来太多。
在一般代码中,大多数编译器默认情况下(缺少另一个原因)将大致按照您在代码中排序的方式对生成的机器代码进行排序。因此,如果语句在失败时是前向分支。
因此,您应该按照可能性递减的顺序对分支进行排序,以便从“第一次遇到”中获得最佳分支预测。
一个在一组条件下紧密循环多次并完成微不足道的工作的微基准测试将受到指令数等微小影响的支配,而在相关分支预测问题方面几乎没有影响。因此,在这种情况下,您必须配置文件,因为经验法则不可靠。
最重要的是,矢量化和许多其他优化适用于微小的紧密循环。
因此,在一般代码中,将最有可能的代码放在 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;
}
将 MSVC2017 与 /O2 结合使用,结果显示排序后的版本始终比未排序的版本快约 28%。根据 luk32 的评论,我还切换了两个测试的顺序,这产生了明显的差异(22% 对 28%)。该代码在 Intel Xeon E5-2697 v2 上的 Windows 7 下运行。当然,这是非常具体的问题,不应被解释为结论性的答案。
if... else if
语句可能会对逻辑在代码中的流动方式产生重大影响。 unlikely
检查可能不会经常出现,但可能存在业务需要先检查 unlikely
条件,然后再检查其他条件。
g++ -O2 -march=native -std=c++14
确实使排序的条件语句略有优势,但大多数时候,两次运行之间的百分比差异约为 5%。有几次,它实际上更慢(由于差异)。我相当肯定,像这样订购 if
是不值得担心的; PGO 可能会完全处理任何此类情况
只是我的 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;
}
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. 迭代次数很重要
4K 和 8K 迭代之间的差异(几乎)100% 概率的高度喜欢的语句大约是两倍(如预期的那样):
---------------------------------------------------------------------
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
所以,这些提示也有帮助,但只是一点点。
总体结论是:总是对代码进行基准测试,因为结果可能会出人意料。
希望有帮助。
g++ -O2
或 -O3 -fno-tree-vectorize
,但您应该这样说。
不,你不应该,除非你真的确定目标系统受到影响。默认情况下以可读性为准。
我非常怀疑您的结果。我对您的示例进行了一些修改,因此逆向执行更容易。 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;
}
}
基于此处的其他一些答案,看起来唯一真正的答案是:视情况而定。它至少取决于以下内容(尽管不一定按重要性顺序):
每个分支的相对概率。这是最初提出的问题。根据现有的答案,似乎在某些情况下按概率排序会有所帮助,但似乎并非总是如此。如果相对概率不是很不同,那么它们的顺序不太可能有任何区别。但是,如果第一个条件发生 99.999% 的时间,而下一个条件是剩下的一小部分,那么我会假设把最有可能的一个放在第一位在时间方面是有益的。
计算每个分支的真/假条件的成本。如果一个分支测试条件的时间成本比另一个分支高,那么这可能会对时间和效率产生重大影响。例如,考虑一个需要 1 个时间单位来计算的条件(例如,检查布尔变量的状态)与另一个需要数十、数百、数千甚至数百万时间单位来计算的条件(例如,检查磁盘上的文件或对大型数据库执行复杂的 SQL 查询)。假设代码每次都按顺序检查条件,那么更快的条件可能应该是第一个(除非它们依赖于其他先失败的条件)。
编译器/解释器 一些编译器(或解释器)可能包括对另一种可能影响性能的优化(其中一些仅在编译和/或执行期间选择某些选项时才存在)。因此,除非您使用完全相同的编译器在同一系统上对其他相同代码的两个编译和执行进行基准测试,唯一的区别是相关分支的顺序,否则您将不得不为编译器的变化留出一些余地。
操作系统/硬件 正如 luk32 和 Yakk 所提到的,各种 CPU 都有自己的优化(操作系统也是如此)。因此,基准在这里再次容易受到变化的影响。
代码块执行的频率 如果包含分支的块很少被访问(例如,在启动期间只有一次),那么你放置分支的顺序可能就无关紧要了。另一方面,如果您的代码在代码的关键部分敲击此代码块,那么排序可能很重要(取决于基准测试)。
确定的唯一方法是对您的特定情况进行基准测试,最好是在与最终运行代码的预期系统相同(或非常相似)的系统上。如果它打算在一组具有不同硬件、操作系统等的不同系统上运行,那么最好对多个变体进行基准测试,看看哪个是最好的。让代码在一种类型的系统上以一种顺序编译,而在另一种类型的系统上以另一种顺序编译,这甚至可能是一个好主意。
我个人的经验法则(在大多数情况下,在没有基准的情况下)是基于:
依赖于先验条件结果的条件,计算条件的成本,然后是每个分支的相对概率。
我通常看到解决高性能代码的方法是保持最易读的顺序,但为编译器提供提示。以下是 Linux kernel 中的一个示例:
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 specific features。似乎 clang 和 Intel C 编译器支持相同的语法,但是 MSVC doesn't have such feature。
likely()
和 unlikely()
宏,并包含有关相应编译器功能的一些信息,这将更有帮助。
else if
的顺序。
还取决于您的编译器和您正在编译的平台。
理论上,最可能的情况应该使控制跳跃尽可能少。
通常最可能的情况应该是首先:
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 取消执行管道并停止,因为程序计数器发生了变化(对于支持真正常见的管道的体系结构)。然后是关于编译器,它可能会或可能不会应用一些复杂的优化,以使统计上最有可能的条件使控件的跳转更少。
clang
实际上对 test2
和 test3
采用了不同的方法:由于指示 < 0
或 == 0
测试可能为假的启发式方法,它决定将函数的其余部分克隆到两条路径,因此它能够使 condition == false
成为直通路径。这是可行的,只是因为函数的其余部分很短:在 test4
中我又添加了一个操作,它又回到了我上面概述的方法。
jmp
之后的其余指令没用,因此浪费了获取/解码带宽(2)即使预测现代大内核每个周期只进行一次提取,因此它设置了 1 个采取分支/周期的硬性限制(OTOH 现代英特尔可以做 2 个未采取/周期)(3)分支预测更难处理采取的连续分支,并且在快速+慢速预测器的情况下......
我决定使用 Lik32 代码在我自己的机器上重新运行测试。由于我的 Windows 或编译器认为高分辨率是 1ms,我不得不更改它,使用
mingw32-g++.exe -O3 -Wall -std=c++11 -fexceptions -g
vector<int> rand_vec(10000000);
GCC 对两个原始代码进行了相同的转换。
请注意,仅测试前两个条件,因为第三个条件必须始终为真,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
所以这并没有告诉我们太多,除了最后一种情况不需要分支预测。
现在我尝试了所有 6 个 if 组合,前 2 个是原始的反向并排序。 high >= 95,low < 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.
所以分支将被预测采用,采用并剩余
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 条指令),并且循环也需要一个周期。数据依赖项是计数器和循环变量,但是一旦错误预测消失,它就不应该影响时间。
所以对于“反向”,我们得到了时间(这应该是计算机体系结构中使用的公式:一种定量方法 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 字节对齐,但在这种情况下并非如此。
将它们按照您喜欢的任何逻辑顺序排列。当然,分支可能会更慢,但分支不应该是您的计算机所做的大部分工作。
如果您正在处理代码的性能关键部分,那么当然可以使用逻辑顺序、配置文件引导优化和其他技术,但对于一般代码,我认为它确实更像是一种风格选择。
++i
可以使用时,我不会使用 i++
,因为我知道某些迭代器的 i++
很难优化到 ++i
并且差异(对我而言)并不重要。这是为了避免悲观;将最有可能的块放在首位作为 默认习惯 不会导致明显的可读性降低(实际上可能会有所帮助!),同时会产生对分支预测友好的代码(从而为您提供统一的无法通过后期微优化重新获得的小幅性能提升)
如果您已经知道 if-else 语句的相对概率,那么出于性能目的,最好使用排序方式,因为它只会检查一个条件(真正的条件)。
编译器会以一种未排序的方式不必要地检查所有条件并且需要时间。
不定期副业成功案例分享