Why is "or" slower than "and" in Java?

Question

Today I encountered a rather amazing behavior in java, or is slower than and!

I even made a test case that you can see at the below.Now I wonder why this happens? Am I doing something wrong or does it happen just on my computer? I don't see any reason that or should be slower than and specially with this significant difference. I want to test this phenomenon with some other languages, do you have any idea about this in general?

public class TestClass {

    public static void main(String[] args) {

        long[] or = new long[10];
        long[] and = new long[10];
        long lStartTime, lEndTime, difference = 0;
        for (int idx = 0; idx < 10; idx++) {

            lStartTime = System.nanoTime();
            for (int i= 0; i < 1000000000; i++) { 
                int j = i | i+1 ;
            }
            lEndTime = System.nanoTime();
            difference = lEndTime - lStartTime;
            System.out.println("Elapsed milliseconds: " + difference/1000000);
            or[idx] = difference;

            lStartTime = System.nanoTime();
            for (int i= 0; i < 1000000000; i++) {
                int j = i & i+1 ;
            }
            lEndTime = System.nanoTime();
            difference = lEndTime - lStartTime;
            System.out.println("Elapsed milliseconds: " + difference/1000000);  
            and[idx] = difference;
            System.out.println("------------------------------------" );

        }

        long tmp = 0;
        for (long l : or) {
            tmp += l;
        }
        tmp /= 10;
        System.out.println("Elapsed milliseconds for or: " + tmp/1000000);
        tmp = 0;
        for (long l : and) {
            tmp += l;
        }
        tmp /= 10;
        System.out.println("Elapsed milliseconds for and: " + tmp/1000000);
    }
}

results :

Elapsed milliseconds: 1600
Elapsed milliseconds: 1332
------------------------------------
Elapsed milliseconds: 1609
Elapsed milliseconds: 1335
------------------------------------
Elapsed milliseconds: 1609
Elapsed milliseconds: 1335
------------------------------------
Elapsed milliseconds: 1542
Elapsed milliseconds: 1314
------------------------------------
Elapsed milliseconds: 1705
Elapsed milliseconds: 1324
------------------------------------
Elapsed milliseconds: 1559
Elapsed milliseconds: 1315
------------------------------------
Elapsed milliseconds: 1526
Elapsed milliseconds: 1314
------------------------------------
Elapsed milliseconds: 1568
Elapsed milliseconds: 1340
------------------------------------
Elapsed milliseconds: 1551
Elapsed milliseconds: 1318
------------------------------------
Elapsed milliseconds: 1574
Elapsed milliseconds: 1321
------------------------------------
Elapsed milliseconds for or: 1584
Elapsed milliseconds for and: 1325

i think it's different by shifting. but `AND` only filled up, and `OR` check each bits,.. — Adrian Preuss, Mar 22 '14 at 08:38
@AdrianPreuss- I don't understand "i think it's different by shifting", would you please explain? — Mohsen Kamrani, Mar 22 '14 at 08:41
Check out the function http://en.wikipedia.org/wiki/Bitwise_operator — Adrian Preuss, Mar 22 '14 at 08:44
You see, the `OR` must calculated a little bit more than an `AND` ^^ — Adrian Preuss, Mar 22 '14 at 08:45
@mok Nice catch. Can you add the short circuit `&&` and `||` to your evaluation? And also `Elapsed milliseconds - OR` for each result you obtain will be more readable. — aravind, Mar 22 '14 at 08:45
Do you get the same result if you make the first loop use `&` and the second one `|`? — user253751, Mar 22 '14 at 08:45
@AdrianPreuss They are both single instructions on the CPU that take the same number of cycles, specifically 1. No shifting required. — user207421, Mar 22 '14 at 08:49
II can think of several reasons: (i) your measurement methodology is flawed: if you swap the tests, do you get same result? (ii) your processor is better at and-ing than or-ing (on recent Intel processors it should be the same) (iii) the JVM has found an optimisation in one case but not the other. — assylias, Mar 22 '14 at 08:51
I get opposite results when I run this on my laptop. i.e. `or` takes more time than `and`. Is this architecture dependent? I am using Java 7, on Linux 32 bit machine. — Sourabh Bhat, Mar 22 '14 at 08:53
@assylias- ass immibis says I swapped the loops and the result completely opposed. — Mohsen Kamrani, Mar 22 '14 at 08:54
@mok then it's something to do with the loops, and the order of the code, and stuff interfering with your measurement, and not the actual operations. — user253751, Mar 22 '14 at 08:54
Your benchmark is flawed! The java compiler/JIT/VM/whatever optimises away your for loops and I get 0ms for everything :), so I modified your code a little bit, but I'm getting the opposite results :) — Svetlin Zarev, Mar 22 '14 at 08:55
@immibis- It's more acceptable for me this way. cause I don't see any reason that `and`/`or` should have different performances. But how should I exactly do my test? BTW, I tried to implement `or` with `not` + `and` but it's every time more time consuming, so I think this benchmark ,indeed, is showing they `and` and `or` are equal, do you agree? — Mohsen Kamrani, Mar 22 '14 at 08:59
@SvetlinZarev- I think so, but even [here](http://stackoverflow.com/questions/180158/how-do-i-time-a-methods-execution-in-java) it shows this way. What's wrong in my measurement? — Mohsen Kamrani, Mar 22 '14 at 09:03
I ran you code. Only the first couple of loops showed non zero results as it got optimised away. So I ran it once and `or` came out slower, then I switched the order. This time `and` came out slower. Elapsed milliseconds for and: 1325700 Elapsed milliseconds for or: 798400 — Salix alba, Mar 22 '14 at 09:09
@Salixalba- Yes, I tried swapping the loops, and the results changed. But I don't know why?! — Mohsen Kamrani, Mar 22 '14 at 09:12

barak manos · Answer 1 · 2014-03-22T10:08:38.987

Bit-Wise OR is not slower than Bit-Wise AND!

Swap between the time-measuring snippets in your code, and you'll get the opposite results:

for (int idx = 0; idx < 10; idx++) {

    lStartTime = System.nanoTime();
    for (int i= 0; i < 1000000000; i++) {
        int j = i & i+1 ;
    }
    lEndTime = System.nanoTime();

    difference = lEndTime - lStartTime;
    System.out.println("Elapsed milliseconds: " + difference/1000000);  
    and[idx] = difference;

    lStartTime = System.nanoTime();
    for (int i= 0; i < 1000000000; i++) { 
        int j = i | i+1 ;
    }
    lEndTime = System.nanoTime();

    difference = lEndTime - lStartTime;
    System.out.println("Elapsed milliseconds: " + difference/1000000);
    or[idx] = difference;

    System.out.println("------------------------------------");
}

I tend to guess that the JVM applies some kind of runtime optimization during the second snippet.

I completely agree. I tried as immibs and ... said. But what's wrong in my test? — Mohsen Kamrani, Mar 22 '14 at 09:57
@mok: As I mentioned at the bottom of the answer, I tend to guess that the JVM applies some kind of runtime optimization during the second snippet. Other than that, I don't think that there's anything wrong with your test, only with your conclusions from this test. — barak manos, Mar 22 '14 at 10:03

score 4 · Accepted Answer · edited May 23 '17 at 12:03

Writing correct micro benchmarks like the one you have done is very time consuming and error prone. I recommend using an existing library like e.g. Caliper instead.

Here is a corresponding benchmark done in Caliper (latest git version necessary to compile):

public class BitwiseOperatorPerformance {
    @Benchmark
    public int timeOr(int reps){
        int dummy = 0;
        for (int i = 0; i < reps; i++) {
            dummy |= i+1;
        }
        return dummy;
    }
    @Benchmark
    public int timeAnd(int reps){
        int dummy = 0;
        for (int i = 0; i < reps; i++) {
            dummy &= i+1;
        }
        return dummy;
    }
}

And here is the test result: link

The result shows, that the performance of the AND and OR operators is exactly the same.

Why is "or" slower than "and" in Java?

2 Answers2