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

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.MAXVALUE - 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