# Thread: Confusing Optimization in Integer.class

1. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
5,642
Rep Power
9

## 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. ## 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.

3. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
5,642
Rep Power
9

## 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. ## 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

#### Posting Permissions

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