36

I have an old piece of code that performs find and replace of tokens within a string.

It receives a map of from and to pairs, iterates over them and for each of those pairs, iterates over the target string, looks for the from using indexOf(), and replaces it with the value of to. It does all the work on a StringBuffer and eventually returns a String.

I replaced that code with this line: replaceAll("[,. ]*", "");
And I ran some comparative performance tests.
When comparing for 1,000,000 iterations, I got this:

Old Code: 1287ms
New Code: 4605ms

3 times longer!

I then tried replacing it with 3 calls to replace:
replace(",", "");
replace(".", "");
replace(" ", "");

This resulted with the following results:

Old Code: 1295
New Code: 3524

2 times longer!

Any idea why replace and replaceAll are so inefficient? Can I do something to make it faster?


Edit: Thanks for all the answers - the main problem was indeed that [,. ]* did not do what I wanted it to do. Changing it to be [,. ]+ almost equaled the performance of the non-Regex based solution. Using a pre-compiled regex helped, but was marginal. (It is a solution very applicable for my problem.

Test code:
Replace string with Regex: [,. ]*
Replace string with Regex: [,. ]+
Replace string with Regex: [,. ]+ and Pre-Compiled Pattern

1

5 Answers 5

69

While using regular expressions imparts some performance impact, it should not be as terrible.

Note that using String.replaceAll() will compile the regular expression each time you call it.

You can avoid that by explicitly using a Pattern object:

Pattern p = Pattern.compile("[,. ]+");

// repeat only the following part:
String output = p.matcher(input).replaceAll("");

Note also that using + instead of * avoids replacing empty strings and therefore might also speed up the process.

9
  • @Lukas: it doesn't change what is done (in this case, where the replacement is the empty string). It might change the performance characteristics, but I don't know if leaving out + is faster or slower. Jun 7, 2011 at 8:27
  • 4
    @Joachim, interestingly, with a simple benchmark test on your solution, []+ seems the fastest (1x), [] in the middle (1.5x) , and []* the slowest (2x).
    – Lukas Eder
    Jun 7, 2011 at 8:33
  • This answer assumes that the map he receives is reused over and over again.
    – aioobe
    Jun 7, 2011 at 8:34
  • @Joachim, []* matches the empty String "". So, for each character, a match is found of "" and replaced by "". This causes it to be slower. You can test it by doing ....replaceAll("$$$$") and watching the output.
    – SJuan76
    Jun 7, 2011 at 10:21
  • @SJuan76: I'm well aware of that (I already explained that in my answer). The only thing I didn't know was if replaceAll("[,. ]+", "") would be slower or faster than replaceAll("[,. ]", ""). Jun 7, 2011 at 10:41
10

replace and replaceAll uses regex internally which in most cases gives a serious performance impact compared to e.g., StringUtils.replace(..).

String.replaceAll():

public String replaceAll(String regex, String replacement) {
        return Pattern.compile(regex).matcher(this ).replaceAll(
             replacement);
}

String.replace() uses Pattern.compile underneath.

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

Also see Replace all occurrences of substring in a string - which is more efficient in Java?

7
  • 4
    replace() doesn't use regex. Jun 7, 2011 at 8:20
  • 9
    @Adeel, String.replace(char, char) doesn't. String.replace(CharSequence, CharSequence) does.
    – Lukas Eder
    Jun 7, 2011 at 8:25
  • 1
    @Lukas: None of those does. BTW, replace(char, char) is out of question, because it can't use regex, whatsoever, and the OP never used it. Jun 7, 2011 at 8:29
  • 3
    @Lukas String.replace(CharSequence, CharSequence) uses a compiled pattern, true, but not compiled against a regular expression. Jun 7, 2011 at 8:34
  • 2
    @Johan yep, it's also the first three words of a children's song. (Which is also irrelevant) Jun 7, 2011 at 8:47
4

As I have put in a comment [,. ]* matches the empty String "". So, every "space" between characters matches the pattern. It is only noted in performance because you are replacing a lot of "" by "".

Try doing this:

Pattern p = Pattern.compile("[,. ]*");
System.out.println(p.matcher("Hello World").replaceAll("$$$");

It returns:

H$$$e$$$l$$$o$$$$$$W$$$o$$$r$$$l$$$d$$$!$$$

No wonder it is slower that doing it "by hand"! You should try with [,. ]+

1
  • Thanks - that explains why it worked so hard to perform the replacement
    – RonK
    Jun 8, 2011 at 19:26
1

When it comes to replaceAll("[,. ]*", "") it's not that big of a surprise since it relies on regular expressions. The regex engine creates an automaton which it runs over the input. Some overhead is expected.

The second approach (replace(",", "")...) also uses regular expressions internally. Here the given pattern is however compiled using Pattern.LITERAL so the regular expression overhead should be negligable.) In this case it is probably due to the fact that Strings are immutable (however small change you do, you will create a new string) and thus not as efficient as StringBuffers which manipulate the string in-place.

4
  • 1
    @aiiobe: String.replace(CharSequence, CharSequence) uses regular expressions internally...
    – Lukas Eder
    Jun 7, 2011 at 8:24
  • Yes, but with Pattern.LITERAL which in effect turns off all regexp overhead.
    – aioobe
    Jun 7, 2011 at 8:29
  • But that precisely means it doesn't, you can only pass a regex to it, but it will not work as expected, I suppose. Jun 7, 2011 at 8:33
  • 1
    Still, the compilation for a LITERAL pattern shouldn't be super complicated, eh? ;-)
    – aioobe
    Jun 7, 2011 at 8:36
0

This is a very old post, but for the record, since Java 9, the performance characteristics of String.replace(String,String) has changed, it now does not use Pattern under the hood

https://medium.com/javarevisited/micro-optimizations-in-java-string-replaceall-c6d0edf2ef6

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.