网站可以不备案,青岛房产网首页,厦门抖音代运营公司,巨蟹座适合网站建设吗分支预测的英文名字是「Branch Prediction」大家可以在Google上搜索这个关键字#xff0c;可以看到关于分支预测的很多内容#xff0c;不过要搞清楚分支预测如何工作的#xff0c;才是问题的关键。分支预测对程序的影响我们来看看下面的两段代码代码1#include algorithm… 分支预测的英文名字是「Branch Prediction」大家可以在Google上搜索这个关键字可以看到关于分支预测的很多内容不过要搞清楚分支预测如何工作的才是问题的关键。分支预测对程序的影响我们来看看下面的两段代码代码1#include algorithm
#include ctime
#include iostream
int main()
{// Generate dataconst unsigned arraySize 32768;int data[arraySize];for (unsigned c 0; c arraySize; c)data[c] std::rand() % 256;// !!! With this, the next loop runs faster.//std::sort(data, data arraySize);// Testclock_t start clock();long long sum 0;for (unsigned i 0; i 100000; i) {for (unsigned c 0; c arraySize; c) { // Primary loopif (data[c] 128) sum data[c];}}double elapsedTime static_castdouble(clock()-start) / CLOCKS_PER_SEC;std::cout elapsedTime \n;std::cout sum sum \n;
}执行结果ubuntu:/data/study$ g fenzhi.cpp ./a.out
21.6046
sum 314931600000代码2#include algorithm
#include ctime
#include iostream
int main()
{// Generate dataconst unsigned arraySize 32768;int data[arraySize];for (unsigned c 0; c arraySize; c)data[c] std::rand() % 256;// !!! With this, the next loop runs faster.std::sort(data, data arraySize);// Testclock_t start clock();long long sum 0;for (unsigned i 0; i 100000; i) {for (unsigned c 0; c arraySize; c) { // Primary loopif (data[c] 128) sum data[c];}}double elapsedTime static_castdouble(clock()-start) / CLOCKS_PER_SEC;std::cout elapsedTime \n;std::cout sum sum \n;
}执行结果ubuntu:/data/study$ g fenzhi.cpp ./a.out
8.52157
sum 314931600000第一段代码生成随机数组后没有进行排序第二段代码对随机的数组进行排序执行的时间上发生了非常大的差异。所以他们发生了什么事情呢导致他们结果不同的原因就是分支预测分支预测是CPU处理器对程序的一种预测和CPU架构有关系现在的很多处理器都有分支预测的功能。CPU在执行这段代码的时候if (data[c] 128) sum data[c];CPU会有一个提前预测机制比如前面的执行结果都是true那么下一次在判断if的时候就会默认认为是true来处理让下面的几条指令提前进入预装。当然这个判断不会影响实际的结果输出这个判断只是为了让CPU并行执行代码。CPU执行一条指令分为几个阶段既然是分阶段执行也就是我们正常说的pipeline(流水线执行)。流水线的工人只要完成自己负责的内容就好了没有必要去关心其他的人处理。那如果我有一段代码如下int a 0;
a 1;
a 2;
a 3;从这个图上我们可以看到我们认为是在执行 a 0结束后才会执行a1。但是实际CPU是在执行a0的第一条执行后马上就去执行a1的第一条指令了。也就因为这样执行速度上得到了大幅度的提升。但是对于if() 语言在没有分支预测的时候我们需要等待if()执行出现结果后才能继续执行下一个代码。如果存在分支预测的情况通过比较我们可以发现如果存在分支预测的时候就让执行速度变快了。那如果预测失败会不会就影响了执行的时间答案是肯定的。在前面的例子中没有对数组排序的情况下分支预测大部分都会是失败的这个时候就会在执行结束后重新取指令执行会严重影响执行效率。而在排序后的例子中分支预测一直处于成功的状态CPU的执行速率得到大幅度的提升。如果解决分支预测引起的性能下降分支预测一定会存在一定的能性下降想让性能提升的方法就是不要使用这个该死的if语句。比如上面的代码我们可以修改成这样#include algorithm
#include ctime
#include iostream
int main()
{// Generate dataconst unsigned arraySize 32768;int data[arraySize];for (unsigned c 0; c arraySize; c)data[c] std::rand() % 256;// !!! With this, the next loop runs faster.//std::sort(data, data arraySize);// Testclock_t start clock();long long sum 0;for (unsigned i 0; i 100000; i) {for (unsigned c 0; c arraySize; c) { // Primary loopint t (data[c] - 128) 31;sum ~t data[c];}}double elapsedTime static_castdouble(clock()-start) / CLOCKS_PER_SEC;std::cout elapsedTime \n;std::cout sum sum \n;
}比如我们看到的绝对值代码里面也用了这样的思想/*** abs - return absolute value of an argument* x: the value. If it is unsigned type, it is converted to signed type first.* char is treated as if it was signed (regardless of whether it really is)* but the macros return type is preserved as char.** Return: an absolute value of x.*/
#define abs(x) __abs_choose_expr(x, long long, \__abs_choose_expr(x, long, \__abs_choose_expr(x, int, \__abs_choose_expr(x, short, \__abs_choose_expr(x, char, \__builtin_choose_expr( \__builtin_types_compatible_p(typeof(x), char), \(char)({ signed char __x (x); __x0?-__x:__x; }), \((void)0)))))))#define __abs_choose_expr(x, type, other) __builtin_choose_expr( \__builtin_types_compatible_p(typeof(x), signed type) || \__builtin_types_compatible_p(typeof(x), unsigned type), \({ signed type __x (x); __x 0 ? -__x : __x; }), other)当然你也可以这样写int abs(int i){if(i0)return ~(--i);return i;
}所以说计算机的尽头是数学参考https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array/11227902#11227902https://blog.csdn.net/loongshawn/article/details/118339009https://blog.csdn.net/DBC_121/article/details/105360658
