java for 循环中的分支预测

Question

我在 if 条件旁边看到了这条评论：

// branch prediction favors most often used condition

源代码中的JavaFX SkinBase class.

protected double computeMinWidth(double height, double topInset, double rightInset, double bottomInset, double leftInset) {

    double minX = 0;
    double maxX = 0;
    boolean firstManagedChild = true;
    for (int i = 0; i < children.size(); i++) {
        Node node = children.get(i);
        if (node.isManaged()) {
            final double x = node.getLayoutBounds().getMinX() + node.getLayoutX();
            if (!firstManagedChild) {  // branch prediction favors most often used condition
                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x + node.minWidth(-1));
            } else {
                minX = x;
                maxX = x + node.minWidth(-1);
                firstManagedChild = false;
            }
        }
    }
    double minWidth = maxX - minX;
    return leftInset + minWidth + rightInset;
}

我相信开发者想解释他为什么要写一个negate if。

这个优化真的有用吗？

Answer 1

可以找到一篇关于分支预测的非常详细的文章here

回答你的问题 - 据我了解，没有。我认为否定 "if" 不会有任何不同。它将优化重复假值的条件，就像重复多个真值一样。

Answer 2

JavaFX 团队的成员非常关注性能，因此他们肯定知道切换 if 和 else 对分支预测没有 material 影响。

我想这表明重构没有显着的性能改进：

double minX = Double.MAX_VALUE;
double maxX = Double.MIN_VALUE;

for (int i = 0; i < children.size(); i++) {
  Node node = children.get(i);
  if (node.isManaged()) {
    final double x = node.getLayoutBounds().getMinX() + node.getLayoutX();
    minX = Math.min(minX, x);
    maxX = Math.max(maxX, x + node.minWidth(-1));
  }
}

因为分支预测实质上会将 if/else 变成适合您的东西（给予或接受）。

This commit 证实了这个解释，虽然我不确定他们为什么改变它 - 可能是因为当 isManaged 条件永远不成立时它有副作用...

进一步调查，提交指的是a bug "up to 50% performance regression in Controls benchmarks"（您需要登录才能访问它）。

他们似乎遇到了性能问题，并且在调查时注意到代码中存在错误（类似于我上面的示例）。他们修复了这个错误并添加了一条评论来澄清由于分支预测，该修复不会影响性能。

摘录：

[..] looking at the code, I noticed an error in the case where none of the skin's children are managed. In such a case, minX/Y and maxX/Y would end up being MAX/MIN_VALUE where we really want them to be zero. So this change set fixes that issue. In testing, I saw a small (~1 fps) improvement in performance, so I don't think this change fixes the performance problem. Regardless, the code must be the way it is.

[...] Note that there was a bug in the use of MIN/MAX - those values are not the largest and smallest values for Float and Double (that would have made sense wrt symmetry with the integral types, but it isn't the way they were specified). For doing min/max operations on floating point values you want to use the NEGATIVE/POSITIVE_INFINITY values instead to achieve the results you are looking for.

Answer 3

句子“分支预测有利于最常用的条件”并没有说明评估条件的价值，无论是积极的还是消极的。它只是说分支预测可能有助于更频繁使用的条件分支，即循环中的条件分支。所以它基本上说，在循环中使用 if 是可以的。

虽然结论是正确的，但你不应该担心循环中的 ifs（你不应该担心任何事情，除非分析器告诉你存在瓶颈），句子本身是在 Java.

的上下文中毫无意义

分支预测是一个 CPU 功能，因此在解释执行中它与 Java 级分支无关，因为它们只是修改解释器的状态（即读取下一条指令的指针）但与特定分支的 CPU 指令无关。

HotSpot 启动后，情况就完全不同了。如果这段代码是一个热点，优化器将应用大量代码转换，这使得大多数关于 Java 代码将如何执行的假设都是错误的。

一个常见的优化是循环展开。不是用一个代码块来表示循环体，而是会有多个实例相互跟随，针对它们特定迭代的不变量进行优化。此设置允许完全省略 if 相关分支，因为完全可以预测，在 firstManagedChild 从 true 到 false 的第一次转换之后，它将永远不会返回，因此虽然第一次迭代总是看到它的 true 值，但可以优化后续迭代的代码以将变量视为常量 false.

所以在那种情况下，分支预测将再次没有意义，因为对于结果可以提前预测的 if 语句将没有分支。

Answer 4

除了现有的答案：

此评论似乎不是 "negate if" 的理由（因为这无论如何都不会对性能产生影响）。相反，这可能是 而不是 尝试 "optimize" 代码并避免单个 if 的理由。这可以通过这样的方式实现：

protected double computeMinWidth(double height, double topInset, 
    double rightInset, double bottomInset, double leftInset) {

    double minX = 0;
    double maxX = 0;

    // Initialize minX/maxX with the coordinate of the FIRST managed child
    int i = 0;
    for (i = 0; i < children.size(); i++) {
        Node node = children.get(i);
        if (node.isManaged()) {
            final double x = node.getLayoutBounds().getMinX() + node.getLayoutX();
            minX = x;
            maxX = x + node.minWidth(-1);
        }
    }

    // Continue the loop at the last index, updating the
    // minX/maxX with the remaining managed children
    for (; i < children.size(); i++) {
        Node node = children.get(i);
        if (node.isManaged()) {
            final double x = node.getLayoutBounds().getMinX() + node.getLayoutX();

            // Don't have to check whether it's the first managed child here. 
            // Just do the update.

            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x + node.minWidth(-1));
        }
    }
    double minWidth = maxX - minX;
    return leftInset + minWidth + rightInset;
}

评论指出，由于保存了 if，这不会带来任何性能优势，因为由于分支预测，这个 if 实际上实际上是免费的。

_{旁注：我认为可能还有其他 "microoptimizations"，例如 avoiding Math#min(double,double)。但是 JavaFX 的人（希望）知道他们的东西，如果这可能会对他们的情况产生影响，他们可能会这样做）}

java for 循环中的分支预测

Branch prediction in a java for loop

java

javafx

java-8

branch-prediction