奇怪的分支表现

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 bug.对于小分支概率,它会产生类似下面的内容,因为展开会更加复杂(我简化了很多):

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

获取char: 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%的增长显然是由于分支机构的错误预测.

所以看起来JIT没有使用大约0.04而不是0.18的正确阈值.