Branch prediction in a java for loop

Question

I saw this comment next to a if condition:

// branch prediction favors most often used condition

in the source code of the 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;
}

I believe that the developer want to explain why he wrote a negate if.

is this optimization really useful ?

Answer 1

The guys of the JavaFX team are pretty focused on performance so they surely know that switching the if and the else has no material effect on branch prediction.

I imagine that it is an indication that there is no significant performance improvement to refactor as:

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));
  }
}

Because branch prediction will essentially turn the if/else into something like that for you (give or take).

---

This commit confirms this explanation, although I'm not sure why they changed it - possibly because it had side effects when the isManaged condition was never true...

Investigating further, the commit refers to a bug "up to 50% performance regression in Controls benchmarks" (you need to login to access it).

It seems that they had a performance issue and while investigating noticed that there was a bug in the code (that was similar to what my example above). They fixed the bug and added a comment to clarify that the fix did not affect performance thanks to branch prediction.

Excerpts:

[..] 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 2

The sentence “branch prediction favors most often used condition” doesn’t say anything about the value of the evaluated condition, be it positive or negative. It only says that the branch prediction may help the conditional branches that are used more often, i.e. the ones in a loop. So it basically says, using if inside a loop is ok.

While the conclusion is correct, you shouldn’t worry about ifs in a loop (you shouldn’t worry about anything unless a profiler tells you that there is a bottleneck), the sentence itself is pretty meaningless in the context of Java.

Branch prediction is a CPU feature, thus in interpreted execution it’s irrelevant to Java level branches as they just modify the interpreter’s state (i.e. the pointer though which the next instruction will be read) but are not associated with a CPU instruction that would be specific to the particular branch.

Once HotSpot kicks in, the picture is entirely different. If this code is a hot spot, the optimizer will apply plenty of code transformations which render most assumption about, how the Java code will be executed, wrong.

One common optimization is loop unrolling. Instead of having one block of code representing the loop’s body, there will be multiple instances of it following each other, being optimized regarding invariants of their particular iteration. This setups allows to elide the if related branches completely as it is perfectly predictable that after the first transition of firstManagedChild from true to false, it will never go back, hence while the first iteration invariably see a true value for it, the code for the subsequent iterations can be optimized to treat the variable as being constantly false.

So in that case, branch prediction will again have no meaning as there will be no branches for an if statement whose outcome can be predicted in advance.

Answer 3

An pretty detailled article on branch prediction cab be found here

To answer your question - From my understanding, no. I don't think negating the "if" will make any difference whatsoever. It'll optimise the condition for repeating false values just the same as it would for multiple true values.

Answer 4

In addition to the existing answers:

This comment does not seem to be a justification for the "negate if" (as this should not make a difference performance-wise anyhow). Instead, it is probably a justification for not trying to "optimize" the code and avoid the single if. This would be possible with something like this:

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;
}

The comment indicates that this will not bring any performance benefit due to the saved if, because this if will in practice essentially be free due to branch prediction.

_{Side note: I think that there could be other "microoptimizations", like avoiding Math#min(double,double). But the JavaFX guys (hopefully) know their stuff, and probably would have done this if it was likely to make a difference in their case)}