來源于stackoverflow上的一個問題為什么處理有序陣列比處理無需陣列快，原文中已經有了一些探討，這里我們首先來復現下結果，然后再解釋下為什么！
我們有如下兩段代碼，代碼看起來都是差不多的，實際上邏輯也是一樣的，都是統計陣列中小于THRESHOLD數的個數，唯一的區別是一個是在無序陣列中統計，另一個是在有序陣列中統計，如果兩個陣列資料源是一致的（陣列大小、資料都是一致的），只是一個無序一個有序，你覺得兩個函式的性能差距會有多大？
public static void countUnsortedArr() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
if (arr[i] < THRESHLOD) {
cnt++;
}
}
}
public static void countSortedArr() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
if (arrSotred[i] < THRESHLOD) {
cnt++;
}
}
}
直覺上，兩段代碼的邏輯完全一樣，因為資料源一致統計結果也是一致的，所以性能上不會有什么差異，但真的是這樣嗎？我們用OpenJdk中的基準測驗工具JMH來測驗下，
測驗環境
MacBook Pro (13-inch, 2017)
CPU: 2.5 GHz Intel Core i7
JMH version: 1.21
VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28
測驗方式：預熱一輪，然后對每個函式做三輪的壓測，每輪都是10s
結果如下，SCore表示執行一次這個函所需要的微秒數，數值越小性能越高，
Benchmark Mode Cnt Score Error Units
BranchPredictionTest.countSortedArr avgt 3 5212.052 ± 7848.382 us/op
BranchPredictionTest.countUnsortedArr avgt 3 31854.238 ± 5393.947 us/op
是不是很出乎意料，明顯有序陣列中統計快的多，性能差距足足有 6倍 ，而且經過我多次測驗，這個性能差距非常穩定，是不是感覺不符合邏輯，大多數程式猿都是用高級語言撰寫代碼，其實語言本身就封裝了很多底層的細節，事實上，CPU對分支跳轉指令是有優化的，這就是我們標題中提到的CPU分支預測，在詳細分支預測前先申明一句，本文目標不是講清楚分支預測，而是告訴你分支預測對性能的影響，想了解更多關于CPU分支預測的內容，文末列出了幾篇參考資料，
要說分支預測，還得提到現代CPU的指令流水線模式，如上圖所示，現代CPU為了提升指令的吞吐率，將單個指令切分成多個階段，大致分為__取指(fetch)，譯碼(decode)，執行(execute)，回寫(write-back)__，一條指令不必等上一條完全執行完成就可以開始執行了，就好比工廠中的流水線，可以大大提升指令執行的吞吐率，現代CPU實際上不止4個階段，像intel和arm的處理器基本上都有十多個階段，流水線吞吐率的優勢更加明顯，
但理想很美好，顯示很骨干，不是說所有的指令多可以再上一條指令執行完成前就開始執行，可能這條指令會依賴上一條指令的執行結果，為了應對這種資料依賴情況下導致到吞吐率下降，CPU的設計者提出了好多優化方式，比如指令冒險,指令亂序執行,預測，我們今天提到的__分支預測__就屬于“預測”的一種，
分支預測的思路也很簡單，既然依賴的資料還沒算出來，那我就猜一個結果，然后提前開始執行指令，當然也不是隨機猜測，現代CPU的預測思路是看前幾次預測的結果，就好比前天下雨、昨天也下雨，那我可以簡單粗暴的認為今天也下雨，具體細節見文末參考資料，思路很簡單，但效果卻出奇的好，從Wikipedia的資料我們可以知道現代CPU的分支預測準確率可以到90%以上，
既然準確率不是100%，就意味著有失敗的時候，如果CPU發現預測錯誤會把所有預測之后的指令執行結果全部拋棄，然后從預測分支那重新開始執行，相當于很多指令白跑了，預測失敗的代價很高，正常一條指令執行需要10-20個指令周期，預測失敗的話可能額外多出30-40個指令周期， 回到我們上面的測驗代碼，我準備的資料是100w個從0-100w之間的數，然后統計小于50w的數的個數，無序的情況下相當于會有50%的可能性分支預測失敗，有序情況下100w次預測只會有一次失敗，分支預測失敗就是產生性能差距的原因，
性能優化
知道了原因，如何優化性能？既然有序陣列最快，是不是我們直接將陣列排序，然后做遍歷就行？別忘了，額外做排序帶來的性能損失遠超過分支預測失敗帶來的性能損失，既然提升分支預測成功率的方式行不通我們就干脆直接干掉會導致分支預測的邏輯，How?
優化1
對于我這個簡單的統計邏輯，可以直接用位運算來完成，位運算看著復雜，但其實思路很簡單，就是將整數的符號位直接轉化成0和1，再加到cnt上，沒有了if小于判斷，生成的指令里也就沒有了jmp指令，從而避免CPU分支預測錯誤導致的性能消耗，
代碼如下：
@Benchmark
public static void count1() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
cnt += (-~(THRESHLOD-arr[i]) >> 31);
}
}
優化2
既然我都對位運算標了優化1，那肯定還有優化2，事實上用 ? : 三目運算子也能優化性能，
public static void count2() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
cnt += arr[i] < THRESHLOD ? 1 : 0;
}
}
我們把四種方式放一起再看一下性能差距，位運算毫無疑問是最快的，使用?:三目運算子的方式也相當快，和有序資料統計差不多，可以確定三目運算子也成功避免了分支預測錯誤代碼來的性能損失，
Benchmark Mode Cnt Score Error Units
BranchPredictionTest.count1 avgt 3 3807.000 ± 16265.107 us/op
BranchPredictionTest.count2 avgt 3 4706.082 ± 19757.705 us/op
BranchPredictionTest.countSortedArr avgt 3 4458.783 ± 107.975 us/op
BranchPredictionTest.countUnsortedArr avgt 3 30719.090 ± 4517.611 us/op
?:三目運算為什么這么快?
?:運算式里有有小于判斷，為什么就沒有分支跳轉了？這個問題我也疑惑了好久，后來我用C語言代碼生成了if和?:邏輯的匯編代碼，終于發現了其中的不同，
C代碼
int fun1(int x)
{
int cnt = 0;
if (x < 0)
{
cnt += 1;
}
return cnt;
}
int fun2(int x)
{
int cnt = 0;
cnt += x > 0 ? 1 : 0;
return cnt;
}
匯編代碼
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 10, 14
.globl _fun1 ## -- Begin function fun1
.p2align 4, 0x90
_fun1: ## @fun1
.cfi_startproc
## %bb.0:
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
movl %edi, -4(%rbp)
movl $0, -8(%rbp)
cmpl $0, -4(%rbp)
jge LBB0_2 ## 如果cmpl指令判斷的結果是大于等于，就跳轉到LBB0_2代碼塊
## %bb.1:
movl -8(%rbp), %eax
addl $1, %eax
movl %eax, -8(%rbp)
LBB0_2:
movl -8(%rbp), %eax
popq %rbp
retq
.cfi_endproc
## -- End function
.globl _fun2 ## -- Begin function fun2
.p2align 4, 0x90
_fun2: ## @fun2
.cfi_startproc
## %bb.0:
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
xorl %eax, %eax
movl %edi, -4(%rbp)
movl $0, -8(%rbp)
movl -4(%rbp), %edi
cmpl $0, %edi
movl $1, %edi
cmovll %edi, %eax
addl -8(%rbp), %eax
movl %eax, -8(%rbp)
movl -8(%rbp), %eax
popq %rbp
retq
.cfi_endproc
## -- End function
.subsections_via_symbols
從匯編代碼可以看出，fun2中沒有jge指令(jump when greater or equal)，這是一個典型的跳轉指令，它會根據cmpl指令的結果來跳轉到某個代碼塊，上文已經提到了，CPU只有在跳轉指令時才會做分支預測，而?:的實作完全不同，雖然也有cmpl指令，后面跟的是cmovll指令，這個指令會根據cmp的結果把值放到%eax暫存器中，后續所有的指令都是串行執行的，完全沒有跳轉指令，所以不會出現分支預測失敗導致的性能損失，
和我之前想象的不太一樣，跳轉指令不是大小比較產生的，而是像if for這種邏輯分叉產生的，條件跳轉只是依賴大小比較的結果而已，
完整基準測驗代碼：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
@Fork(3)
@Warmup(iterations = 1)
@Measurement(iterations = 3)
public class BranchPredictionTest {
private static Random random = new Random();
private static int MAX_LENGTH = 10_000_000;
private static int[] arr;
private static int[] arrSotred;
private static int THRESHLOD = MAX_LENGTH >> 1;
@Setup
public static void init() {
arr = new int[MAX_LENGTH];
for (int i = 0; i < MAX_LENGTH; i++) {
arr[i] = random.nextInt(MAX_LENGTH);
}
arrSotred = Arrays.copyOf(arr, arr.length);
Arrays.sort(arrSotred);
}
@Benchmark
public static void countUnsortedArr() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
if (arr[i] < THRESHLOD) {
cnt++;
}
}
}
@Benchmark
public static void countSortedArr() {
int cnt = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
if (arrSotred[i] < THRESHLOD) {
cnt++;
}
}
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(BranchPredictionTest.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
結語
CPU分支預測本身是為了提升流水線下避免流水線等待的手段，其實本質上是利用了區域性原理，因為區域性的存在，大多數情況下這個技術本身給性能帶來的是正向的(要不然它今天也不會存在了)，所以我們大多數情況下都不需要關注它的存在，還是放心大膽的寫代碼吧，不要因為我們這篇博客就把所有的if改成?:三目運算，可能對代碼可讀性的影響遠大于性能提升的收益，再次強調下，我今天只是構造了一個極端的資料來驗證其性能差異，因為區域性的存在大多數情況下分支預測都是對的，
最后，我還發現如果把上面基準測驗中所有的小于號改成大于號，所有的性能差異就都消失了，實際測驗結果如下，想不通，看起來是沒有分支預測了，有知道的大佬解釋下嗎？
Benchmark Mode Cnt Score Error Units
BranchPredictionTest.count1 avgt 3 3354.059 ± 3995.160 us/op
BranchPredictionTest.count2 avgt 3 4047.069 ± 2285.700 us/op
BranchPredictionTest.countSortedArr avgt 3 5732.614 ± 6491.716 us/op
BranchPredictionTest.countUnsortedArr avgt 3 5251.890 ± 64.813 us/op
參考資料
- 維基百科指令流水線
- 維基百科分支預測
- CPU分支預測
- 區域性原理
本文來自https://blog.csdn.net/xindoo
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/157151.html
標籤：Java