很久以前在stackoverflow上看到下面这段代码,今天忍不住把它摘录过来。
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const 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);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
上面的程序在保留std::sort(data, data + arraySize);语句时,程序运行时间是 11.54秒
但去掉排序语句后,程序运行时间是1.93秒
问题:为什么会出现这种情况?
解答:分支预测。
考虑以下if语句块。对于处理器来说,就是一个分支指令,如下:
处理器每次遇到一条分支时,它都不知道该走哪一条道。这时候该怎么办?程序停下来,等待前面的指令执行完,得到确切的结果后,再接着走某一条分支。
现代处理器都支持指令并行处理和超流水线作业。因此,当处理器遇到程序分支时,都会去猜测应该走哪一条分支。
如果猜对了,程序接着流畅运行。如果猜错了,则处理器需要做一些额外的工作,再次回到那条正确的分支。
因此,如果处理器每次都猜错,那程序的运行时间就会边长。
这就是上面的代码为什么运行时间会相差那么大的原因。
对于分支语句:
if (data[c] >= 128)
sum += data[c];
在保留std::sort(data, data + arraySize);的情况下。数组data中的内容是这样的:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
在未排序的情况下,数组data中的内容是这样的:
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)
也就是说,在已经排序的情况下,处理器便能更好的预测分支了。因此,程序也运行的更快。
关于分支预测
阅读linux源代码时,你会发现if(likely( )){}或是if(unlikely( ))这样的语句。对于条件选择语句,gcc内建了一条指令用于优化,在一个条件经常出现,或者该条件很少出现的时候,编译器可以根据这条指令对条件分支选择进行优化。而Linux内核把这条指令封装成了宏likely()和unlikely()。
因此,在编写程序时,如果一个分支条件只有在很少数的情况下才出现时,我们使用unlikely( )和likely( )能够加快程序的运行,这也是一种优化程序的手段。
比如这样:
if ( unlikely(statement) ) { //这里便是告诉编译器,这个条件只在少数情况下发生
dosomething();
}
转载请注明:快课网 ? Code Inside:为什么处理已排序数组比处理未排序数组更快?
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。