java - 奇怪的分支性能

Question

我的基准测试结果表明，当分支的概率为 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 时，时间突然下降（性能提高）。

有关下降的更多详细信息。改变种子表明发生了更多奇怪的事情。请注意，表示最小值和最大值的黑线非常短，除非靠近悬崖。

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

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

• 边界检查通过一个无符号比较最佳地完成。
• 它完全是多余的，因为 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

使用条件移动指令。这是多一条指令，但没有分支，因此没有分支预测错误的惩罚。

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

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