很久以前在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秒
問題：為什么會出現(xiàn)這種情況？
解答：分支預(yù)測。
考慮以下if語句塊。對于處理器來說，就是一個分支指令，如下：
處理器每次遇到一條分支時，它都不知道該走哪一條道。這時候該怎么辦？程序停下來，等待前面的指令執(zhí)行完，得到確切的結(jié)果后，再接著走某一條分支。
現(xiàn)代處理器都支持指令并行處理和超流水線作業(yè)。因此，當(dāng)處理器遇到程序分支時，都會去猜測應(yīng)該走哪一條分支。
如果猜對了，程序接著流暢運行。如果猜錯了，則處理器需要做一些額外的工作，再次回到那條正確的分支。
因此，如果處理器每次都猜錯，那程序的運行時間就會邊長。
這就是上面的代碼為什么運行時間會相差那么大的原因。
對于分支語句：
if (data[c] >= 128)
sum += data[c];
在保留std::sort(data, data + arraySize);的情況下。數(shù)組data中的內(nèi)容是這樣的：
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)
在未排序的情況下，數(shù)組data中的內(nèi)容是這樣的：
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)
也就是說，在已經(jīng)排序的情況下，處理器便能更好的預(yù)測分支了。因此，程序也運行的更快。
關(guān)于分支預(yù)測
閱讀linux源代碼時，你會發(fā)現(xiàn)if(likely( )){}或是if(unlikely( ))這樣的語句。對于條件選擇語句，gcc內(nèi)建了一條指令用于優(yōu)化，在一個條件經(jīng)常出現(xiàn)，或者該條件很少出現(xiàn)的時候，編譯器可以根據(jù)這條指令對條件分支選擇進行優(yōu)化。而Linux內(nèi)核把這條指令封裝成了宏likely()和unlikely()。
因此，在編寫程序時，如果一個分支條件只有在很少數(shù)的情況下才出現(xiàn)時，我們使用unlikely( )和likely( )能夠加快程序的運行,這也是一種優(yōu)化程序的手段。
比如這樣：
if ( unlikely(statement) ) { //這里便是告訴編譯器，這個條件只在少數(shù)情況下發(fā)生
dosomething();
}
轉(zhuǎn)載請注明：快課網(wǎng) ? Code Inside：為什么處理已排序數(shù)組比處理未排序數(shù)組更快？
本站文章版權(quán)歸原作者及原出處所有 。內(nèi)容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責(zé)，本站只提供參考并不構(gòu)成任何投資及應(yīng)用建議。本站是一個個人學(xué)習(xí)交流的平臺，網(wǎng)站上部分文章為轉(zhuǎn)載，并不用于任何商業(yè)目的，我們已經(jīng)盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯(lián)系我們，我們將根據(jù)著作權(quán)人的要求，立即更正或者刪除有關(guān)內(nèi)容。本站擁有對此聲明的最終解釋權(quán)。
