奇怪的分支性能

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时，结果显示了突然的时间下降（性能增加）。

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

- maaartinus

---

我感觉有个连续踩问题的人，甚至可能有两个。如果你有意见，请在评论中说明问题所在，不要讲解释。 - maaartinus

我认为我喜欢这个问题。我对答案很感兴趣。 - Pankaj

请给出下投票者的原因解释..!! - akki0996

可能是因为代码是链接而不是直接发布，并且没有任何上下文信息。这只是我的猜测。 - Durandal

@Vivin Paliath：你能重现我的结果吗？我已经尝试了不同的种子和一切……看起来JIT做错了，你能确认一下吗？ - maaartinus

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%以下的斜坡明显是由于分支预测错误造成的。

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

- maaartinus

---

非常有趣。但我认为你关于这是JIT故障的结论是错误的 - 考虑你一遍又一遍地运行相同的方法，但JIT可能只基于热身阶段做出决策。由于你基准测试的结构，你引诱JIT假设一个基于热身的分支比率，这并不真正代表真实分布。至于数组边界检查是否多余，对于一个索引表达式来说，它将保持在某些范围内可能是一个非常困难的问题，无法通用证明。 - Durandal

@Durandal：但是预热阶段非常长，当尝试不同的种子时，同样的事情发生了。如果它不具有代表性，JIT也必须在另一个方向上出错，但这从未发生过。 - maaartinus

@Durandal：我同意一般来说这很难，但在这里它相当简单。y == x >>> 27 意味着 y < 32，就像 y = z && 31 一样。这种移位可能不够常见，以至于实现者们不会关心，但通常比掩码更好。 - maaartinus

@Durandal：这更加复杂：有分层编译和定期采样线程堆栈的分析，所以你无法在代码中看到它。将位向下移动允许您从乘法中获取最佳位，而乘法是最佳位扩展操作。在这种特殊情况下，我看不到使用掩码的任何同样快速的解决方案。一般来说，在计算hashCode的索引时，我建议进行类似的处理。 - maaartinus

@maaartinus 但是分层编译默认是关闭的吗？它会直接从字节码转换为C2代码。我也从未听说过通过异步堆栈分析进行剖析。我熟悉的所有情况都涉及监视特定的调用站点、循环等，剖析代码会被解释器明确地分支到代码中的特定点。 - Marko Topolnik