參考Why is processing a sorted array faster than an unsorted array?
問題
看以下代碼：
#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那一行，以上代碼將運行更長的時間。在我的機器上未去掉std::sort耗時8.99s，去掉后耗時24.78s。編譯器使用的是gcc4.4.3。事實上，以上代碼跟編譯器沒有關系，甚至跟語言沒有關系。那這是為什么呢？
這跟處理這個數組的邏輯有非常大的關系。如以上代碼所示，這個循環里有個條件判斷。條件判斷被編譯成二進制代碼后，就是一個跳轉指令，類似：
具體為什么會不同，這涉及到計算機CPU執行指令時的行為。
CPU的流水線指令執行
想象現在有一堆指令等待CPU去執行，那么CPU是如何執行的呢？具體的細節可以找一本計算機組成原理的書來看。CPU執行一堆指令時，并不是單純地一條一條取出來執行，而是按照一種流水線的方式，在CPU真正執行一條指令前，這條指令就像工廠里流水線生產的產品一樣，已經被經過一些處理。簡單來說，一條指令可能經過這些過程：取指(Fetch)、解碼(Decode)、執行(Execute)、放回(Write-back)。
假設現在有指令序列ABCDEFG。當CPU正在執行(execute)指令A時，CPU的其他處理單元（CPU是由若干部件構成的）其實已經預先處理到了指令A后面的指令，例如B可能已經被解碼，C已經被取指。這就是流水線執行，這可以保證CPU高效地執行指令。
Branch Prediction
如上所說，CPU在執行一堆順序執行的指令時，因為對于執行指令的部件來說，其基本不需要等待，因為諸如取指、解碼這些過程早就被做了。但是，當CPU面臨非順序執行的指令序列時，例如之前提到的跳轉指令，情況會怎樣呢？
取指、解碼這些CPU單元并不知道程序流程會跳轉，只有當CPU執行到跳轉指令本身時，才知道該不該跳轉。所以，取指解碼這些單元就會繼續取跳轉指令之后的指令。當CPU執行到跳轉指令時，如果真的發生了跳轉，那么之前的預處理（取指、解碼）就白做了。這個時候，CPU得從跳轉目標處臨時取指、解碼，然后才開始執行，這意味著：CPU停了若干個時鐘周期！
這其實是個問題，如果CPU的設計放任這個問題，那么其速度就很難提升起來。為此，人們發明了一種技術，稱為branch prediction，也就是分支預測。分支預測的作用，就是預測某個跳轉指令是否會跳轉。而CPU就根據自己的預測到目標地址取指令。這樣，即可從一定程度提高運行速度。當然，分支預測在實現上有很多方法。
簡單的預測可以直接使用之前的實際執行結果。例如某個跳轉指令某一次產生了跳轉，那么下一次執行該指令時，CPU就直接從跳轉目標地址處取指，而不是該跳轉指令的下一條指令。
答案
了解了以上信息后，文章開頭提出的問題就可以解釋了。這個代碼中有一個循環，這個循環里有一個條件判斷。每一次CPU執行這個條件判斷時，CPU都可能跳轉到循環開始處的指令，即不執行if后的指令。使用分支預測技術，當處理已經排序的數組時，在若干次data[c]>=128都不成立時（或第一次不成立時，取決于分支預測的實現），CPU預測這個分支是始終會跳轉到循環開始的指令時，這個時候CPU將保持有效的執行，不需要重新等待到新的地址取指；同樣，當data[c]>=128條件成立若干次后，CPU也可以預測這個分支是不必跳轉的，那么這個時候CPU也可以保持高效執行。
相反，如果是無序的數組，CPU的分支預測在很大程度上都無法預測成功，基本就是50%的預測成功概率，這將消耗大量的時間，因為CPU很多時間都會等待取指單元重新取指。
本文完。最后感嘆下stackoverflow上這個帖子里那個老外回答問題的專業性，我要是樓主早就感動得涕淚橫飛了。感謝每一個傳播知識的人。
參考資料
- http://blog.sina.com.cn/s/blog_6c673e570100zfmo.html
- http://www.cnblogs.com/dongliqian/archive/2012/04/05/2433847.html
- http://en.wikipedia.org/wiki/Branch_predictor