JVM常見概念之條件移動

問題

當我們有分支頻率數據時，有什么有趣的技巧可以做嗎？什么是條件移動？

基礎知識

如果您需要在來自一個分支的兩個結果之間進行選擇，那么您可以在 ISA 級別做兩件不同的事情。

首先，你可以創建一個分支：

    # %r = (%rCond == 1) ? $v1 : $v2cmp %rCond, $1jne Amov %r, $v1jmp EA: mov %r, $v2E:

其次，您可以執行依賴于比較結果的預測指令。在 x86 中，這采用條件移動 (CMOV) 的形式，當選定條件成立時執行操作：

# %r = (%rCond == 1) ? $v1 : $v2mov %r, $v1      ; put $v1 to %rcmp %rCond, ...cmovne %r, $v2   ; put $v2 to %r if condition is false

執行條件移動的優點是它有時會生成更緊湊的代碼，就像在這個例子中一樣，并且它不會受到可能的分支預測錯誤懲罰。缺點是它需要在選擇返回哪一邊之前計算兩邊，這可能會花費過多的 CPU 周期，增加寄存器壓力等。在分支情況下，我們可以選擇在檢查條件后不計算內容。預測良好的分支將優于條件移動。

因此，是否執行條件移動的選擇在很大程度上取決于其成本預測。這就是分支分析可以幫助我們的地方：它可以說出哪些分支可能沒有被完美預測，因此適合 CMOV 替換。當然，實際成本模型還包括我們正在處理的參數類型、兩個計算分支的相對深度等。

實驗

源碼-用例1

@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class BranchFrequency {@Benchmarkpublic void fair() {doCall(true);doCall(false);}@CompilerControl(CompilerControl.Mode.DONT_INLINE)public int doCall(boolean condition) {if (condition) {return 1;} else {return 2;}}
}

執行結果

我們在每次調用時都會在分支之間進行切換，這意味著它的運行時配置文件在它們之間大約是 50%-50%。如果我們通過提供 -XX:ConditionalMoveLimit=0 來限制條件移動替換，那么我們就可以清楚地看到替換的發生。

# doCall, out of box variant4.36%  ...4ac: mov    $0x1,%r11d         ; move $1 -> %r113.24%  ...4b2: mov    $0x2,%eax          ; move $2 -> %res8.46%  ...4b7: test   %edx,%edx          ; test boolean0.02%  ...4b9: cmovne %r11d,%eax         ; if false, move %r11 -> %res7.88%  ...4bd: add    $0x10,%rsp         ; exit the method8.12%  ...4c1: pop    %rbp18.60%  ...4c2: cmp    0x340(%r15),%rsp...4c9: ja     ...4d00.14%  ...4cf: retq# doCall, CMOV conversion inhibited6.48%    ...cac: test   %edx,%edx         ; test boolean╭  ...cae: je     ...cc8│                                   ; if true...│  ...cb0: mov    $0x1,%eax         ; move $1 -> %res7.41% │↗ ...cb5: add    $0x10,%rsp        ; exit the method0.02% ││ ...cb9: pop    %rbp27.43% ││ ...cba: cmp    0x340(%r15),%rsp││ ...cc1: ja     ...ccf3.28% ││ ...cc7: retq││                                  ; if false...7.04% ↘│ ...cc8: mov    $0x2,%eax         ; move $2 -> %res0.02%  ╰ ...ccd: jmp    ...cb5            ; jump back

在此示例中，CMOV 版本的表現稍好一些：

Benchmark                              Mode  Cnt   Score    Error  Units# Branches
BranchFrequency.fair                   avgt   25   5.422 ±  0.026  ns/op
BranchFrequency.fair:L1-dcache-loads   avgt    5  12.078 ±  0.226   #/op
BranchFrequency.fair:L1-dcache-stores  avgt    5   5.037 ±  0.120   #/op
BranchFrequency.fair:branch-misses     avgt    5   0.001 ±  0.003   #/op
BranchFrequency.fair:branches          avgt    5  10.037 ±  0.216   #/op
BranchFrequency.fair:cycles            avgt    5  14.659 ±  0.285   #/op
BranchFrequency.fair:instructions      avgt    5  35.184 ±  0.559   #/op# CMOVs
BranchFrequency.fair                   avgt   25   4.799 ±  0.094  ns/op
BranchFrequency.fair:L1-dcache-loads   avgt    5  12.014 ±  0.329   #/op
BranchFrequency.fair:L1-dcache-stores  avgt    5   5.005 ±  0.167   #/op
BranchFrequency.fair:branch-misses     avgt    5  ≈ 10??            #/op
BranchFrequency.fair:branches          avgt    5   7.054 ±  0.118   #/op
BranchFrequency.fair:cycles            avgt    5  12.964 ±  1.451   #/op
BranchFrequency.fair:instructions      avgt    5  36.285 ±  0.713   #/op

您可能認為這是因為 CMOV 沒有分支預測失誤懲罰，但這種解釋與計數器不一致。請注意，在兩種情況下，“分支失誤”幾乎為零。這是因為硬件分支預測器實際上可以記住一個短暫的分支歷史，而這種反復出現的分支對它們來說沒有任何問題。性能差異的實際原因是分支情況下的跳躍：我們在關鍵路徑上有一條額外的控制流指令。

源碼-用例2

@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Thread)
public class AdjustableBranchFreq {@Param("50")int percent;boolean[] arr;@Setup(Level.Iteration)public void setup() {final int SIZE = 100_000;final int Q = 1_000_000;final int THRESH = percent * Q / 100;arr = new boolean[SIZE];ThreadLocalRandom current = ThreadLocalRandom.current();for (int c = 0; c < SIZE; c++) {arr[c] = current.nextInt(Q) < THRESH;}// Avoid uncommon traps on both branches.doCall(true);doCall(false);}@Benchmarkpublic void test() {for (boolean cond : arr) {doCall(cond);}}@CompilerControl(CompilerControl.Mode.DONT_INLINE)public int doCall(boolean condition) {if (condition) {return 1;} else {return 2;}}
}

執行結果

使用不同的 percent 值和 -prof perfnorm JMH 分析器運行它將產生以下結果：
在這里插入圖片描述依據上圖，你可以清楚地看到幾件事：

每個測試的分支數約為 5，而 CMOV 轉換將其降至 4。這與之前的反匯編轉儲相關：我們將測試中的一個分支轉換為 CMOV。另外 4 個分支來自測試基礎設施本身。
如果沒有 CMOV，分支測試性能會受到影響，在 50% 的分支概率下會變得最差。這個峰值反映了硬件分支預測器幾乎完全混亂，因為它每次操作都會遇到大約 0.5 次分支失誤。這意味著分支預測器并不是一直猜錯（這太荒謬了！），而只是一半的時間猜錯。我推測基于歷史的預測器會放棄，讓靜態預測器選擇最近的分支，而我們只選擇了一半的時間。
使用 CMOV 后，我們可以看到操作時間幾乎持平。該圖表明 CMOV 成本模型對于此測試來說可能過于保守，并且切換得有點晚。這并不一定意味著它有錯誤，因為其他情況的表現很可能會有所不同。盡管如此，當進行 CMOV 轉換時，對分支情況的改進是巨大的。
您可能會注意到，當分支預測準確率為 >97% 時，分支變體會低于 CMOV 中間平均值。當然，這又是測試、硬件、虛擬機特有的事情。

總結

分支分析允許在執行概率敏感指令選擇時做出或多或少明智的選擇。條件移動替換通常使用分支頻率信息來驅動替換。這再次強調了使用與真實數據類似的數據來預熱 JIT 編譯代碼的必要性，以便編譯器能夠針對特定情況進行有效優化。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/898889.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/898889.shtml
英文地址，請注明出處：http://en.pswp.cn/news/898889.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！