Confusing Optimization in Integer.class

[jim829]

Hi folks,

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

 // 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:

r = i - ((q << 6) + (q << 5) + (q << 2));

and then repeated for the following:

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

[KevinWorkman]

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

   /**
     * 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.

[jim829]

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

[JosAH]

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