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 中间平均值。当然，这又是测试、硬件、虚拟机特有的事情。