Java – Why is (a*b != 0) faster than (a != 0 && b != 0) in Java

branch-predictionjavamicrobenchmarkperformanceprocessing-efficiency

I'm writing some code in Java where, at some point, the flow of the program is determined by whether two int variables, "a" and "b", are non-zero (note: a and b are never negative, and never within integer overflow range).

I can evaluate it with

if (a != 0 && b != 0) { /* Some code */ }

Or alternatively

if (a*b != 0) { /* Some code */ }

Because I expect that piece of code to run millions of times per run, I was wondering which one would be faster. I did the experiment by comparing them on a huge randomly generated array, and I was also curious to see how the sparsity of the array (fraction of data = 0) would affect the results:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

And the results show that if you expect "a" or "b" to be equal to 0 more than ~3% of the time, a*b != 0 is faster than a!=0 && b!=0:

I'm curious to know why. Could anyone shed some light? Is it the compiler or is it at the hardware level?

Edit: Out of curiosity… now that I learned about branch prediction, I was wondering what the analog comparison would show for a OR b is non-zero:

We do see the same effect of branch prediction as expected, interestingly the graph is somewhat flipped along the X-axis.

Update

1- I added !(a==0 || b==0) to the analysis to see what happens.

2- I also included a != 0 || b != 0, (a+b) != 0 and (a|b) != 0 out of curiosity, after learning about branch prediction. But they are not logically equivalent to the other expressions, because only a OR b needs to be non-zero to return true, so they are not meant to be compared for processing efficiency.

3- I also added the actual benchmark that I used for the analysis, which is just iterating an arbitrary int variable.

4- Some people were suggesting to include a != 0 & b != 0 as opposed to a != 0 && b != 0, with the prediction that it would behave more closely to a*b != 0 because we would remove the branch prediction effect. I didn't know that & could be used with boolean variables, I thought it was only used for binary operations with integers.

Note: In the context that I was considering all this, int overflow is not an issue, but that's definitely an important consideration in general contexts.

CPU: Intel Core i7-3610QM @ 2.3GHz

Java version: 1.8.0_45
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

Best Answer

I'm ignoring the issue that your benchmarking might be flawed, and taking the result at face value.

Is it the compiler or is it at the hardware level?

That latter, I think:

  if (a != 0 && b != 0)

will compile to 2 memory loads and two conditional branches

  if (a * b != 0)

will compile to 2 memory loads, a multiply and one conditional branch.

The multiply is likely to be faster than the second conditional branch if the hardware-level branch prediction is ineffective. As you increase the ratio ... the branch prediction is becoming less effective.

The reason that conditional branches are slower is that they cause the instruction execution pipeline to stall. Branch prediction is about avoiding the stall by predicting which way the branch is going to go and speculatively choosing the next instruction based on that. If the prediction fails, there is a delay while the instruction for the other direction is loaded.

(Note: the above explanation is oversimplified. For a more accurate explanation, you need to look at the literature provided by the CPU manufacturer for assembly language coders and compiler writers. The Wikipedia page on Branch Predictors is good background.)

However, there is one thing that you need to be careful about with this optimization. Are there any values where a * b != 0 will give the wrong answer? Consider cases where computing the product results in integer overflow.

UPDATE

Your graphs tend to confirm what I said.

There is also a "branch prediction" effect in the conditional branch a * b != 0 case, and this comes out in the graphs.
If you project the curves beyond 0.9 on the X-axis, it looks like 1) they will meet at about 1.0 and 2) the meeting point will be at roughly the same Y value as for X = 0.0.

UPDATE 2

I don't understand why the curves are different for the a + b != 0 and the a | b != 0 cases. There could be something clever in the branch predictors logic. Or it could indicate something else.

(Note that this kind of thing can be specific to a particular chip model number or even version. The results of your benchmarks could be different on other systems.)

However, they both have the advantage of working for all non-negative values of a and b.

Related Solutions

Java – Is Java “pass-by-reference” or “pass-by-value”

Java is always pass-by-value. Unfortunately, when we deal with objects we are really dealing with object-handles called references which are passed-by-value as well. This terminology and semantics easily confuse many beginners.

It goes like this:

public static void main(String[] args) {
    Dog aDog = new Dog("Max");
    Dog oldDog = aDog;

    // we pass the object to foo
    foo(aDog);
    // aDog variable is still pointing to the "Max" dog when foo(...) returns
    aDog.getName().equals("Max"); // true
    aDog.getName().equals("Fifi"); // false
    aDog == oldDog; // true
}

public static void foo(Dog d) {
    d.getName().equals("Max"); // true
    // change d inside of foo() to point to a new Dog instance "Fifi"
    d = new Dog("Fifi");
    d.getName().equals("Fifi"); // true
}

In the example above aDog.getName() will still return "Max". The value aDog within main is not changed in the function foo with the Dog "Fifi" as the object reference is passed by value. If it were passed by reference, then the aDog.getName() in main would return "Fifi" after the call to foo.

Likewise:

public static void main(String[] args) {
    Dog aDog = new Dog("Max");
    Dog oldDog = aDog;

    foo(aDog);
    // when foo(...) returns, the name of the dog has been changed to "Fifi"
    aDog.getName().equals("Fifi"); // true
    // but it is still the same dog:
    aDog == oldDog; // true
}

public static void foo(Dog d) {
    d.getName().equals("Max"); // true
    // this changes the name of d to be "Fifi"
    d.setName("Fifi");
}

In the above example, Fifi is the dog's name after call to foo(aDog) because the object's name was set inside of foo(...). Any operations that foo performs on d are such that, for all practical purposes, they are performed on aDog, but it is not possible to change the value of the variable aDog itself.

For more information on pass by reference and pass by value, consult the following SO answer: https://stackoverflow.com/a/430958/6005228. This explains more thoroughly the semantics and history behind the two and also explains why Java and many other modern languages appear to do both in certain cases.

Java – Avoiding NullPointerException in Java

This to me sounds like a reasonably common problem that junior to intermediate developers tend to face at some point: they either don't know or don't trust the contracts they are participating in and defensively overcheck for nulls. Additionally, when writing their own code, they tend to rely on returning nulls to indicate something thus requiring the caller to check for nulls.

To put this another way, there are two instances where null checking comes up:

Where null is a valid response in terms of the contract; and
Where it isn't a valid response.

(2) is easy. Either use assert statements (assertions) or allow failure (for example, NullPointerException). Assertions are a highly-underused Java feature that was added in 1.4. The syntax is:

assert <condition>

assert <condition> : <object>

where <condition> is a boolean expression and <object> is an object whose toString() method's output will be included in the error.

An assert statement throws an Error (AssertionError) if the condition is not true. By default, Java ignores assertions. You can enable assertions by passing the option -ea to the JVM. You can enable and disable assertions for individual classes and packages. This means that you can validate code with the assertions while developing and testing, and disable them in a production environment, although my testing has shown next to no performance impact from assertions.

Not using assertions in this case is OK because the code will just fail, which is what will happen if you use assertions. The only difference is that with assertions it might happen sooner, in a more-meaningful way and possibly with extra information, which may help you to figure out why it happened if you weren't expecting it.

(1) is a little harder. If you have no control over the code you're calling then you're stuck. If null is a valid response, you have to check for it.

If it's code that you do control, however (and this is often the case), then it's a different story. Avoid using nulls as a response. With methods that return collections, it's easy: return empty collections (or arrays) instead of nulls pretty much all the time.

With non-collections it might be harder. Consider this as an example: if you have these interfaces:

public interface Action {
  void doSomething();
}

public interface Parser {
  Action findAction(String userInput);
}

where Parser takes raw user input and finds something to do, perhaps if you're implementing a command line interface for something. Now you might make the contract that it returns null if there's no appropriate action. That leads the null checking you're talking about.

An alternative solution is to never return null and instead use the Null Object pattern:

public class MyParser implements Parser {
  private static Action DO_NOTHING = new Action() {
    public void doSomething() { /* do nothing */ }
  };

  public Action findAction(String userInput) {
    // ...
    if ( /* we can't find any actions */ ) {
      return DO_NOTHING;
    }
  }
}

Compare:

Parser parser = ParserFactory.getParser();
if (parser == null) {
  // now what?
  // this would be an example of where null isn't (or shouldn't be) a valid response
}
Action action = parser.findAction(someInput);
if (action == null) {
  // do nothing
} else {
  action.doSomething();
}

ParserFactory.getParser().findAction(someInput).doSomething();

which is a much better design because it leads to more concise code.

That said, perhaps it is entirely appropriate for the findAction() method to throw an Exception with a meaningful error message -- especially in this case where you are relying on user input. It would be much better for the findAction method to throw an Exception than for the calling method to blow up with a simple NullPointerException with no explanation.

try {
    ParserFactory.getParser().findAction(someInput).doSomething();
} catch(ActionNotFoundException anfe) {
    userConsole.err(anfe.getMessage());
}

Or if you think the try/catch mechanism is too ugly, rather than Do Nothing your default action should provide feedback to the user.

public Action findAction(final String userInput) {
    /* Code to return requested Action if found */
    return new Action() {
        public void doSomething() {
            userConsole.err("Action not found: " + userInput);
        }
    }
}

Update

Best Answer

Related Solutions

Java – Is Java “pass-by-reference” or “pass-by-value”

Java – Avoiding NullPointerException in Java

Related Topic