String.replaceは思ったほど速くない

一般的にJavaで何度も同じ文字列置換を行う際には、正規表現による置換が必要であればString.replaceAllではなくPattern.compileしたPatternインスタンスを使いまわし、固定文字列による置換で事足りるのであれば単にString.replaceで置換するという使い方が多いと思います。

private String regex = ...
private Patten pattern = Pattern.compile(regex);
private String masking(String input) {
    input = input.replace("yyy", "XXX");
    // input = input.replaceAll(regex, "xxx"); は遅いので書き換え
    input = pattern.matcher(input).replaceAll("xxx");
    return input;
}

これはreplaceAllの正規表現置換は結局Patternクラスを使用していて、呼び出しのたびにPattern.compileされていることが知られている一方で、固定文字列のreplaceは高速な検索・置換が可能だと考えられるからです。常識的に考えて。
しかし実際にはString.replaceはこのような実装になっています。（OpenJDK/OracleJDK:8u40）

java.lang.Stringより抜粋

public String replace(CharSequence target, CharSequence replacement) {
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
            this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}

驚きの手抜き実装です。なにか理由があるんでしょうか。チケットが発行されているのを見る限り、たぶんないんだと思いますが…
https://bugs.openjdk.java.net/browse/JDK-8058779

replaceの速度が欲しい場合はApache Commons LangのStringUtils.replaceを使うなどで逃げるようです。自分で適当にindexOfとStringBuilderでサクッと作ってもいいかもしれません。たとえばこんな感じ。

private static String replaceByHand(final String original, final String old, final String replace) {
	int offset = 0;
	StringBuilder builder = new StringBuilder(original.length());
	int index;
	while (0 <= (index = original.indexOf(old, offset))) {
		builder.append(original, offset, index);
		builder.append(replace);
		offset = index + old.length();
	}
	builder.append(original, offset, original.length());
	return builder.toString();
}

正しい測定は面倒なので省略しますが、適当な測定によると速くなると言ってもだいたい3倍速程度です。またreplaceAllでやるように、あらかじめPattern.compile(target.toString(), Pattern.LITERAL)しておいた場合ではreplaceの1.5倍程度でした。プロファイラで出てこない限りはライブラリが何かの都合で実装していればそっちを使う程度で、積極的には置き換えるほどではない数値ですね。チケットも上がってますし将来的にJDKの方で修正されるのならそれでよさそうです。

一方で、replaceの速度がボトルネックになった場合はreplaceを置き換えるとともに文字列パターンにあった文字列探索アルゴリズムを検討するとよいかもしれません。indexOfの実装は非常にナイーブな（シンプルな）ものです。いろいろな状況に合わせる必要性を鑑みると、indexOfやreplaceにおける文字列探索はおそらくナイーブなものにならざるを得ず、自動で最適化される日は将来的にも当面は来ないと思います。そのあたりPatternが上手くやってくれると期待したくなりますが、Patternのリテラル実装も同じぐらいナイーブです。

何事も疑ってかかると時間がいくらあっても足りませんが、思い込みで「上手くやってくれているはず」というのも危険という話でした。