Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By JosAH

Thread: Confusing Optimization in Integer.class

  1. #1
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,602
    Rep Power
    5

    Default Confusing Optimization in Integer.class

    Hi folks,

    The following code is take from the Integer.class in the JDK. Lines 355-363 in the source for Java 1.7.

    Java Code:
     // Generate two digits per iteration
            while (i >= 65536) {
                q = i / 100;
            // really: r = i - (q * 100);
                r = i - ((q << 6) + (q << 5) + (q << 2));
                i = q;
                buf [--charPos] = DigitOnes[r];
                buf [--charPos] = DigitTens[r];
            }
    How this works is not the issue. My question is regarding the bit-shift and sum alternative to just simply multiplying.
    I did some iteration tests of the following:
    Java Code:
    r = i - ((q << 6) + (q << 5) + (q << 2));
    and then repeated for the following:
    Java Code:
    r = i -  (q * 100);
    My results keep indicating that it would be almost two times faster to just do the basic
    multiplication as opposed to the bit shift method. Am I missing some subtlety here?
    My IDE is Eclipse Junos.

    Regards,
    Jim

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Confusing Optimization in Integer.class

    For convenience, here is the method that code is found in:

    Java Code:
       /**
         * Places characters representing the integer i into the
         * character array buf. The characters are placed into
         * the buffer backwards starting with the least significant
         * digit at the specified index (exclusive), and working
         * backwards from there.
         *
         * Will fail if i == Integer.MIN_VALUE
         */
        static void getChars(int i, int index, char[] buf) {
            int q, r;
            int charPos = index;
            char sign = 0;
    
            if (i < 0) {
                sign = '-';
                i = -i;
            }
    
            // Generate two digits per iteration
            while (i >= 65536) {
                q = i / 100;
            // really: r = i - (q * 100);
                r = i - ((q << 6) + (q << 5) + (q << 2));
                i = q;
                buf [--charPos] = DigitOnes[r];
                buf [--charPos] = DigitTens[r];
            }
    
            // Fall thru to fast mode for smaller numbers
            // assert(i <= 65536, i);
            for (;;) {
                q = (i * 52429) >>> (16+3);
                r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
                buf [--charPos] = digits [r];
                i = q;
                if (i == 0) break;
            }
            if (sign != 0) {
                buf [--charPos] = sign;
            }
        }
    How are you running your benchmark?

    It's hard to test performance with micro-benchmarks. This method (and the code in question) was probably designed to work with a range of numbers. So the multiplication code might run faster for your test, but not in the overall case. Plus the compiler might do something smart and convert your multiplication anyway.

    But I don't really have a good answer for you, so I'm curious what smarter people have to say about this.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,602
    Rep Power
    5

    Default Re: Confusing Optimization in Integer.class

    Well, you had me thinking about my benchmark. I went back and checked and it appears that the original code may be a tad faster. I believe my benchmark was subject to a hoisting optimization by the compiler. So it only appeared that the multiplication was faster. I will investigate further and if I find something else I will post it. Sorry to bother everyone.

    Regards,
    Jim

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,520
    Blog Entries
    7
    Rep Power
    20

    Default Re: Confusing Optimization in Integer.class

    Some processors, especially small RISC processors, don't have a proper multiplication instruction and a sequence of shifts and adds is as fast as you can get; e.g. an old ARM processor could only do part of the multiplication where the 'one' bits of the multiplicand weren't further apart than 12 bits. e.g. it could multiply by 0xc000 but not by 0x8001 ... also the Atmel processor comes to mind with its (fast) 8 bit wide registers ...

    kind regards,

    Jos
    KevinWorkman likes this.
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. A very confusing question
    By JohnPringle83 in forum New To Java
    Replies: 3
    Last Post: 05-08-2011, 07:29 AM
  2. Replies: 1
    Last Post: 04-19-2011, 04:32 PM
  3. confusing ques
    By rok0016 in forum New To Java
    Replies: 6
    Last Post: 07-15-2010, 06:07 PM
  4. Replies: 7
    Last Post: 12-16-2008, 06:44 PM
  5. Replies: 2
    Last Post: 12-12-2007, 05:01 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •