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
