Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

Thank you Brian!

This looks good to me.

With kind regards,

Ivan

On 8/23/19 1:33 PM, Brian Burkhalter wrote:

Hi Ivan,

On Aug 23, 2019, at 12:41 PM, Ivan Gerasimov 
mailto:ivan.gerasi...@oracle.com>> wrote:


One minor comment.  Here:
3990 if (digits > 0) {
3991 padWithZeros(buf, digits);
3992 } else {
3993 buf.append('0');
3994 }

I cannot really see how digits may be <= 0, so it seems to me it can 
be safely replaced by just one line `padWithZeros(buf, digits);`.


Actually I don’t see how digits may be non-positive for signum == 0 
either. I’ve reduced the above to one line (L3990) in [1]. That is the 
only change versus version .04.


Alternatively, the entire branch `if (signum == 0) {` can be removed 
from smallToString (so that this method will only work with strictly 
positive numbers), and done only for results[1] at line 4083 because 
it is the only possible source of ZERO values in the process.


It also seems that the arithmetic in the very internal loop at 
4005-4017 can be slightly optimized, but this probably can be left 
for another enhancement.


I think I’ll leave it as is for now.

Thanks!

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.05/


--
With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Hi Ivan,

> On Aug 23, 2019, at 12:41 PM, Ivan Gerasimov  
> wrote:
> 
> One minor comment.  Here:
> 3990 if (digits > 0) {
> 3991 padWithZeros(buf, digits);
> 3992 } else {
> 3993 buf.append('0');
> 3994 }
> 
> I cannot really see how digits may be <= 0, so it seems to me it can be 
> safely replaced by just one line `padWithZeros(buf, digits);`.

Actually I don’t see how digits may be non-positive for signum == 0 either. 
I’ve reduced the above to one line (L3990) in [1]. That is the only change 
versus version .04.

> Alternatively, the entire branch `if (signum == 0) {` can be removed from 
> smallToString (so that this method will only work with strictly positive 
> numbers), and done only for results[1] at line 4083 because it is the only 
> possible source of ZERO values in the process.
> 
> It also seems that the arithmetic in the very internal loop at 4005-4017 can 
> be slightly optimized, but this probably can be left for another enhancement.

I think I’ll leave it as is for now.

Thanks!

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.05/

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

Hi Brian.
This looks good to me, thanks!

One minor comment.  Here:
3990 if (digits > 0) {
3991 padWithZeros(buf, digits);
3992 } else {
3993 buf.append('0');
3994 }

I cannot really see how digits may be <= 0, so it seems to me it can be 
safely replaced by just one line `padWithZeros(buf, digits);`.


Alternatively, the entire branch `if (signum == 0) {` can be removed 
from smallToString (so that this method will only work with strictly 
positive numbers), and done only for results[1] at line 4083 because it 
is the only possible source of ZERO values in the process.



It also seems that the arithmetic in the very internal loop at 4005-4017 
can be slightly optimized, but this probably can be left for another 
enhancement.


With kind regards,
Ivan


On 8/23/19 10:11 AM, Brian Burkhalter wrote:

Hi Ivan,

On Aug 22, 2019, at 1:24 PM, Ivan Gerasimov 
mailto:ivan.gerasi...@oracle.com>> wrote:


I have a few further suggestions how to simplify the code.

[…]


Those are all good suggestions: thanks!


Here's the patch, which illustrates all the suggestions above:
http://cr.openjdk.java.net/~igerasim/8229845/00/webrev/
(I have only run the tests from test/jdk/java/math/BigInteger to 
verify it).


This patch has a problem:
4023 padWithZeros(buf, digits - s.length() + (numGroups - 1) * 
digitsPerLong[radix]);

It is missing parentheses:

4023         padWithZeros(buf, digits - (s.length() + (numGroups - 1) 
* digitsPerLong[radix]));


I was unable to find this by debugging but implemented your 
suggestions by hand and then found it by diff-ing the patches. My 
updated versions with your suggestions incorporated are: [1] delta, 
[2] absolute. I also increased the size of some of the values tested 
at line 798 of BigIntegerTest.


Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.03-04/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.04/


--
With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Hi Ivan,

> On Aug 22, 2019, at 1:24 PM, Ivan Gerasimov  wrote:
> 
> I have a few further suggestions how to simplify the code.
> 
> […]

Those are all good suggestions: thanks!

> Here's the patch, which illustrates all the suggestions above:
> http://cr.openjdk.java.net/~igerasim/8229845/00/webrev/ 
> 
> (I have only run the tests from test/jdk/java/math/BigInteger to verify it).

This patch has a problem:
4023 padWithZeros(buf, digits - s.length() + (numGroups - 1) * 
digitsPerLong[radix]);
It is missing parentheses:

4023 padWithZeros(buf, digits - (s.length() + (numGroups - 1) * 
digitsPerLong[radix]));

I was unable to find this by debugging but implemented your suggestions by hand 
and then found it by diff-ing the patches. My updated versions with your 
suggestions incorporated are: [1] delta, [2] absolute. I also increased the 
size of some of the values tested at line 798 of BigIntegerTest.

Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.03-04/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.04/

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

Thank you Brian, this looks much better!

I have a few further suggestions how to simplify the code.

1)
If this BigInteger is negative, it is negated in two places: @ 3943 and 
either @ 4003 or @ 4061.
It is better to keep abs value at the very beginning and make private 
toString(...) and smallToString() to only accept non-negative numbers.


2)
Once the 1) is done, it is possible to remove lines 3948-3954, and 
always call private toString(...), which will immediately delegate to 
smallToString() if necessary.  This is just to make the code shorter.


3)
In padWithZeros(), the condition check `if (digits > 0 && len < digits) 
{` is not necessary.
Actually, I would suggest to make a single argument, say, 
numLeadingZeros (in the current code it is `m`).


4)
I think that logic with making the argument `digits` == -1 for the first 
chunk of digits is over-complication:  `digits` can always be safely set 
to 1 in the initial call to the private toString() or smallToString().

Then the variable atBeginning is not needed at all.

5)
If 3) and 4) are done, the two lines 3988 and 3989 can be reduced to 
`padWithZeros(buf, digits);`


Here's the patch, which illustrates all the suggestions above:
http://cr.openjdk.java.net/~igerasim/8229845/00/webrev/
(I have only run the tests from test/jdk/java/math/BigInteger to verify it).

With kind regards,
Ivan


On 8/22/19 11:04 AM, Brian Burkhalter wrote:

Hi Ivan,

Please see the delta [1] and absolute [2] webrevs.

On Aug 21, 2019, at 7:38 PM, Ivan Gerasimov 
mailto:ivan.gerasi...@oracle.com>> wrote:


A couple of comments

1)
3974 if (signum == 0) {
3975 buf.append('0');
3976 return;
3977 }

Shouldn't it be padded with zeroes, if digits > 0?
If I'm not mistaken, it could happen if result[1] at the end of 
toString() happens to be ZERO.


Good catch: you are absolutely correct.

It that's true, then it may be a good idea to add a testcase for a 
number with many trailing zeros in a string representation. 
Currently, test/jdk/java/math/BigInteger/BigIntegerTest.java in 
stringConv() operates on random numbers, which are unlikely to have 
huge number of trailing zeros.


I added testing this to stringConv(). The test fails without the most 
recent delta applied to the implementation.



2)
4120 /* zero is a string of NUM_ZEROS consecutive zeros. */
4121 private static final String zeros = "0".repeat(NUM_ZEROS);

Nit in the comment:  name of the constant should be zero*s*.


I changed the variable name to ZEROS as it is a constant.

Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.02-03/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.03/


--
With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Hi Ivan,

Please see the delta [1] and absolute [2] webrevs.

> On Aug 21, 2019, at 7:38 PM, Ivan Gerasimov  wrote:
> 
> A couple of comments
> 
> 1)
> 3974 if (signum == 0) {
> 3975 buf.append('0');
> 3976 return;
> 3977 }
> 
> Shouldn't it be padded with zeroes, if digits > 0?
> If I'm not mistaken, it could happen if result[1] at the end of toString() 
> happens to be ZERO.

Good catch: you are absolutely correct.

> It that's true, then it may be a good idea to add a testcase for a number 
> with many trailing zeros in a string representation. Currently, 
> test/jdk/java/math/BigInteger/BigIntegerTest.java in stringConv() operates on 
> random numbers, which are unlikely to have huge number of trailing zeros.

I added testing this to stringConv(). The test fails without the most recent 
delta applied to the implementation.

> 2)
> 4120 /* zero is a string of NUM_ZEROS consecutive zeros. */
> 4121 private static final String zeros = "0".repeat(NUM_ZEROS);
> 
> Nit in the comment:  name of the constant should be zeros.

I changed the variable name to ZEROS as it is a constant.

Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.02-03/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.03/

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

Hi Brian!

A couple of comments

1)
3974 if (signum == 0) {
3975 buf.append('0');
3976 return;
3977 }

Shouldn't it be padded with zeroes, if digits > 0?
If I'm not mistaken, it could happen if result[1] at the end of 
toString() happens to be ZERO.


It that's true, then it may be a good idea to add a testcase for a 
number with many trailing zeros in a string representation.
Currently, test/jdk/java/math/BigInteger/BigIntegerTest.java in 
stringConv() operates on random numbers, which are unlikely to have huge 
number of trailing zeros.


2)
4120 /* zero is a string of NUM_ZEROS consecutive zeros. */
4121 private static final String zeros = "0".repeat(NUM_ZEROS);

Nit in the comment:  name of the constant should be zero*s*.

With kind regards,
Ivan


On 8/21/19 5:28 PM, Brian Burkhalter wrote:

Hello,


On Aug 20, 2019, at 4:31 PM, Brian Burkhalter  
wrote:


On Aug 20, 2019, at 2:45 PM, Ivan Gerasimov mailto:ivan.gerasi...@oracle.com>> wrote:

Would it make sense to add an argument `digits` to smallToString (like the same 
named argument of toString, the minimum number of digits to pad to), so it 
could zero-pad the result itself?

This way we could avoid inserting zeros into the middle of a StringBuilder 
after a call to smallToString.

Indeed I do not like the zero insertion either. I’ll investigate your idea.

I modified the patch so that characters are exclusively appended to the 
StringBuilder thereby eliminating copying of characters which are already 
present after the insertion point, viz., the padding with zeros after calling 
smallToString() in the recursive path. A delta versus version .01 is at [1] and 
the diff versus the tip at [2].

Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.01-02/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.02/


--
With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Hello,

> On Aug 20, 2019, at 4:31 PM, Brian Burkhalter  
> wrote:
> 
>> On Aug 20, 2019, at 2:45 PM, Ivan Gerasimov > > wrote:
>> 
>> Would it make sense to add an argument `digits` to smallToString (like the 
>> same named argument of toString, the minimum number of digits to pad to), so 
>> it could zero-pad the result itself?
>> 
>> This way we could avoid inserting zeros into the middle of a StringBuilder 
>> after a call to smallToString.
> 
> Indeed I do not like the zero insertion either. I’ll investigate your idea.

I modified the patch so that characters are exclusively appended to the 
StringBuilder thereby eliminating copying of characters which are already 
present after the insertion point, viz., the padding with zeros after calling 
smallToString() in the recursive path. A delta versus version .01 is at [1] and 
the diff versus the tip at [2].

Thanks,

Brian

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.01-02/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.02/

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Hi Ivan,

> On Aug 20, 2019, at 2:45 PM, Ivan Gerasimov  wrote:
> 
> Would it make sense to add an argument `digits` to smallToString (like the 
> same named argument of toString, the minimum number of digits to pad to), so 
> it could zero-pad the result itself?
> 
> This way we could avoid inserting zeros into the middle of a StringBuilder 
> after a call to smallToString.

Indeed I do not like the zero insertion either. I’ll investigate your idea.

Thanks,

Brian

> On 8/20/19 11:51 AM, Brian Burkhalter wrote:
>> Delta [1] and revised [2] patches:
>> 
>> [1] http://cr.openjdk.java.net/~bpb/8229845/webrev.00-01/ 
>> 
>> [2] http://cr.openjdk.java.net/~bpb/8229845/webrev.01/ 
>> 

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

> On Aug 20, 2019, at 2:58 PM, Claes Redestad  wrote:
> 
> On 2019-08-20 23:56, Claes Redestad wrote:
>> On 2019-08-20 10:05, Aleksey Shipilev wrote:
>>> 
>>>   *) This might be "static final", while we are at it:
>>> 
>>> 4109 private static String[] zeros = new String[64];
>> Addressed by http://cr.openjdk.java.net/~redestad/8228581/open.00/ 
>> 
> 
> Meant to link the review thread, not the webrev:
> 
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2019-July/061520.html 
> 
Looks like we have a small collision. ;-)

Thanks,

Brian

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Claes Redestad]

On 2019-08-20 23:56, Claes Redestad wrote:

On 2019-08-20 10:05, Aleksey Shipilev wrote:


  *) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


Addressed by http://cr.openjdk.java.net/~redestad/8228581/open.00/


Meant to link the review thread, not the webrev:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2019-July/061520.html

/Claes

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Claes Redestad]

On 2019-08-20 10:05, Aleksey Shipilev wrote:


  *) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


Addressed by http://cr.openjdk.java.net/~redestad/8228581/open.00/

/Claes

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

Hi Brian!

Would it make sense to add an argument `digits` to smallToString (like 
the same named argument of toString, the minimum number of digits to pad 
to), so it could zero-pad the result itself?


This way we could avoid inserting zeros into the middle of a 
StringBuilder after a call to smallToString.


With kind regards,
Ivan

On 8/20/19 11:51 AM, Brian Burkhalter wrote:

Delta [1] and revised [2] patches:

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.00-01/
[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.01/

On Aug 20, 2019, at 1:05 AM, Aleksey Shipilev > wrote:


On 8/19/19 10:08 PM, Brian Burkhalter wrote:

[2]http://cr.openjdk.java.net/~bpb/8229845/webrev.00/


Two drive-by comments:

*) It seems the "signum == 0" case in smallToString is regressing? 
Before, it just returned the

constant-pooled "0", now it goes via StringBuilder;


Yes, and I don’t see any way not to have it do so. Note that due to 
lines 3933-3936 in [2] this case will never be hit for values which 
have no more than 20 ints in their magnitude, i.e., those which do not 
recurse in toString(BigInteger,StringBuilder,int,int).



*) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


Above made final at L4111 in [2].

On Aug 20, 2019, at 10:28 AM, Ivan Gerasimov 
mailto:ivan.gerasi...@oracle.com>> wrote:


While we're here.

On 8/20/19 1:05 AM, Aleksey Shipilev wrote:

 *) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


It may make sense to create the only string as

private static final String zeros = "0".repeat(63);


Changed at L4111 in [2].


and then replace all

sb.append(zeros[x]) with sb.append(zeros, 0, x) and


L4006 in [2].


sb.insert(pos, zeros[x]) with sb.insert(pos, zeros, 0, x).


L4049 and L4054 in [2].

The difference would be in one extra bounds check, and as both 
append() and insert() are relatively expensive, this check would 
hardly be noticeable.


Thanks,

Brian


--
With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Brian Burkhalter]

Delta [1] and revised [2] patches:

[1] http://cr.openjdk.java.net/~bpb/8229845/webrev.00-01/ 

[2] http://cr.openjdk.java.net/~bpb/8229845/webrev.01/

> On Aug 20, 2019, at 1:05 AM, Aleksey Shipilev  wrote:
> 
> On 8/19/19 10:08 PM, Brian Burkhalter wrote:
>> [2] http://cr.openjdk.java.net/~bpb/8229845/webrev.00/ 
>> 
> 
> Two drive-by comments:
> 
> *) It seems the "signum == 0" case in smallToString is regressing? Before, it 
> just returned the
> constant-pooled "0", now it goes via StringBuilder;

Yes, and I don’t see any way not to have it do so. Note that due to lines 
3933-3936 in [2] this case will never be hit for values which have no more than 
20 ints in their magnitude, i.e., those which do not recurse in 
toString(BigInteger,StringBuilder,int,int).

> *) This might be "static final", while we are at it:
> 
> 4109 private static String[] zeros = new String[64];

Above made final at L4111 in [2].

> On Aug 20, 2019, at 10:28 AM, Ivan Gerasimov  
> wrote:
> 
> While we're here.
> 
> On 8/20/19 1:05 AM, Aleksey Shipilev wrote:
>>  *) This might be "static final", while we are at it:
>> 
>> 4109 private static String[] zeros = new String[64];
>> 
> It may make sense to create the only string as
> 
> private static final String zeros = "0".repeat(63);

Changed at L4111 in [2].

> and then replace all
> 
> sb.append(zeros[x]) with sb.append(zeros, 0, x) and

L4006 in [2].

> sb.insert(pos, zeros[x]) with sb.insert(pos, zeros, 0, x).

L4049 and L4054 in [2].

> The difference would be in one extra bounds check, and as both append() and 
> insert() are relatively expensive, this check would hardly be noticeable.


Thanks,

Brian

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Ivan Gerasimov]

While we're here.

On 8/20/19 1:05 AM, Aleksey Shipilev wrote:

  *) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


It may make sense to create the only string as

private static final String zeros = "0".repeat(63);

and then replace all

sb.append(zeros[x]) with sb.append(zeros, 0, x) and

sb.insert(pos, zeros[x]) with sb.insert(pos, zeros, 0, x).

The difference would be in one extra bounds check, and as both append() 
and insert() are relatively expensive, this check would hardly be 
noticeable.


--

With kind regards,
Ivan Gerasimov

Re: 8229845: Decrease memory consumption of BigInteger.toString()

[Aleksey Shipilev]

On 8/19/19 10:08 PM, Brian Burkhalter wrote:
> [2] http://cr.openjdk.java.net/~bpb/8229845/webrev.00/

Two drive-by comments:

 *) It seems the "signum == 0" case in smallToString is regressing? Before, it 
just returned the
constant-pooled "0", now it goes via StringBuilder;

 *) This might be "static final", while we are at it:

4109 private static String[] zeros = new String[64];


-- 
Thanks,
-Aleksey