Hi Rémi! On 25.05.2015 0:23, Remi Forax wrote:

Hi Ivan, I will let people to comment on your first version but your second version uses a Stream and some lambdas which is in my opinion not a good idea in term of dependencies (Stream will be loaded too soon by example) and it may create some trouble in the future because lambdas depends on some classes of java.lang.invoke that are initialized late in the boot process while java.lang.String is initialized early.

Good point. It could be rewritten using anonymous class instead. Though, I still like the first version better :-) Sincerely yours, Ivan

cheers, Rémi

On 05/24/2015 10:17 PM, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

Thank you Mark for looking at this! On 26.05.2015 18:39, mark.reinhold@oracle.com wrote:

Your micro-benchmark improvements are significant, but do you have evidence to suggest that the performance of this method is actually critical to real applications?

In other words, is the added code complexity really worth it?

The enhancement request contains a few links to the discussions of this method's performance at open forums. The most frequent suggestion is to use alternatives from 3rd party libraries. That should prove the benefits of this fix -- by improving performance we can keep some users from moving away from JDK :) grep shows that langtools would also benefit from making replace() faster. Sincerely yours, Ivan

- Mark

Thank you Roger for looking at this! On 26.05.2015 19:40, Roger Riggs wrote:

Hi Ivan,

Did you consider doing the optimization inside of Pattern.compile/replaceAll. That would have a broader impact and benefit.

In Pattern.compile the flag LITERAL can be combined with several other flags, which makes things more complex. However, in String.replace we've got a special case, which can be optimized in a straight-forward (though a little bit verbose) way. Sincerely yours, Ivan

Roger

On 5/26/2015 12:36 PM, Ivan Gerasimov wrote:

...

Thank you Mark for looking at this!

On 26.05.2015 18:39, mark.reinhold@oracle.com wrote:

...

Your micro-benchmark improvements are significant, but do you have evidence to suggest that the performance of this method is actually critical to real applications?

In other words, is the added code complexity really worth it?

The enhancement request contains a few links to the discussions of this method's performance at open forums. The most frequent suggestion is to use alternatives from 3rd party libraries.

That should prove the benefits of this fix -- by improving performance we can keep some users from moving away from JDK :)

grep shows that langtools would also benefit from making replace() faster.

Sincerely yours, Ivan

...

- Mark

I second that. API accepts CharSequence for a reason. The benchmarks might look a little different if you pass StringBuilder in a call to replace. It looks like removing toString() call on CharSequences will be easy with one drawback of loosing the benefit of System.arraycopy call. Note that String.indexOf requires String argument but that can also be fixed. -- Tomasz On Tue, May 26, 2015 at 7:17 PM, Xueming Shen <xueming.shen@oracle.com> wrote:

On 5/26/15 10:08 AM, Ivan Gerasimov wrote:

...

Thank you Roger for looking at this!

On 26.05.2015 19:40, Roger Riggs wrote:

...

Hi Ivan,

Did you consider doing the optimization inside of Pattern.compile/replaceAll. That would have a broader impact and benefit.

In Pattern.compile the flag LITERAL can be combined with several other flags, which makes things more complex. However, in String.replace we've got a special case, which can be optimized in a straight-forward (though a little bit verbose) way.

It probably makes big difference to access those characters via CharSequence.charAt() and the direct internal char[] access. Though avoiding allocating those objects created by Pattern/Matcher/SB definitely helps.

-Sherman

...

Sincerely yours, Ivan

Roger

...

On 5/26/2015 12:36 PM, Ivan Gerasimov wrote:

...

Thank you Mark for looking at this!

On 26.05.2015 18:39, mark.reinhold@oracle.com wrote:

...

Your micro-benchmark improvements are significant, but do you have evidence to suggest that the performance of this method is actually critical to real applications?

In other words, is the added code complexity really worth it?

The enhancement request contains a few links to the discussions of this method's performance at open forums. The most frequent suggestion is to use alternatives from 3rd party libraries.

That should prove the benefits of this fix -- by improving performance we can keep some users from moving away from JDK :)

grep shows that langtools would also benefit from making replace() faster.

Sincerely yours, Ivan

- Mark

...

-- Tomasz Kowalczewski

I know it was like that before :) I asked similar question about fixing String.contains to not call toString on it's CharSequence argument ( http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-March/032394.html). Responses were generally encouraging. Regards, Tomasz On Tue, May 26, 2015 at 7:39 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

But the current implementation converts the argument to String in the first place too:

return Pattern.compile(*target.toString()*, Pattern.LITERAL).matcher( this).replaceAll(Matcher.quoteReplacement( *replacement.toString()*));

So I didn't introduce this conversion :-)

When browsing the source code, looking for usages of this method, I only saw Strings passed as the parameters. Thus, I guess it is reasonable to have the variant which works best in this case.

Sincerely yours, Ivan

On 26.05.2015 20:26, Tomasz Kowalczewski wrote:

I second that. API accepts CharSequence for a reason. The benchmarks might look a little different if you pass StringBuilder in a call to replace. It looks like removing toString() call on CharSequences will be easy with one drawback of loosing the benefit of System.arraycopy call. Note that String.indexOf requires String argument but that can also be fixed.

-- Tomasz

On Tue, May 26, 2015 at 7:17 PM, Xueming Shen <xueming.shen@oracle.com> <xueming.shen@oracle.com> wrote:

On 5/26/15 10:08 AM, Ivan Gerasimov wrote:

Thank you Roger for looking at this!

On 26.05.2015 19:40, Roger Riggs wrote:

Hi Ivan,

Did you consider doing the optimization inside of Pattern.compile/replaceAll. That would have a broader impact and benefit.

In Pattern.compile the flag LITERAL can be combined with several other flags, which makes things more complex. However, in String.replace we've got a special case, which can be optimized in a straight-forward (though a little bit verbose) way.

It probably makes big difference to access those characters via CharSequence.charAt() and the direct internal char[] access. Though avoiding allocating those objects created by Pattern/Matcher/SB definitely helps.

-Sherman

Sincerely yours, Ivan

Roger

On 5/26/2015 12:36 PM, Ivan Gerasimov wrote:

Thank you Mark for looking at this!

On 26.05.2015 18:39, mark.reinhold@oracle.com wrote:

Your micro-benchmark improvements are significant, but do you have evidence to suggest that the performance of this method is actually critical to real applications?

In other words, is the added code complexity really worth it?

The enhancement request contains a few links to the discussions of this method's performance at open forums. The most frequent suggestion is to use alternatives from 3rd party libraries.

That should prove the benefits of this fix -- by improving performance we can keep some users from moving away from JDK :)

grep shows that langtools would also benefit from making replace() faster.

Sincerely yours, Ivan

- Mark

-- Tomasz Kowalczewski

Ivan, It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ... -Sherman On 5/26/15 4:11 PM, Ivan Gerasimov wrote:

I updated the webrev: http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here.

And I want to add that this proposed implementation is not only faster, but also more memory efficient. The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation.

---------------------------------------- public class C { public static void main(String[] args) throws Throwable { String s = "string"; for (int i = 1; i < Integer.MAX_VALUE; ++i) { try { s = s.replace("string", "stringstring"); } catch (OutOfMemoryError o) { System.out.println(i + ") " + s.length()); break; } } } } ----------------------------------------

$ time ~/java9/jdk/bin/java -showversion -Xmx1g C java version "1.9.0-ea" Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode)

25) 100663296

real 0m4.525s user 0m4.402s sys 0m1.189s

$ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode)

26) 201326592

real 0m2.139s user 0m1.960s sys 0m0.461s

Sincerely yours, Ivan

On 24.05.2015 23:17, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

On 05/27/2015 11:36 AM, Ivan Gerasimov wrote:

Hi Sherman!

Please take a look at my other webrev, that I provided in the first message. WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

I used StringJoiner there, which in some aspects seems to fit better here, comparing to StringBuilder. It does reduce the code, but of course runs slower. In that version every part of the source string had to be converted to a separate String, which add another redundant copying.

I still prefer the version, which deals with arrays. I don't think it's too complex. It surely adds some complexity to the original code, but it's only 70 lines of code in total. Everything else are comments and empty lines.

Sincerely yours, Ivan

Hi Ivan, If I was to choose, I would take the 1st variant (with index arrays) too. The speed does matter! But anyway, every now and then one would like to write an algorithm that gathers sub-strings and then either joins them or dumps them to some buffer that eventually becomes another string or array. Since String.substring() changed when offset/length fields were removed, there is no official way to handle sub-sequences as "vews" of underlying String. There was some debate in the past about using String's implementation of CharSequence.subSequence() for that purpose - to return a private CharSequence implementation that would represent a view of underlying String's array, but that was not pursued because of limiting API specification that says: "Returns a character sequence that is a subsequence of this sequence. An invocation of this method of the form str.subSequence(begin, end) behaves in exactly the same way as the invocation str.substring(begin, end)" My opinion is that this part of text did matter at the time when substring() did return a view over underlying array, but when the substring method changed, there was no reason to keep the specification bound to that text. It would have been wiser to keep the behavior unchanged and change the specification. Anyway, what's done is done. I don't know if String.subSequence can be changed now. Maybe? What could be done is introduce some new API. It could be in the form of a new class or just a static method (on CharSequence perhaps?) that would return a private implementation of CharSequence as a sub-sequence view over underlying CharSequence or String's array in case the passed-in argument is a String. With such API one could gather sub-sequence view objects into a LinkedList and then dump them into the correctly pre-sized StringBuilder. There could even be a String counstructor with the following signature: public String(Iterable<CharSequence> sequences, int estimatedLength) { ... ..which would eliminate the last copying step too. Hopefully all temporary view objects would be found as method-local and would be allocated on stack / in registers by JIT (wishful thinking)... Regards, Peter

On 27.05.2015 2:38, Xueming Shen wrote:

...

Ivan,

It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ...

-Sherman

On 5/26/15 4:11 PM, Ivan Gerasimov wrote:

...

I updated the webrev: http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here.

And I want to add that this proposed implementation is not only faster, but also more memory efficient. The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation.

---------------------------------------- public class C { public static void main(String[] args) throws Throwable { String s = "string"; for (int i = 1; i < Integer.MAX_VALUE; ++i) { try { s = s.replace("string", "stringstring"); } catch (OutOfMemoryError o) { System.out.println(i + ") " + s.length()); break; } } } } ----------------------------------------

$ time ~/java9/jdk/bin/java -showversion -Xmx1g C java version "1.9.0-ea" Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode)

25) 100663296

real 0m4.525s user 0m4.402s sys 0m1.189s

$ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode)

26) 201326592

real 0m2.139s user 0m1.960s sys 0m0.461s

Sincerely yours, Ivan

On 24.05.2015 23:17, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

Thank you Peter for looking at this! On 27.05.2015 16:15, Peter Levart wrote:

Hi Ivan,

How does this implementation compare to your's two regarding speed:

http://cr.openjdk.java.net/~plevart/jdk9-dev/String.replace/webrev.01/

You need to check for possible overflow here: 2287 resLen += repLen + ss.length();

It is not much shorter than your's first, but more object oriented ;-)

Well, the main difference is that you store the positions of substrings in a linked-list instead of an array. But arrays are more efficient. On small data the performance is almost the same as for the 'array' version: MyBenchmark.test thrpt 40 1'046'137.437 ± 13961.121 ops/s But on huge data the performance is much worse, comparing to even current implementation. Here are the results of running the stress test, I had posted earlier: ------------------------- time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode) 25) 100663296 real 0m12.945s user 0m15.670s sys 0m7.189s ------------------------- It took 6 times more time to complete, comparing to the current implementation, which uses regexp engine. Sincerely yours, Ivan

Regards, Peter

On 05/27/2015 11:36 AM, Ivan Gerasimov wrote:

...

Hi Sherman!

Please take a look at my other webrev, that I provided in the first message. WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

I used StringJoiner there, which in some aspects seems to fit better here, comparing to StringBuilder. It does reduce the code, but of course runs slower. In that version every part of the source string had to be converted to a separate String, which add another redundant copying.

I still prefer the version, which deals with arrays. I don't think it's too complex. It surely adds some complexity to the original code, but it's only 70 lines of code in total. Everything else are comments and empty lines.

Sincerely yours, Ivan

On 27.05.2015 2:38, Xueming Shen wrote:

...

Ivan,

It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ...

-Sherman

On 5/26/15 4:11 PM, Ivan Gerasimov wrote:

...

I updated the webrev: http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here.

And I want to add that this proposed implementation is not only faster, but also more memory efficient. The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation.

---------------------------------------- public class C { public static void main(String[] args) throws Throwable { String s = "string"; for (int i = 1; i < Integer.MAX_VALUE; ++i) { try { s = s.replace("string", "stringstring"); } catch (OutOfMemoryError o) { System.out.println(i + ") " + s.length()); break; } } } } ----------------------------------------

$ time ~/java9/jdk/bin/java -showversion -Xmx1g C java version "1.9.0-ea" Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode)

25) 100663296

real 0m4.525s user 0m4.402s sys 0m1.189s

$ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode)

26) 201326592

real 0m2.139s user 0m1.960s sys 0m0.461s

Sincerely yours, Ivan

On 24.05.2015 23:17, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

You might want to use directly sb.append.(char[], off, len), instead of append(str, off, len)/append(str). Btw, is the target.lenght==0 the popular use case/scenario? Just wonder why do we need a special case here for it. thanks, -Sherman On 5/27/15 8:29 AM, Ivan Gerasimov wrote:

For completeness, here's another webrev, which uses StringBuilder: http://cr.openjdk.java.net/~igerasim/8058779/03/webrev/

Its performance is somewhere in between the current implementation and the array-based implementation: MyBenchmark.test thrpt 40 796'059.192 ± 12455.970 ops/s

Memory efficiency is less then the one of array-based implementation: $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode)

25) 100663296

real 0m2.585s user 0m1.875s sys 0m0.887s

Sincerely yours, Ivan

On 27.05.2015 2:38, Xueming Shen wrote:

...

Ivan,

It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ...

-Sherman

On 5/26/15 4:11 PM, Ivan Gerasimov wrote:

...

I updated the webrev: http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here.

And I want to add that this proposed implementation is not only faster, but also more memory efficient. The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation.

---------------------------------------- public class C { public static void main(String[] args) throws Throwable { String s = "string"; for (int i = 1; i < Integer.MAX_VALUE; ++i) { try { s = s.replace("string", "stringstring"); } catch (OutOfMemoryError o) { System.out.println(i + ") " + s.length()); break; } } } } ----------------------------------------

$ time ~/java9/jdk/bin/java -showversion -Xmx1g C java version "1.9.0-ea" Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode)

25) 100663296

real 0m4.525s user 0m4.402s sys 0m1.189s

$ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode)

26) 201326592

real 0m2.139s user 0m1.960s sys 0m0.461s

Sincerely yours, Ivan

On 24.05.2015 23:17, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

The .append(srepl) -> append(srep.value) And I would simply remove the "fastpath" for the target.length() = 0 special case ... And maybe pick an appropriate initial size (maybe this.length + 16 * diff) for the sb to further reduce its internal expanding ... Personally this code is straightforward and I would be happy with the 800+ vs 1000+ score diff. public String replace(CharSequence target, CharSequence replacement) { String starget = target.toString(); int targLen = starget.length(); String srepl = replacement.toString(); int j = indexOf(starget); // special case: nothing to replace if (j< 0) { return this; } final char[] value = this.value; StringBuilder sb = new StringBuilder(); int i = 0; do { sb.append(value, i, j - i) .append(srepl.value); i = j + targLen; } while ((j = indexOf(starget, i))> 0); return sb.append(this, i, length()).toString(); } -Sherman On 05/27/2015 10:06 AM, Ivan Gerasimov wrote:

On 27.05.2015 18:44, Xueming Shen wrote:

...

You might want to use directly sb.append.(char[], off, len), instead of append(str, off, len)/append(str).

Ah, yes sure! It would improve things. I updated the webrev in place: http://cr.openjdk.java.net/~igerasim/8058779/03/webrev/

However the general picture is almost the same: performance: Baseline: MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s StringBuilder: MyBenchmark.test thrpt 40 808'033.808 ± 22152.166 ops/s Arrays: MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

Memory efficiency is still less then for array-version: $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode)

25) 100663296

real 0m2.429s user 0m2.112s sys 0m0.792s

Sincerely yours, Ivan

...

Btw, is the target.lenght==0 the popular use case/scenario? Just wonder why do we need a special case here for it.

thanks, -Sherman

On 5/27/15 8:29 AM, Ivan Gerasimov wrote:

...

For completeness, here's another webrev, which uses StringBuilder: http://cr.openjdk.java.net/~igerasim/8058779/03/webrev/

Its performance is somewhere in between the current implementation and the array-based implementation: MyBenchmark.test thrpt 40 796'059.192 ± 12455.970 ops/s

Memory efficiency is less then the one of array-based implementation: $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode)

25) 100663296

real 0m2.585s user 0m1.875s sys 0m0.887s

Sincerely yours, Ivan

On 27.05.2015 2:38, Xueming Shen wrote:

...

Ivan,

It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ...

-Sherman

On 5/26/15 4:11 PM, Ivan Gerasimov wrote:

...

I updated the webrev: http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here.

And I want to add that this proposed implementation is not only faster, but also more memory efficient. The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation.

---------------------------------------- public class C { public static void main(String[] args) throws Throwable { String s = "string"; for (int i = 1; i < Integer.MAX_VALUE; ++i) { try { s = s.replace("string", "stringstring"); } catch (OutOfMemoryError o) { System.out.println(i + ") " + s.length()); break; } } } } ----------------------------------------

$ time ~/java9/jdk/bin/java -showversion -Xmx1g C java version "1.9.0-ea" Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode)

25) 100663296

real 0m4.525s user 0m4.402s sys 0m1.189s

$ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode)

26) 201326592

real 0m2.139s user 0m1.960s sys 0m0.461s

Sincerely yours, Ivan

On 24.05.2015 23:17, Ivan Gerasimov wrote:

...

Hello everybody!

I know many people here like it when the performance is getting better. It was suggested to make the literal variant of String.replace() faster. Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code.

I've created two versions of the fix. In the first one, we scan the string and store indices of the found substrings in an array. Then, we allocate the precisely sized char array and fill it it. The case with the empty target has to be handled separately.

BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/

The second variant is much less verbose, however it's less efficient too. Here the StringJoiner is used as an intermediate storage.

WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/

Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). 0) Baseline MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s

1) Heavy-duty +308% MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

2) StringJoiner +190% MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s

Personally, I like my first variant better, even though it adds almost 300 lines of code. But I'd like to hear what people think of it.

Sincerely yours, Ivan

targLen = max(1, tagLen); ? On 05/27/2015 10:59 AM, Ivan Gerasimov wrote:

On 27.05.2015 20:40, Xueming Shen wrote:

...

The .append(srepl) -> append(srep.value)

And I would simply remove the "fastpath" for the target.length() = 0 special case ... And maybe pick an appropriate initial size (maybe this.length + 16 * diff) for the sb to further reduce its internal expanding ...

Sorry, I forgot to comment this. This is not really a fastpath. This is a special case, which isn't handled by the general algorithm. We can modify the general algorithm, of course to handle empty target, but I thought it would be more clear to have a separate branch.

I think your variant below would loop forever in the loop with an empty target: i = j + targLen; // targLen == 0 j = indexOf(starget, i) // j == i

Sincerely yours, Ivan

...

Personally this code is straightforward and I would be happy with the 800+ vs 1000+ score diff.

public String replace(CharSequence target, CharSequence replacement) { String starget = target.toString(); int targLen = starget.length(); String srepl = replacement.toString();

int j = indexOf(starget); // special case: nothing to replace if (j< 0) { return this; }

final char[] value = this.value; StringBuilder sb = new StringBuilder(); int i = 0; do { sb.append(value, i, j - i) .append(srepl.value); i = j + targLen; } while ((j = indexOf(starget, i))> 0);

return sb.append(this, i, length()).toString(); }

-Sherman

On 05/27/2015 10:06 AM, Ivan Gerasimov wrote:

...

On 27.05.2015 18:44, Xueming Shen wrote:

...

You might want to use directly sb.append.(char[], off, len), instead of append(str, off, len)/append(str).

Ah, yes sure! It would improve things. I updated the webrev in place: http://cr.openjdk.java.net/~igerasim/8058779/03/webrev/

However the general picture is almost the same: performance: Baseline: MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s StringBuilder: MyBenchmark.test thrpt 40 808'033.808 ± 22152.166 ops/s Arrays: MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s

Memory efficiency is still less then for array-version: $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode)

25) 100663296

real 0m2.429s user 0m2.112s sys 0m0.792s

Sincerely yours, Ivan

...

Btw, is the target.lenght==0 the popular use case/scenario? Just wonder why do we need a special case here for it.

thanks, -Sherman

On 5/27/15 8:29 AM, Ivan Gerasimov wrote:

...

For completeness, here's another webrev, which uses StringBuilder: http://cr.openjdk.java.net/~igerasim/8058779/03/webrev/

Its performance is somewhere in between the current implementation and the array-based implementation: MyBenchmark.test thrpt 40 796'059.192 ± 12455.970 ops/s

Memory efficiency is less then the one of array-based implementation: $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C java version "1.9.0-internal" Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00) Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_27_14_47-b00, mixed mode)

25) 100663296

real 0m2.585s user 0m1.875s sys 0m0.887s

Sincerely yours, Ivan

On 27.05.2015 2:38, Xueming Shen wrote:

...

Ivan,

It might be worth trying String.index + StringBuilder, instead of writing/handling everything yourself. Yes, it inevitably adds an arraycopy at the end to convert the StrinbBuilder to String, but it might have better balance between performance and code complexity. The regex is probably a little heavy for literal string replacement, but StringBuilder should not be that bad ...

-Sherman

On 5/26/15 4:11 PM, Ivan Gerasimov wrote: > I updated the webrev: > http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/ > > In the check at 2300-2301 and 2351-2352 I replaced MAX_ARRAY_SIZE with Integer.MAX_VALUE, which seems to be more accurate here. > > And I want to add that this proposed implementation is not only faster, but also more memory efficient. > The following simple stress-test shows that the proposed version is able to handle twice larger strings, comparing to the current implementation. > > ---------------------------------------- > public class C { > public static void main(String[] args) throws Throwable { > String s = "string"; > for (int i = 1; i < Integer.MAX_VALUE; ++i) { > try { > s = s.replace("string", "stringstring"); > } catch (OutOfMemoryError o) { > System.out.println(i + ") " + s.length()); > break; > } > } > } > } > ---------------------------------------- > > $ time ~/java9/jdk/bin/java -showversion -Xmx1g C > java version "1.9.0-ea" > Java(TM) SE Runtime Environment (build 1.9.0-ea-b63) > Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b63, mixed mode) > > 25) 100663296 > > real 0m4.525s > user 0m4.402s > sys 0m1.189s > > $ time ~/java9/jdk-build/bin/java -showversion -Xmx1g C > java version "1.9.0-internal" > Java(TM) SE Runtime Environment (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00) > Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-internal-igerasim_2015_05_23_19_25-b00, mixed mode) > > 26) 201326592 > > real 0m2.139s > user 0m1.960s > sys 0m0.461s > > Sincerely yours, > Ivan > > On 24.05.2015 23:17, Ivan Gerasimov wrote: >> Hello everybody! >> >> I know many people here like it when the performance is getting better. >> It was suggested to make the literal variant of String.replace() faster. >> Currently, this method is implemented as a few calls to regexp API, so that the whole implementation takes only two lines of code. >> >> I've created two versions of the fix. >> In the first one, we scan the string and store indices of the found substrings in an array. >> Then, we allocate the precisely sized char array and fill it it. >> The case with the empty target has to be handled separately. >> >> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8058779 >> WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/00/webrev/ >> >> The second variant is much less verbose, however it's less efficient too. >> Here the StringJoiner is used as an intermediate storage. >> >> WEBREV: http://cr.openjdk.java.net/~igerasim/8058779/01/webrev/ >> >> >> Here are the micro-benchmark results (in a string of ~300 chars do ~15 replacements). >> 0) Baseline >> MyBenchmark.test thrpt 40 257'051.948 ± 4537.484 ops/s >> >> 1) Heavy-duty +308% >> MyBenchmark.test thrpt 40 1'049'235.602 ± 15501.803 ops/s >> >> 2) StringJoiner +190% >> MyBenchmark.test thrpt 40 746'000.629 ± 15387.036 ops/s >> >> >> Personally, I like my first variant better, even though it adds almost 300 lines of code. >> But I'd like to hear what people think of it. >> >> Sincerely yours, >> Ivan >> >> >

On 05/27/2015 12:43 PM, Ivan Gerasimov wrote:

On 27.05.2015 21:08, Xueming Shen wrote:

...

targLen = max(1, tagLen); ?

Well, almost :) With such targLen, (i = j + targLen) would result in i == length() + 1, which will cause IOOBE in the following append().

I'm sure the algorithms can be adopted to run correctly with empty target, it just needs some accurate checking.

But why can't we consider the first variant of replace()? http://cr.openjdk.java.net/~igerasim/8058779/02/webrev/

It's still faster and it can handle larger strings without OOME. I think this is important.

I haven't heard any critics of it except for its relative complexity, comparing to the original code. And we have a backup variant with StringBuilder, if problems are found.

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

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

Thanks! I'll simplify this check for overflow, as you're suggesting. Sincerely yours, Ivan On 31.05.2015 10:01, Xueming Shen wrote:

On 5/30/2015 11:38 PM, Peter Levart wrote:

...

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

agreed.

On 31.05.2015 13:28, Ulf Zibis wrote:

Am 31.05.2015 um 08:38 schrieb Peter Levart:

...

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(); }

Hm, what has this situation to do with Out-Of-Memory ?

That should indicate that we were about to try to allocate an array of size > Integer.MAX_VALUE. E.g. java.util.AbstractCollection.java: private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError ("Required array size too large");

In other words, IMHO NegativeArraySizeException is much better here and additionally saves performance. Additionally you could propagate it to InvalidArgumentException.

I don't think it is InvalidArgument case. It just happens that the result is larger then allowed, so let's throw OOM! Sincerely yours, Ivan

-Ulf

Hi Remi! On 31.05.2015 11:43, Remi Forax wrote:

I agree with the others the code is more readable.

There is a slightly difference between the current behavior and the behavior of the proposed code, "foo".replace("bar", null) should throw a NPE because replacement is null but the proposed code will return "foo" because replacement.toString() is called after the short-circuit test (j < 0).

Yes, you're right, thanks for catching it! And the regression test should have caught that, but I only had "a".replace("a", null) there, which passed. I fixed the code and added the case to the regression test in the new webrev.

so the first part of the code should be: String starget = target.toString(); // implict nullcheck String srepl = replacement.toString(); // implicit nullcheck int j = indexOf(starget); if (j < 0) { return this; } ...

also 'i' can be initialized just before the 'do', there is no point to initialize it before.

To finish, the two 'final' are useless here but i suppose it's a matter of style :)

I moved declaration of i just to save a line. I don't think it decreased performance. Declaring the 'value' variable final was suggested by Martin, and I think it is reasonable (see http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-March/032601.html). The other variable is final just for symmetry :) Sincerely yours, Ivan

cheers, Rémi

On 05/31/2015 04:19 AM, 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

Hi, Am 31.05.2015 um 18:03 schrieb Ivan Gerasimov:

On 31.05.2015 18:54, Ivan Gerasimov wrote:

...

I fixed the code and added the case to the regression test in the new webrev.

Which is right here: http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/

Shoudn't the user be informed via javadoc about the risk of an OutOfMemoryError, just from illegal arguments of this method? Example: this.value.length() = 100 target.value.length() = 200 replacement.value.length() = 50 results in: newLenHint = -500 --> OutOfMemoryError In other words, is this a good reason to throw such an Error? Little nit: Indentation for line continuation should be 8 spaces. -Ulf

On May 31, 2015, at 6:03 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

...

Which is right here: http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/

Much better. For the test can you use RandomFactory recently added to the test library? Paul.

Ivan, The code looks fine for me. Just wonder what's the motivation of using the newStringUnsafe() in the test case. Simply to save the char[] copy to speed up the test? I don't think we really care about it here, right? -Sherman On 06/01/2015 11:53 AM, Ivan Gerasimov wrote:

On 01.06.2015 11:33, Paul Sandoz wrote:

...

On May 31, 2015, at 6:03 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

...

Which is right here: http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/

Much better.

For the test can you use RandomFactory recently added to the test library?

Sure. Here the updated webrev with this change and a few other minor changes. http://cr.openjdk.java.net/~igerasim/8058779/06/webrev/

The changes are: - move declaration of i below, - indent .append(), - use RandomFactory in the test, - extend number of test cases with null input.

Do you think it's ready to go?

Sincerely yours, Ivan

...

Paul.

On Jun 1, 2015, at 8:53 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

On 01.06.2015 11:33, Paul Sandoz wrote:

...

On May 31, 2015, at 6:03 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

...

Which is right here: http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/

Much better.

For the test can you use RandomFactory recently added to the test library?

Sure. Here the updated webrev with this change and a few other minor changes. http://cr.openjdk.java.net/~igerasim/8058779/06/webrev/

The changes are: - move declaration of i below, - indent .append(), - use RandomFactory in the test, - extend number of test cases with null input.

Do you think it's ready to go?

Almost :-) Like Sherman i think you should get rid of JavaLangAccess.newStringUnsafe. 78 @Test(dataProvider="sourceTargetReplacementWithNull") You can use the "expectedExceptions" attribute instead of an explicit try/fail/catch. 79 public void testNPE(String source, String target, String replacement) { 80 try { 81 source.replace(target, replacement); 82 fail("Expected to throw NPE: " + source + ".replace(" + target + 83 "," + replacement + ")"); 84 } catch (NullPointerException npe) { 85 } 86 } You could simplify the data provider sourceTargetReplacementWithNull, there is no point testing with a null source. String.replace accepts two arguments, each can be either null or non-null. Thats 2 bits of state, so one can simply be explicit and presumably it should not matter what the non-null argument value (there are enough non-null values supplied by the other data providers): {null, null} {null, "foo"} {"foo", null} No need for another review for any of these. Paul.

On Jun 2, 2015, at 10:56 AM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

...

You could simplify the data provider sourceTargetReplacementWithNull, there is no point testing with a null source. String.replace accepts two arguments, each can be either null or non-null. Thats 2 bits of state, so one can simply be explicit and presumably it should not matter what the non-null argument value (there are enough non-null values supplied by the other data providers):

{null, null} {null, "foo"} {"foo", null}

I agree there is not much value in testing the case source == null, so it can be removed. However, I would leave other test cases. Earlier in this thread Rémi spotted a bug, which had been observed in a call "bar".replace("foo", null), but not in "foo".replace("foo", null).

Ok, presumably for the same identity rather than value? Paul.

Looks Ok to me, thumb up :) Rémi On 06/01/2015 08:53 PM, Ivan Gerasimov wrote:

On 01.06.2015 11:33, Paul Sandoz wrote:

...

On May 31, 2015, at 6:03 PM, Ivan Gerasimov <ivan.gerasimov@oracle.com> wrote:

...

Which is right here: http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/

Much better.

For the test can you use RandomFactory recently added to the test library?

Sure. Here the updated webrev with this change and a few other minor changes. http://cr.openjdk.java.net/~igerasim/8058779/06/webrev/

The changes are: - move declaration of i below, - indent .append(), - use RandomFactory in the test, - extend number of test cases with null input.

Do you think it's ready to go?

Sincerely yours, Ivan

...

Paul.

Hi Ivan, <nitpicking mode="on"/> Le 31 mai 2015 17:54:35 CEST, Ivan Gerasimov <ivan.gerasimov@oracle.com> a écrit :

Hi Remi!

On 31.05.2015 11:43, Remi Forax wrote:

...

I agree with the others the code is more readable.

There is a slightly difference between the current behavior and the behavior of the proposed code, "foo".replace("bar", null) should throw a NPE because replacement is null but the proposed code will return "foo" because replacement.toString() is called after the short-circuit test

...

(j < 0).

Yes, you're right, thanks for catching it! And the regression test should have caught that, but I only had "a".replace("a", null) there, which passed.

I fixed the code and added the case to the regression test in the new webrev.

...

so the first part of the code should be: String starget = target.toString(); // implict nullcheck String srepl = replacement.toString(); // implicit nullcheck int j = indexOf(starget); if (j < 0) { return this; } ...

also 'i' can be initialized just before the 'do', there is no point to initialize it before.

To finish, the two 'final' are useless here but i suppose it's a matter of style :)

I moved declaration of i just to save a line. I don't think it decreased performance.

I don't think so too. It decrease readability, when you read the code of the loop you have to scroll up to find the initialization of 'i' like in plain old good C.

Declaring the 'value' variable final was suggested by Martin, and I think it is reasonable (see http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-March/032601.html). The other variable is final just for symmetry :)

Either i read the code in an IDE and local variables and fields do not have the same color or i read diff and in that case fields are usually not visible. For me, final on local variable is just noise. But as i said it's a matter of taste.

Sincerely yours, Ivan

cheers, Rémi

...

cheers, Rémi

On 05/31/2015 04:19 AM, 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