一文告訴你CPU分支預測對性能影響有多大

來源於stackoverflow上的一個問題為什麼處理有序數組比處理無需數組快，原文中已經有了一些探討，這裡我們首先來複現下結果，然後再解釋下為什麼！我們有如下兩段代碼，代碼看起來都是差不多的，實際上邏輯也是一樣的，都是統計數組中小於THRESHOLD數的個數，唯一的區別是一個是在無序數組中統計， ...

來源於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分支預測的內容，文末列出了幾篇參考資料。
![在這裡插入圖片描述](https://img-blog.csdnimg.cn/20190930115912874.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly94aW5kb28uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70 =400x)
要說分支預測，還得提到現代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

參考資料

本文來自https://blog.csdn.net/xindoo