奇怪的分支performance

我的基准testing 结果显示，当分支有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; } 

它计算给定string中BREAKING_WHITESPACE字符的数量。 结果显示当分支概率达到约0.20时突然的时间下降（性能增加）。

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

Answer 1

它看起来像一个小小的JIT错误。 对于一个小的分支概率，它会产生类似下面的内容，由于展开而变得复杂得多（我简化了很多）：

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

获取char： int r9d = queries[r10]

 imul $0x8acbf29,%r9d,%ebx 

乘以： ebx = 145538857 * r9d

 shr $0x1b,%ebx 

Shift： 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循环开始： 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的正确阈值。