奇怪的分支性能

performance java

2022-09-02 04:45:12

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

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

cliff

答案 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 somewhereIndexOutOfBoundsException

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失败。

thr

答案 2