很久以前在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);語句時，程序運行時間是1.93 秒

但去掉排序語句后，程序運行時間是11.54秒

問題：為什么會出現(xiàn)這種情況？

解答：分支預(yù)測。

[[119029]]

程序分支

考慮以下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ù)這條指令對條件分支選擇進(jìn)行優(yōu)化。而Linux內(nèi)核把這條指令封裝成了宏likely()和unlikely()。

因此，在編寫程序時，如果一個分支條件只有在很少數(shù)的情況下才出現(xiàn)時，我們使用unlikely( )和likely( )能夠加快程序的運行,這也是一種優(yōu)化程序的手段。

比如這樣：

if ( unlikely(statement) ) { //這里便是告訴編譯器，這個條件只在少數(shù)情況下發(fā)生  
 
dosomething();  
 
} 

原文鏈接：http://www.cricode.com/3347.html