Why was & used over && in java when comparing two bools?

Question

I was looking through code in Guava https://github.com/google/guava and I see a lot of cool optimizations.

I was wondering if using & over && is an optimization and if it is, why is it? Could it be a style choice?

We are squaring an int b in the IntMath.checkedPow function. We want to check that b * b does not overflow:

checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT);
        b *= b;

In this example, why was & used over &&?

Edit: Matt is correct. I compiled this Java code in Java 8:

public static boolean and (boolean a, boolean b){
    return a && b;
}

public static boolean andBit (boolean a, boolean b){
    return a & b;
}

I looked at the Byte code using Intellij. I see that we are using branching in the "and" function because we have IFEQ and GOTO.

  // access flags 0x9
  public static and(ZZ)Z
   L0
    LINENUMBER 8 L0
    ILOAD 0
    IFEQ L1
    ILOAD 1
    IFEQ L1
    ICONST_1
    GOTO L2
   L1
   FRAME SAME
    ICONST_0
   L2
   FRAME SAME1 I
    IRETURN
   L3
    LOCALVARIABLE a Z L0 L3 0
    LOCALVARIABLE b Z L0 L3 1
    MAXSTACK = 1
    MAXLOCALS = 2

  // access flags 0x9
  public static andBit(ZZ)Z
   L0
    LINENUMBER 12 L0
    ILOAD 0
    ILOAD 1
    IAND
    IRETURN
   L1
    LOCALVARIABLE a Z L0 L1 0
    LOCALVARIABLE b Z L0 L1 1
    MAXSTACK = 2
    MAXLOCALS = 2
}

To answer the question, & is faster if the cost of evaluating an extra <= is faster than branching.

Erwin's comment made me look closer at the actual while loop. b *=b is in a while loop which may repeat a lot. However, b can only be negative in the first loop because when we pass b *= b: b will be positive from then on.

I suspect it was a typo. *Since neither expression has side-effects* it is semantically equivalent to the short-circuiting `&&` expect it may perform a needless compare. The only time when `boolean & boolean` "makes sense" is when *wanting to ensure* the second operand expression is always evaluated - ie. there are "tricky side-effects". — user2864740, Dec 25 '17 at 03:44
Matt brought up a point that it may be related to internal compilation/branching so.. I'd leave it open. — user2864740, Dec 25 '17 at 03:50
@EricCherin the thing to get here is actually that this is a small nightmare to test (to actually prove that `&` would have a big benefit), so don't write code like this *yourself* - unless you really know what you are doing — Eugene, Dec 26 '17 at 07:50
They place the method in their benchmarking suite and then write a lot of tests. It is good to know and interesting. — Eric Cherin, Dec 26 '17 at 14:06

Matt Timmermans · Accepted Answer · 2017-12-25T03:57:06.613

5

Since conditional branches are somewhat expensive, but comparing the values of integers is very fast, the fastest way to implement that expression in machine instructions would evaluate both sub-expressions and would not include a conditional branch.

The way it is written in your code snippet does reflect the best way to implement it. We usually expect the compiler to figure stuff like this out by itself, but maybe they tested and found that it did not...

Or maybe the developer just wrote it the faster way because the alternative would be to write it in a way that might be slower -- and there's certainly no good reason to do that!

edited Dec 25 '17 at 03:57

answered Dec 25 '17 at 03:46

Matt Timmermans

53,709
3
46
87

3

Again, Java Byte Code or no purchase. This may be right - but it needs a little bit of validation or supporting resources :} – user2864740 Dec 25 '17 at 03:48
When the code says && it means a conditional branch -- the right side is not evaluated when the left side is false. The compiler is free to do anything that is functionally equivalent, though, *and* the user may have a few different Java or JIT compilers to choose from, so whether or not you get a branch in the machine code from && in this case is up in the air. – Matt Timmermans Dec 25 '17 at 03:55
I'm skeptical. If this were indeed the reason, I would expect it to be well-documented in the code. – shmosel Dec 25 '17 at 03:59
Matt is indeed right. I just compiled and got the bytecode using intellij and Java 8. – Eric Cherin Dec 25 '17 at 04:01
1

I don't think this has any performance impact, since the only case where it would make a difference (if the value `b` was smaller than `-FLOOR_SQRT_MAX_INT`) is an abnormal case resulting in throwing an exception ( which is in itself way more expensive than a branch). – Erwin Bolwidt Dec 25 '17 at 04:06
1

The fact that one branch will only be taken in case of abnormal input means that the branch prediction will be 100% correct for correctly written code. https://softwareengineering.stackexchange.com/questions/159706/does-current-jit-optimize-generated-machine-codes-for-branch-prediction-based-on – Erwin Bolwidt Dec 26 '17 at 01:00
@ErwinBolwidt, I think this does have impact. I have been looking at the Guava code more and the authors consistently avoid branching by using bit manipulation. They also use | instead of || for similar reasons. Even if we have great branch prediction, we are still branching which is slower than not branching. Using a bit wise operator prevents us from branching even if we have to check both conditions. – Eric Cherin Dec 27 '17 at 21:44
@EricCherin Not always. Sometimes [branching is cheaper](https://stackoverflow.com/a/19693809/581205) as it needs one machine code instruction less and uses a possibly otherwise idle branching unit on the CPU. I guess, the Guava guys are wrong this time, but using `&` vs `&&` is only a hint to the JVM, which is free to change it as long as the outcome is the same. – maaartinus Dec 29 '17 at 11:01
@EricCherin I've just found out that Skylake (no idea about others) can perform two predicted not-taken branches per cycle. – maaartinus Dec 30 '17 at 06:14

Why was & used over && in java when comparing two bools?

1 Answers1