java - 奇怪的分支性能

Question

results我的benchmark表明当分支的概率为 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的数量给定字符串中的字符。结果显示，当分支概率达到约 0.20 时，时间突然下降(性能提高)。

更多 details关于下降。 Varying the seed显示更多奇怪的事情正在发生。请注意，表示最小值和最大值的黑线非常短，除非靠近悬崖。

Answer 1

它看起来像一个小的 JIT 错误。对于较小的分支概率，它会生成如下内容，只是由于展开而复杂得多(我正在简化很多):

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

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

imul   $0x8acbf29,%r9d,%ebx

乘:ebx = 145538857 * r9d

shr    $0x1b,%ebx

类次: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

只需 goto back

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

• 使用单个 unsigned comparison 即可以最佳方式完成边界检查。 .
• 这是完全多余的，因为 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

使用 conditional move操作说明。这多了一条指令，但没有分支，因此没有分支预测错误的惩罚。

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

因此，使用大约 0.04 而不是 0.18 的适当阈值看起来像是 JIT 失败。