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

時間：2021-02-23 09:56:55

關(guān)鍵字： C 代碼嵌入式

手機看文章

掃描二維碼
隨時隨地手機看文章

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

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

以下是正文

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

由于某些怪異的原因，下面這段C++代碼表現(xiàn)的異乎尋常—-當這段代碼作用于有序數(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++中那么大，但是也有幾分相似。

對于上面的問題，我首先想的原因是排序可能會導致數(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)遠程或廣播通訊工具。

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

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

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

如果猜對了，火車繼續(xù)往前走；
如果猜錯了，列車長會讓火車停下來，并后退，然后告訴你正確的方向，然后火車重新啟動開往正確的方向。

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

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

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

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

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

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

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

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

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

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

從上面可以得到啟發(fā)，這個問題的“罪魁禍首”就是 if 語句

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

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

這是非常有好的分支預(yù)測因為分支會連續(xù)多次執(zhí)行相同的分支。即使是一個簡單的飽和計數(shù)器也會預(yù)測正確除去當變換方向后的少數(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ù)是完全隨機的，分支預(yù)測則毫無用處因為它不能預(yù)測隨機數(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語句嚴格相等，但是在我們這個例子里，對輸入數(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