RFR (S) 8136500: Integer/Long getChars and stringSize should be more idiomatic
Ivan Gerasimov
ivan.gerasimov at oracle.com
Sat Nov 21 20:38:09 UTC 2015
Hi Aleksey!
Just by a coincidence, I was experimenting with the same piece of code :)
I haven't come up with the complete solution so far, but here are a few
considerations, which you may find useful.
1)
When benchmarking different implementation of Integer.stringSize() the
fastest (on my machine) variants were with explicitly unrolled
switch-like constructions and hard-coded binary search with guaranteed
no-more-than-four comparisons:
They appeared to be twice as fast as the original implementation.
However, the simple loop that you have is surely cleaner.
static int stringSize_switch(int x) {
if (x < 10) return 1;
if (x < 100) return 2;
if (x < 1000) return 3;
if (x < 10000) return 4;
if (x < 100000) return 5;
if (x < 1000000) return 6;
if (x < 10000000) return 7;
if (x < 100000000) return 8;
if (x < 1000000000) return 9;
return 10;
}
static int stringSize_binchop(int x) {
if (x < 100) {
// this produces a bit tinier byte-code than `return (x <
10) ? 1 : 2`
if (x < 10) return 1;
return 2;
}
if (x < 1000000) {
if (x < 10000) {
if (x < 1000) return 3;
return 4;
}
if (x < 100000) return 5;
return 6;
}
if (x < 100000000) {
if (x < 10000000) return 7;
return 8;
}
if (x < 1000000000) return 9;
return 10;
}
2)
The lookup tables DigitTens and DigitOnes are always used together.
Packing them in an one table can save us one array access for the price
of little arithmetic.
static final int[] TwoDigits = {
('0'<<16)+'0', ('0'<<16)+'1', ('0'<<16)+'2', ('0'<<16)+'3',
('0'<<16)+'4',
('0'<<16)+'5', ('0'<<16)+'6', ('0'<<16)+'7', ('0'<<16)+'8',
('0'<<16)+'9',
('1'<<16)+'0', ('1'<<16)+'1', ('1'<<16)+'2', ('1'<<16)+'3',
('1'<<16)+'4',
('1'<<16)+'5', ('1'<<16)+'6', ('1'<<16)+'7', ('1'<<16)+'8',
('1'<<16)+'9',
('2'<<16)+'0', ('2'<<16)+'1', ('2'<<16)+'2', ('2'<<16)+'3',
('2'<<16)+'4',
('2'<<16)+'5', ('2'<<16)+'6', ('2'<<16)+'7', ('2'<<16)+'8',
('2'<<16)+'9',
('3'<<16)+'0', ('3'<<16)+'1', ('3'<<16)+'2', ('3'<<16)+'3',
('3'<<16)+'4',
('3'<<16)+'5', ('3'<<16)+'6', ('3'<<16)+'7', ('3'<<16)+'8',
('3'<<16)+'9',
('4'<<16)+'0', ('4'<<16)+'1', ('4'<<16)+'2', ('4'<<16)+'3',
('4'<<16)+'4',
('4'<<16)+'5', ('4'<<16)+'6', ('4'<<16)+'7', ('4'<<16)+'8',
('4'<<16)+'9',
('5'<<16)+'0', ('5'<<16)+'1', ('5'<<16)+'2', ('5'<<16)+'3',
('5'<<16)+'4',
('5'<<16)+'5', ('5'<<16)+'6', ('5'<<16)+'7', ('5'<<16)+'8',
('5'<<16)+'9',
('6'<<16)+'0', ('6'<<16)+'1', ('6'<<16)+'2', ('6'<<16)+'3',
('6'<<16)+'4',
('6'<<16)+'5', ('6'<<16)+'6', ('6'<<16)+'7', ('6'<<16)+'8',
('6'<<16)+'9',
('7'<<16)+'0', ('7'<<16)+'1', ('7'<<16)+'2', ('7'<<16)+'3',
('7'<<16)+'4',
('7'<<16)+'5', ('7'<<16)+'6', ('7'<<16)+'7', ('7'<<16)+'8',
('7'<<16)+'9',
('8'<<16)+'0', ('8'<<16)+'1', ('8'<<16)+'2', ('8'<<16)+'3',
('8'<<16)+'4',
('8'<<16)+'5', ('8'<<16)+'6', ('8'<<16)+'7', ('8'<<16)+'8',
('8'<<16)+'9',
('9'<<16)+'0', ('9'<<16)+'1', ('9'<<16)+'2', ('9'<<16)+'3',
('9'<<16)+'4',
('9'<<16)+'5', ('9'<<16)+'6', ('9'<<16)+'7', ('9'<<16)+'8',
('9'<<16)+'9',
};
...
int twoDig = TwoDigits[r];
buf[--charPos] = (byte)twoDig;
buf[--charPos] = (byte)(twoDig >> 16);
...
3)
In Integer.toString(int i)
463 if (i == Integer.MIN_VALUE)
464 return "-2147483648";
465 int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
It might be reasonable to reorganize the code a bit:
int size = 0, i1 = i;
if (i < 0) {
if (i == Integer.MIN_VALUE)
return "-2147483648";
size = 1;
i1 = -i;
}
size += stringSize(i1);
First, we would skip one comparison of positive i with MIN_INT.
Second, I think, the code of stringSize() might be better inlined, if it
was used only once.
And the same for AbstractStringBuilder.append(int).
Sincerely yours,
Ivan
On 21.11.2015 1:56, Aleksey Shipilev wrote:
> Hi,
>
> We have discovered this both in Compact Strings and Indy String Concat
> work, but it deserves to be treated separately.
>
> Integer/Long getChars code seems to be very old (Josh Bloch estimated
> circa 1994) and written under the assumption no compiler is here to help
> us. Fast-forward 20 years, and I would like to suggest a cleanup in
> Integer/Long getChars and stringSize:
> http://cr.openjdk.java.net/~shade/8136500/webrev.01/
>
> This cleanup *also* improves performance:
> http://cr.openjdk.java.net/~shade/8136500/notes.txt
>
> While cleaning the code up, the patch does a few things for these reasons:
>
> * Rewrites Integer.stringSize to the similar loop Long.stringSize is
> using. The compiled code shows more efficient code: it does not access
> memory anymore, but what's more important, after the loop unrolling we
> have the precomputed constants against which we are comparing.
>
> * Removes the manual strength-reduction of multiplications/divisions to
> bit-twiddling: the generated code suggests compiler does it for us. In
> fact, manual shifting in current getChar code is a pessimisation!
>
> * Specializes DigitOnes/Tens for bytes for a Latin1 String cases. This
> avoids narrowing conversions in the code: surprisingly, this does affect
> performance.
>
> * Since the weird "65536"-sized bit-twiddling is gone, we can now make
> the first loops to cover all values above and equal to 100. This opens
> up the way to carefully spell out the code that processes the remaining
> two digits -- this does help performance a lot.
>
> * Avoids Integer.digits lookups, and does the computations in place.
> This saves bounds check, and a memory access. (Note that it is a lesser
> evil for the DigitOnes/Tens case, where the alternative computation
> would involve integer division).
>
> Testing:
> - java/lang, java/util, plus new tests
>
> Thanks,
> -Aleksey
>
>
More information about the core-libs-dev
mailing list