Easy to Learn Java: Programming Articles, Examples and Tips

Start with Java in a few days with Java Lessons or Lectures

Home

Code Examples

Java Tools

More Java Tools!

Java Forum

All Java Tips

Books

Submit News
Search the site here...
Search...
 
Search the JavaFAQ.nu
1000 Java Tips ebook

1000 Java Tips - Click here for the high resolution copy!1000 Java Tips - Click here for the high resolution copy!

Java Screensaver, take it here

Free "1000 Java Tips" eBook is here! It is huge collection of big and small Java programming articles and tips. Please take your copy here.

Take your copy of free "Java Technology Screensaver"!.

Speed-kings of inverting booleans

JavaFAQ Home » Story by Dr. Kabutz Go to all tips in Story by Dr. Kabutz


Bookmark and Share

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

Author: Dr. Heinz M. Kabutz

JDK version:

Category: Performance

You can subscribe from our home page: http://www.javaspecialists.co.za (which also hosts all previous issues, available free of charge Smile

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 Smile))

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;? Smile (one guy said flg = !flg; is an answer Wink)"

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 Wink

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 Wink

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 Wink

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

Reprint Rights. Copyright subsists in all the material included in this email, but you may freely share the entire email with anyone you feel may be interested, and you may reprint excerpts both online and offline provided that you acknowledge the source as follows: This material from The Java(tm) Specialists' Newsletter by Maximum Solutions (South Africa). Please contact Maximum Solutions for more information.

Java and Sun are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. Maximum Solutions is independent of Sun Microsystems, Inc.

 Printer Friendly Page  Printer Friendly Page
 Send to a Friend  Send to a Friend

.. Bookmark and Share

Search here again if you need more info!
Custom Search



Home Code Examples Java Forum All Java Tips Books Submit News, Code... Search... Offshore Software Tech Doodling

RSS feed Java FAQ RSS feed Java FAQ News     

    RSS feed Java Forums RSS feed Java Forums

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest 1999-2006 by Java FAQs Daily Tips.

Interactive software released under GNU GPL, Code Credits, Privacy Policy