RFR: 8149330: Capacity of StringBuilder should not get close to Integer.MAX_VALUE unless necessary

[Ivan Gerasimov]

On 23.02.2016 9:23, Martin Buchholz wrote:
> Thanks, Ivan.
>
> I see that the capacity growth x -> 2*x + 2 is mandated by the spec,
> so we can't change that.  Growing by more than a factor of two may
> mean that the "overflow-conscious" code I originally wrote may need
> more checks than ArrayList, where growing by 3/2 provides some sanity.

Right.
Though checking the newCapacity is non-positive should suffice to catch 
overflow in *2+2 formula.

While writing this, I just noticed that I actually made a mistake when 
did newCapacity < 0 check.
This wouldn't catch the overflow when the oldCapacity happens to be 
Integer.MAX_VALUE (which is not possible with the current hotspot, but 
may become an issue one day).

The webrev is updated with this correction:
http://cr.openjdk.java.net/~igerasim/8149330/02/webrev/


To make myself confident with the fix, I extracted the new code for 
calculating new capacity and ran it in a loop for each value from 0 to 
Integer.MAX_VALUE and checked that the result is as expected.
I don't see how it can be turned into a test, however.  So, I created a 
test that just verifies the specific bug is fixed.

> ---
>
> Looking at the compact string code for the first time, I wonder that
> replacing a char[] with a byte[] has effectively reduced the capacity
> by 2, when non-LATIN1 is stored.  If you wanted to preserve the
> maximum capacity, you would need to use a char[] for storage as
> before?
Probably yes.
I don't plan to address this at the moment.
The goals of the fix is to make the code work better and to keep the 
solution local, so it can be easier to port it back to jdk8u.

Sincerely yours,
Ivan

> ----
>
> Anyways, AbstractStringBuilder looks even trickier to get right than
> ArrayList or Vector.
>
> On Mon, Feb 22, 2016 at 3:36 PM, Ivan Gerasimov
> <ivan.gerasimov at oracle.com> wrote:
>>
>> On 22.02.2016 22:49, Martin Buchholz wrote:
>>> Can you make the code look more like the recently optimized code in
>>> ArrayList and Vector?
>>
>> Sure.  Please find the updated webrev below.
>> Of course, there are nuances, as we need to deal with the compact strings,
>> so the code isn't quite the same as in ArrayList.
>>
>> http://cr.openjdk.java.net/~igerasim/8149330/01/webrev/
>>
>> Sincerely yours,
>> Ivan
>>
>>
>>> On Mon, Feb 22, 2016 at 11:20 AM, Ivan Gerasimov
>>> <ivan.gerasimov at oracle.com> wrote:
>>>> Hello!
>>>>
>>>> When the capacity of a StringBuilder needs to be increased (either due to
>>>> append() or due to explicit call to ensureCapacity()), the new capacity
>>>> is
>>>> calculated as "twice the old capacity, plus 2", rounded down to
>>>> Integer.MAX_VALUE:
>>>>
>>>> http://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html#ensureCapacity-int-
>>>> Because of that, StringBuilder throws OOM early, even though there may be
>>>> room to grow.
>>>>
>>>> The proposed solution is to reserve a few bytes at the top of the range
>>>> and
>>>> only try to allocate them if absolutely required.
>>>>
>>>> The regression test is @ignored by default, as it is too greedy for
>>>> memory.
>>>>
>>>> Would you please help review the fix?
>>>>
>>>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8149330
>>>> WEBREV: http://cr.openjdk.java.net/~igerasim/8149330/00/webrev/
>>>>
>>>> Sincerely yours,
>>>> Ivan
>>