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