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

[Ivan Gerasimov]

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