C++性能榨汁機之分支預測器(4)

06-07

C++性能榨汁機之分支預測器(4)

來自專欄 C++性能榨汁機

前言

在上篇文章中，我們通過分析一段典型程序的彙編級代碼更加清楚的看到了分支預測對程序性能的影響，當數據對分支預測器預測不友好的時候，我們的程序性能下降巨大。那麼，怎麼才能避免分支預測頻繁出錯對我們程序運行的不利影響呢？

用條件傳送替代條件控制轉移

分支預測對有規律的分支跳轉可以實現非常高的預測正確率，比如在循環判斷中，在循環終止之前，分支預測都可以基本保證完全的預測正確，預測錯誤只會出現在最後跳出循環的條件滿足時。但是，對於每次跳轉結果都不確定的分支判斷，分支預測率的預測正確率就很低了，可能只有50%左右，基本相當於每次都隨機猜測，這樣的情況下，流水線會經常被打斷，影響程序性能。對於這種嚴重依賴於數據的分支跳轉命令，最好的替代方法就是條件傳送指令。

在使用條件傳送的條件下，命令中是沒有跳轉命令的，也就避免了使用分支預測器去預測一個很難預測的分支。

如何寫條件傳送代碼？

對於C和C++這樣的高級語言是沒有提供控制底層實現到底是使用條件控制轉移指令還是條件傳送指令的功能的，底層命令實現靠編譯器實現。但是，我們可以通過我們寫代碼的具體方法去間接影響編譯器生成的彙編代碼，從而達到使用條件傳送命令替代條件控制轉移命令的目的。

下面的C++代碼經過編譯器編譯後生成的彙編代碼是通過條件控制轉移命令實現分支跳轉的（我們在上一篇文章中已經就此代碼進行了分析）：

for(unsigned c = 0; c < arraySize; ++c){ if(data[c] >= 128){ sum += data[c]; }}

上述代碼的彙編代碼：

.L8: movl $0, -131104(%rbp).L7: cmpl $32767, -131104(%rbp) ja .L5 movl -131104(%rbp), %eax movl -131088(%rbp,%rax,4), %eax cmpl $127, %eax jle .L6 movl -131104(%rbp), %eax movl -131088(%rbp,%rax,4), %eax cltq addq %rax, -131096(%rbp).L6: addl $1, -131104(%rbp) jmp .L7

其中jle .L6就是條件控制轉移指令，當數據隨機的時候，此命令的整體效率會極大降低。

但如果我們使用下面C++代碼實現上面程序同樣的功能的話，就可以避免產生條件控制轉移指令：

for(unsigned c = 0; c < arraySize; ++c){ int t = (data[c] - 128) >> 31; sum += ~t & data[c];}

上述C++代碼首先使用一個減法和移位獲取data[c]與128比較的結果，如果data[c] >= 128，則t的所有位為0，否則t的所有位為1，然後將t取非操作並於data[c]做與操作，以決定累加到sum上的數據是0還是data[c]。產生的彙編代碼如下：

.L6: cmpl $32767, -131108(%rbp) ja .L5 movl -131108(%rbp), %eax movl -131088(%rbp,%rax,4), %eax addl $-128, %eax sarl $31, %eax movl %eax, -131100(%rbp) movl -131100(%rbp), %eax notl %eax movl %eax, %edx movl -131108(%rbp), %eax movl -131088(%rbp,%rax,4), %eax andl %edx, %eax cltq addq %rax, -131096(%rbp) addl $1, -131108(%rbp) jmp .L6

可以看到，上述彙編代碼完整實現了我們C++代碼的思路，而且沒有產生分支控制跳轉命令，我們通過一些hack技巧實現了條件傳送命令替代條件控制跳轉命令，這樣的代碼對於任何數據表現都是一樣的，即程序的性能不會因為輸入數據的隨機與否而變化。

經過測試，修改過後的程序比隨機數據＋條件控制跳轉程序提高了３倍，而且性能表現對於可預測數據和隨機數據均一致。

第一個花費時間7.42568秒是程序在隨機數據上的表現結果，第二個花費時間7.4234秒是程序在排序後數據上的表現結果，可以看多兩者表現相差可以忽略不計，可以說更改後的程序達到了性能與輸入數據無關的目的。

總結

上面代碼將條件控制轉移指令轉換成了條件傳送代碼，但是，代碼的可讀性急劇下降，int t = (data[c] - 128) >> 31; sum += ~t & data[c];這句代碼很難讓人一眼看出代碼的目的，這種代碼會對整個項目的維護帶來巨大麻煩。

所以，在現代處理器和現代編譯器的幫助下，千萬不要過度關心分支預測帶來的影響，對於程序中大部分分支命令，分支預測器都可以有很高的預測正確率，而對於那些分支預測器很難預測的分支，現代編譯器可以對其進行自動優化，比如gcc中開啟-O3優化的時候，編譯器會自動把條件跳轉轉為條件傳送以提高程序運行效率。

大部分情況下，請相信處理器、相信編譯器！有在完全確定了程序的性能瓶頸所在的時候再去針對這部分代碼做特殊優化，避免提前優化和過度優化。