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

以下是正文

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

由于某些怪異的原因，下面這段C++代碼表現(xiàn)的異乎尋?！?當(dāng)這段代碼作用于有序數(shù)據(jù)時(shí)其速度可以提高將近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) 去掉，這段代碼耗時(shí)11.54秒。

  
  

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

  
  

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

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); }}

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

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

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

  
  

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

  
  

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

?

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

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

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

考慮一個(gè)鐵路樞紐：

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

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

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

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

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

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

  
  

• 如果猜錯(cuò)了，列車長(zhǎng)會(huì)讓火車停下來，并后退，然后告訴你正確的方向，然后火車重新啟動(dòng)開往正確的方向。

考慮一個(gè)if語(yǔ)句：在處理器級(jí)別上，他是一個(gè)分支指令：

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

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

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

  
  

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

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

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

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

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

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

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

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

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

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

這是非常有好的分支預(yù)測(cè)因?yàn)榉种?huì)連續(xù)多次執(zhí)行相同的分支。即使是一個(gè)簡(jiǎn)單的飽和計(jì)數(shù)器也會(huì)預(yù)測(cè)正確除去當(dāng)變換方向后的少數(shù)幾個(gè)。

快速可視化

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ù)測(cè)則毫無(wú)用處因?yàn)樗荒茴A(yù)測(cè)隨機(jī)數(shù)據(jù)。這種情況下可能會(huì)有50%的錯(cuò)誤預(yù)測(cè)。

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)化為有條件的移動(dòng)，這時(shí)候可以嘗試一些 Hacks ，如果能夠可以犧牲可讀性的表現(xiàn)。

將下面代碼

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

替換為：

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

用一些按位操作取代分支判斷，這樣就去除了分支。（注意：這個(gè) hacks 并不是和if語(yǔ)句嚴(yán)格相等，但是在我們這個(gè)例子里，對(duì)輸入數(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 方式下：對(duì)于排序和亂序的結(jié)果則沒有差異。

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

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

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

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

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

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

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

樹莓派Pico：僅4美元的MCU

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

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