Speed-kings of inverting booleans

JavaFAQ Home » Story by Dr. Kabutz

The Java Specialists' Newsletter [Issue 042] - Speed-kings of inverting booleans

Author: Dr. Heinz M. Kabutz

Category: Performance

Welcome to the 42nd edition of The Java(tm) Specialists' Newsletter, sent to 2779 Java experts in over 75 countries. I'm writing this newsletter about 30'000 feet above mother earth on my way to Mauritius. Yes, eventually we managed to sort out all the bureacratic problems, and had to just shift the Design Patterns course by one week ))

Speed-kings of inverting booleans

About 10 days ago, I was chatting on ICQ to Roman Porotnikov, the best Java programmer in the Ukraine according to Brainbench, when he posed an interesting question:

"What's more quick variant for flag = !flag;? (one guy said flg = !flg; is an answer )"

I didn't really know the answer, so I guessed: "Probably flag = flag ? false : true;"

Being the avid programmer that I am, I quickly wrote a test program:

public class NotTest1 {
  public static void main(String[] args) {
    boolean flag = true;
    long start;
    start = -System.currentTimeMillis();
    for (int i=0; i<100000000; i++) {
      flag = !flag;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = !flag: " + start + "ms");

    start = -System.currentTimeMillis();
    for (int i=0; i<100000000; i++) {
      flag = flag?false:true;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = flag?false:true: " + start + "ms");
  }
}

Imagine my glee when I saw the following performance results. Roman might be the best Java programmer in the Ukraine, but I am the best Java programmer on this airplane!

time for b = !b: 1712ms
time for b = b?false:true: 1132ms

I was still puzzling over this as I could not understand how that could possible be faster, when Roman piped up:

"The answer is actually flag ^= true;"

Hmmmm - XOR on a bitwise level - sneaky! I added his "way" to my test to see if it really was faster, although I did believe that bitwise manipulation should be faster, but you never know with Java

public class NotTest2 {
  public static void main(String[] args) {
    boolean flag = true;
    long start;
    start = -System.currentTimeMillis();
    for (int i=0; i<100000000; i++) {
      flag = !flag;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = !flag: " + start + "ms");

    start = -System.currentTimeMillis();
    for (int i=0; i<100000000; i++) {
      flag = flag?false:true;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = flag?false:true: " + start + "ms");

    for (int i=0; i<100000000; i++) {
      flag ^= true; // XOR
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag ^= true: " + start + "ms");
  }
}

And of course, Roman was right, as you can see from the figures below.

time for flag = !flag: 1722ms
time for flag = flag?false:true: 1162ms
time for flag ^= true: 781ms

Interesting figures. It proves that my version is 32% faster and that Roman's version is 55% faster.

I mentioned this strange idea to Paul van Spronsen and he suggested we look at the generated bytecode. You can disassemble Java bytecode with the javap tool that forms part of the JDK. [HK: at this point of writing, we hit some turbulence and our food was being served so I thought it best to wait until the hotel. I must just add that this is the best hotel I've stayed at in all my travels and we are planning another bunch of courses in May - will let you know next newsletter. Back to the newsletter ...] In order to be able to compare the bytecode easily, I've split the cases into Normal.java, Faster.java and Fastest.java.

public class Normal {
  public void test() {
    boolean flag = true;
    flag = !flag;
  }
}

Compiling this class and running the command javap -c Normal produced the following for method test (comments are mine):

Method void test()
   0 iconst_1   // push constant "true"
   1 istore_1   // store in location 1 (flag)
   2 iload_1    // load value in location 1
   3 ifne 10    // if value is false goto bytecode 10
   6 iconst_1   // push constant "true"
   7 goto 11    // goto location 11
  10 iconst_0   // push constant "false"
  11 istore_1   // store value on stack in location 1
  12 return     // duh - this is obvious
                // don't you just LOVE assembler comments?

Ok, that was fairly optimal... Let's look at the next case and see how it differs.

public class Faster {
  public void test() {
    boolean flag = true;
    flag = flag?false:true;
  }
}

The resultant bytecodes were:

Method void test()
   0 iconst_1   // push constant "true"
   1 istore_1   // store in location 1 (flag)
   2 iload_1    // load value in location 1
   3 ifne 10    // if value is true goto bytecode 10
   6 iconst_0   // push constant "false"
   7 goto 11    // goto location 11
  10 iconst_1   // push constant "true"
  11 istore_1   // store value on stack in location 1
  12 return

Identical? Yep, pretty much identical. The only difference is in one case we are testing for "equal" and in the other we are testing for "not equal". Surely that could not make such a big difference? (I'll leave the decompiling and understanding of the XORoman way as an exercise to the reader

public class Fastest {
  public void test() {
    boolean flag = true;
    flag ^= true;
  }
}

What happened? I have to assume that some part of the hotspot kicked in after some iterations and that the second example was only faster because it was second, so I ran the examples longer:

public class Not {
  public static void test() {
    boolean flag = true;
    long start;

    start = -System.currentTimeMillis();
    for (int i=0; i<1000000000; i++) {
      flag ^= true;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag ^= true: " + start + "ms");

    start = -System.currentTimeMillis();
    for (int i=0; i<1000000000; i++) {
      flag = !flag;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = !flag: " + start + "ms");

    start = -System.currentTimeMillis();
    for (int i=0; i<1000000000; i++) {
      flag = flag?false:true;
    }
    start += System.currentTimeMillis();
    System.out.println("time for flag = flag?false:true: " + start + "ms");
  }
  public static void main(String[] args) throws Exception {
    test();
    Thread.sleep(1);
    test();
  }
}

Letting it run longer certainly shows more truth:

time for flag ^= true: 12397ms
time for flag = !flag: 11356ms
time for flag = flag?false:true: 11326ms
time for flag ^= true: 5697ms
time for flag = !flag: 11326ms
time for flag = flag?false:true: 11326ms

We can learn two lessons from this:

1. flag ^= true is faster than flag = !flag
2. Never trust Java performance statistics.

Don't forget that an intelligent compiler could've recognised what you were doing and done it on a bit level. There are many factors that affect Java performance: architecture, compiler, hotspot compiler, hardware, etc. and these all play a role when it comes to determining performance.

That's all for tonight - even the mosquitos are asleep already so I better sign off.

Heinz

P.S. If you write to me, please feel free to address me as "Heinz" - we are casually formal in South Africa

P.P.S. Roman Porotnikov's ICQ number is 76669875 and he has an interesting webpage at http://ejb.how.to

Copyright 2000-2004 Maximum Solutions, South Africa

Custom Search