8058779: Faster implementation of String.replace(CharSequence, CharSequence)

Peter Levart peter.levart at gmail.com
Sun May 31 06:38:31 UTC 2015



On 05/31/2015 06:34 AM, Xueming Shen wrote:
> On 5/30/15 7:19 PM, Ivan Gerasimov wrote:
>> Hi everyone!
>>
>> Here's another webrev, in which replace() is implemented with 
>> StringBuilder.
>> On my benchmark it is almost as fast as the version backed with 
>> arrays, but this variant is much shorter.
>>
>> Credits to Sherman for combining the general algorithm with the case 
>> of empty target.
>>
>> Comments, further suggestions are welcome!
>>
>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779
>> WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/04/webrev/
>>
>> Sincerely yours,
>> Ivan
>>
>
> This is one is much better:-) I would suggest to leave the 
> "overflow-conscious" code to the StringBuilder.
> The same range check is being done inside ABS every time the repl 
> string is appended into the buffer,
> it does not appear to be very helpful to have a redundant check here. 
> And it seems this check only works
> for the single appearance of target string.
>
> 2260         // overflow-conscious code
> 2261         if (value.length - targLen > Integer.MAX_VALUE - 
> replValue.length) {
> 2262             throw new OutOfMemoryError();
> 2263         }
>

Hi,

Yes, this one is much easier to grasp.

As I understand the check is to avoid overflow in calculation of 
StringBuilder initial capacity (newLenHint). If overflow happened, 
newLenHint would be negative and StringBuilder construction would fail 
with NegativeArraySizeException. But the calculation of newLenHint:

     int newLenHint = value.length - targLen + replValue.length;

...considering the following:

     value.length >= 0
     targLength >= 0
     replValue.length >= 0
     targLength <= value.length

in case of overflow, it can only produce a negative value. So the check 
could simply be:

     if (newLenHint < 0) {
         throw new OutOfMemoryError();
     }

Right?

Regards, Peter




More information about the core-libs-dev mailing list