奇怪的分支性能

The results https://microbenchmarks.appspot.com/runs/864b7017-da27-400b-a8e3-26fdd561a39d of my 基准 https://dl.dropboxusercontent.com/u/4971686/published/maaartin/so/BranchingBenchmark.java显示当分支的概率为 15%（或 85%）而不是 50% 时，性能最差。

有什么解释吗？

代码太长，但相关部分在这里：

private int diff(char c) {
    return TABLE[(145538857 * c) >>> 27] - c;
}

@Benchmark int timeBranching(int reps) {
    int result = 0;
    while (reps-->0) {
        for (final char c : queries) {
            if (diff(c) == 0) {
                ++result;
            }
        }
    }
    return result;
}

它计算的数量BREAKING_WHITESPACE http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/base/CharMatcher.html#BREAKING_WHITESPACE给定字符串中的字符。结果显示，当分支概率达到 0.20 左右时，时间突然下降（性能提高）。

More details https://microbenchmarks.appspot.com/runs/1a8ef79f-bab5-4e4e-824c-52e403636f04#r:scenario.benchmarkSpec.parameters.seed,scenario.benchmarkSpec.parameters.fractionMatching关于掉落。改变种子 https://microbenchmarks.appspot.com/runs/1a8ef79f-bab5-4e4e-824c-52e403636f04#r:scenario.benchmarkSpec.parameters.fractionMatching,scenario.benchmarkSpec.parameters.seed表明更多奇怪的事情正在发生。请注意，除非靠近悬崖，否则表示最小值和最大值的黑线非常短。

它看起来像是一个小的 JIT bug。对于较小的分支概率，它会生成如下所示的内容，只是由于展开而变得更加复杂（我简化了很多）：

movzwl 0x16(%r8,%r10,2),%r9d

获取字符：int r9d = queries[r10]

imul   $0x8acbf29,%r9d,%ebx

乘：ebx = 145538857 * r9d

shr    $0x1b,%ebx

Shift: ebx >>>= 27

cmp    %edx,%ebx
jae    somewhere

检查边界：if (ebx > edx || ebx < 0) goto somewhere（并在那里扔一个IndexOutOfBoundsException.

cmp    %r9d,%ebx
jne    back

如果不相等则跳回循环开头：if (r9d != ebx) goto back

inc    %eax

增加结果：eax++

jne    back

Simply goto back

我们可以看到一件聪明的事情和一件愚蠢的事情：

• 绑定检查可以通过单个最佳方式完成无符号比较 http://www.aldeid.com/wiki/X86-assembly/Instructions/jae.
• 它完全是多余的，因为 x >>> 27 始终为正数并且小于表长度 (32)。

对于高于 20% 的分支概率，这三个指令

cmp    %r9d,%ebx
jne    back
inc    %eax

被类似的东西取代

mov    %eax,%ecx   // ecx = result
inc    %ecx        // ecx++
cmp    %r9d,%ebx   // if (r9b == index)
cmoveq %ecx,%ebx   //    result = ecx

using a 有条件的移动 http://www.jaist.ac.jp/iscenter-new/mpc/altix/altixdata/opt/intel/vtune/doc/users_guide/mergedProjects/analyzer_ec/mergedProjects/reference_olh/mergedProjects/instructions/instruct32_hh/vc35.htm操作说明。这又是一条指令，但没有分支，因此没有分支错误预测惩罚。

这解释了 20-80% 范围内非常恒定的时间。低于 20% 的下降显然是由于分支预测错误造成的。

因此，看起来 JIT 未能使用大约 0.04 而不是 0.18 的正确阈值。