【導(dǎo)讀】：日常開發(fā)最容易被忽視的就是性能優(yōu)化，除了類似cache的性能刺客，還有分支預(yù)測這種不容易被察覺的優(yōu)化！

以下是正文

為什么處理有序數(shù)組比無序數(shù)組快？

由于某些怪異的原因，下面這段C++代碼表現(xiàn)的異乎尋?！?當(dāng)這段代碼作用于有序數(shù)據(jù)時其速度可以提高將近6倍，這真是令人驚奇。

#include #include #include 
int _tmain (int argc , _TCHAR * argv []){ //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?eclapsedTime?=?static_cast<double?>(clock()?-?start)?/?CLOCKS_PER_SEC;
 std::cout << eclapsedTime << std::endl; std::cout << "sum = " << sum << std::endl;???????return?0;}

• 如果把 std::sort(data, data+arraySize) 去掉，這段代碼耗時11.54秒。

  
  

• 對于有序數(shù)據(jù)，這段代碼耗時1.93秒

  
  

起初我以為這可能是某一種語言或某一個編譯器發(fā)生的異常的事件，后來我在java語言寫了個例子，如下：

import java.util.Arrays;import java.util.Random; public class Test_Sorted_UnSorted_Array { public static void main(String[] args) { //Generate data int arraySize = 32768; int data[] = new int[arraySize];  Random rnd = new Random(0); for( int c = 0; cc) data[c] = rnd.nextInt()%256;  //!!! With this, the next loop runs faster Arrays. sort(data);  //Test long start = System. nanoTime(); long sum = 0;  for( int i=0; i<100000; ++i){ //Primary loop for( int c = 0; cc){ if(data[c] >=128) sum += data[c]; } }  System. out.println((System. nanoTime() - start) / 1000000000.0); System. out.println( "sum = " + sum); }}

上述例子運行結(jié)果和前面C++例子運行的結(jié)果差異，雖然沒有C++中那么大，但是也有幾分相似。

對于上面的問題，我首先想的原因是排序可能會導(dǎo)致數(shù)據(jù)有緩存，但是轉(zhuǎn)念一想之前原因有點不切實際，因為上面的數(shù)組都是剛剛生成的，所以我的問題是：

• 上述代碼運行時到底發(fā)生了什么？

  
  

• 為什么運行排好序的數(shù)組會比亂序數(shù)組快？

  
  

• 上述代碼求和都是獨立的，而順序不應(yīng)該會產(chǎn)生影響。

?

來自?Mysticial?的最佳回復(fù)

你是分支預(yù)測（branch prediction ）失敗的受害者。

什么是分支預(yù)測？

考慮一個鐵路樞紐：

Imageby Mecanismo, via Wikimedia Commons. Used under theCC-By-SA 3.0license.

為了便于討論，假設(shè)現(xiàn)在是1800年，這時候還沒有出現(xiàn)遠(yuǎn)程或廣播通訊工具。

你是一個鐵路樞紐的工人。當(dāng)你聽到火車開來時，你不知道這個火車要走哪一條路，只有讓火車停下來詢問列車長火車要開往哪，最后你將軌道切換到相應(yīng)的方向。

火車的質(zhì)量非常大，固慣性很大，因此火車需要經(jīng)常性的加速減速。

有沒有更好的方法喃？可以猜火車將行駛的方向應(yīng)該是可行的！

• 如果猜對了，火車?yán)^續(xù)往前走；

  
  

• 如果猜錯了，列車長會讓火車停下來，并后退，然后告訴你正確的方向，然后火車重新啟動開往正確的方向。

考慮一個if語句：在處理器級別上，他是一個分支指令：

你來扮演處理器，當(dāng)你遇到一個分支，你不知道它要走哪條路，該怎么辦？你可以停止執(zhí)行并等待直到之前的指令執(zhí)行完。然后繼續(xù)執(zhí)行正確路徑的指令。

有沒有更好的方法喃？可以猜測哪個分支將要被執(zhí)行！

• 如果猜對了，繼續(xù)執(zhí)行；

  
  

• 如果猜錯了，你需要刷新管道并且回退到該分支，重新啟動執(zhí)行正確的方向。

如果每次都能猜對，整個執(zhí)行過程就不會停止。

如果經(jīng)常猜錯，就需要在停止、回退、重新執(zhí)行上花費非常多的時間。

這就是分支預(yù)測。不得不承認(rèn)這不是一個最好的比喻因為火車可以僅僅使用一個標(biāo)志表示其前進(jìn)的方向。但是對于計算機(jī)，直到最后時刻，處理器是不知道哪條分支被執(zhí)行。

想想可以使用什么預(yù)測策略使得火車回退的次數(shù)最少？哈哈，可以利用歷史數(shù)據(jù)！如果火車100次有99次都是向左，那么下次預(yù)測結(jié)果仍向左。如果過去數(shù)據(jù)是交替的，那么預(yù)測結(jié)果也是交替的。如果它每3次都換一個方向，那么預(yù)測也采用相同的方法。

簡而言之，你需要嘗試尋找出一個規(guī)則(模式)然后按照它進(jìn)行預(yù)測就可以了。分支預(yù)測基本上就是這樣工作的。

大部分應(yīng)用程序的分支是很規(guī)律的。這也是為什么現(xiàn)代的分支預(yù)測的準(zhǔn)確率基本上都在90%以上。但是當(dāng)沒有規(guī)律、不可預(yù)測的分支時候，分支預(yù)測就顯得比較拙雞了。

從上面可以得到啟發(fā)，這個問題的“罪魁禍?zhǔn)住本褪?if 語句

if (data[c] >= 128) um += data[c];

注意到數(shù)據(jù)是在0到255均勻分布的。當(dāng)排好序后，小于等于128的前半部分是不會執(zhí)行if語句的，大于128的后半部分都會進(jìn)入if語句。

這是非常有好的分支預(yù)測因為分支會連續(xù)多次執(zhí)行相同的分支。即使是一個簡單的飽和計數(shù)器也會預(yù)測正確除去當(dāng)變換方向后的少數(shù)幾個。

快速可視化

T = branch takenN = 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ù)據(jù)是完全隨機(jī)的，分支預(yù)測則毫無用處因為它不能預(yù)測隨機(jī)數(shù)據(jù)。這種情況下可能會有50%的錯誤預(yù)測。

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)

那這種情況下該怎么做呢？

如果編譯器不能將分支優(yōu)化為有條件的移動，這時候可以嘗試一些 Hacks ，如果能夠可以犧牲可讀性的表現(xiàn)。

將下面代碼

if (data[c] >= 128) sum += data[c];

替換為：

int t = (data[c] - 128) >> 31; sum += ~t & data[c];

用一些按位操作取代分支判斷，這樣就去除了分支。（注意：這個 hacks 并不是和if語句嚴(yán)格相等，但是在我們這個例子里，對輸入數(shù)組data的所有值都是正確的）

Benchmarks: Core i7 920 @ 3.5 GHz

C++ – Visual Studio 2010 – x64 Release

// Branch - Randomseconds = 11.777 // Branch - Sortedseconds = 2.352 // Branchless - Randomseconds = 2.564 // Branchless - Sortedseconds = 2.587

Java – Netbeans 7.1.1 JDK 7 – x64

// Branch - Randomseconds = 10.93293813 // Branch - Sortedseconds = 5.643797077 // Branchless - Randomseconds = 3.113581453 // Branchless - Sortedseconds = 3.186068823

觀察可得：

• 在分支情況下：排序數(shù)組和亂序數(shù)組之間的結(jié)果有著巨大的差異。

• 在 Hack 方式下：對于排序和亂序的結(jié)果則沒有差異。

• 在C++中，對于排序數(shù)組，Hack 會比分支有一點點慢。

一般的經(jīng)驗法則是避免數(shù)據(jù)依賴分支在一些特殊的循環(huán)中。

64位機(jī)器下，GCC 4.6.1附帶選項-O3或者-ftree-vectorize可以產(chǎn)生一個條件移動。因此對于有序和亂序數(shù)據(jù)都是一樣快。

VC++2010不能夠產(chǎn)生條件移動對于這樣的分支。

英特爾編譯器11同樣可以做一些神奇的事。它通過互換兩個循環(huán)，從而提升了不可預(yù)測的分支外循環(huán)。因此，它不但能夠避免誤預(yù)測，而且速度上可以達(dá)到VC++和GCC的兩個快。換句話說，ICC利用了測試回路打破了benchmark。

如果用英特爾編譯器執(zhí)行沒有分支的代碼，它僅僅出右向量化(out-right vectorizes it)，并且和帶分支同樣快。

通過上面說明，即使比較成熟的現(xiàn)代編譯器在優(yōu)化代碼的上可以有很大的不同。

樹莓派Pico：僅4美元的MCU

嵌入式Linux開發(fā)板裸機(jī)程序燒寫方法總結(jié)

國產(chǎn)16位MCU的痛點，可以用這款物美價廉產(chǎn)品