java - 代码优化以避免分支

Question

我刚刚看到这篇文章:Compute the minimum or maximum of two integers without branching

它始于“[o]在一些稀有机器上，其中分支是昂贵的...”。

我曾经认为分支总是很昂贵，因为它经常迫使处理器清除并重新启动其执行管道(例如，参见 Why is it faster to process a sorted array than an unsorted array?)。

这给我留下了几个问题:

• 文章的作者是否弄错了那部分？或者这篇文章可能是在分支成为问题之前的某个时间写的(我找不到它的日期)。
• 现代处理器是否有办法像 (x < y) ? x : y 中那样完成最少的分支？没有性能下降？
• 或者所有的现代编译器都只是自动实现这个 hack 吗？具体来说，Java是做什么的？特别是因为它 Math.min(...) 函数就是那个三元语句...

Answer 1

Did the writer of the article get that part wrong? Or was this article maybe written in a time before branching was an issue (I can't find a date on it).

最老的评论是 5 年前的，所以不是热点新闻。然而，不可预测的分支总是代价高昂的，5 年前也是如此。与此同时，情况变得更糟，因为现代 CPU 每个周期可以做更多的事情，而错误预测的分支因此会花费更多的工作。

但从某种意义上说，作者是对的。大多数 CPU 不在我们的 PC 和服务器中，而是在嵌入式设备中，情况有所不同。

Do modern processors have a way to complete minimal branches like the one in (x < y) ? x : y without performance degradation?

是也不是。 AFAIK Math.max 总是被翻译成条件移动，这意味着没有分支。您拥有的 max 可能会或可能不会使用它，具体取决于 JVM 收集的统计信息。

没有 Elixir 。有了可预测的结果，分支就会更快。准确地找出 CPU 识别的模式是很困难的。 JVM 只查看分支获取的频率，并使用大约 18% 的神奇阈值。看我自己question and answer了解详情。

Or do all modern compilers simply implement this hack automatically? Specifically, what does Java do? Especially since its Math.min(...) function is just that ternary statement...

它实际上是一个编译器内在的。每当 JITc 看到这个方法被调用时，它都会专门处理它。当您复制该方法时，它不会得到任何特殊处理。

在这种情况下，内在函数不是很有用，因为无论如何它都会被大量优化。对于像 Long#numberOfLeadingZeros 这样的方法，内在函数是必不可少的，因为 code相当长而且很慢，现代 CPU 可以在一个周期内完成。