Regex speed in Java

Question

Some example wallclock times for a large number of strings:

.split("[^a-zA-Z]"); // .44 seconds
.split("[^a-zA-Z]+"); // .47 seconds
.split("\\b+"); // 2 seconds

Any explanations for the dramatic increase? I can imagine the [^a-zA-Z] pattern being done in the processor as a set of four compare operations of which all four happen only if it is a true case. What about the \b? Anybody have anything to weigh in for that?

All of those times seem about 3 orders of magnitude too great. What do your input data look like? — tchrist, Dec 01 '10 at 04:17
It looks like a few million rows of splits. This is in the right magnitude. — Jeff Ferland, Dec 08 '10 at 15:35

score 4 · Accepted Answer · edited May 23 '17 at 11:47

4

First, it makes no sense to split on one or more zero-width assertions! Java’s regex is not very clever — and I’m being charitable — about sane optimizations.

Second, never use \b in Java: it is messed up and out of sync with \w.

For a more complete explanation of this, especially how to make it work with Unicode, see this answer.

edited May 23 '17 at 11:47

Community

1
1

answered Dec 01 '10 at 04:16

tchrist

78,834
30
123
180

1

Space cadet moment; forgot about \b being zero-width. – Jeff Ferland Dec 08 '10 at 15:34

Emil Sit · Answer 2 · 2010-12-01T20:47:11.303

-1

\b is a zero-width assertion which is fundamentally different from [^A-Za-z]. Because \b is implemented as an if/then (see tchrist's comment below), it will probably be more work to check that for each letter in each string. Further, the plus is causing backtracking which would multiply that cost.

Additionally, when you split on word boundaries, you will match on more places than if you just split on [^a-zA-Z]+. This will cause the allocation of more strings, which will also take more time. To see that, try this program:

import java.lang.String;

class RegexDemo {
    private static void testSplit(String msg, String re) {
        String[] pieces = "the quick brown fox".split(re);
        System.out.println(msg);
        for (String s : pieces) {
            System.out.println(s);
        }
        System.out.println("----");
    }

    public static void main(String args[]) {
        testSplit("boundary:", "\\b+");
        testSplit("not alpha:", "[^A-Za-z]+");
    }
}

Probably unrelated, when you use String.split(), the regular expression has to be compiled for each usage. If you pre-compile the regex as a pattern, e.g.,

Pattern boundary = Pattern.compile("\\b+");

and then split using boundary.split(testString), you will save on the cost of compiling the regex for each test string. So, conceivably the compilation of "\b+" is slower than the compilation of the other patterns, which you could test by using the precompiled idiom here, though this doesn't seem likely to me as an explanation.

For some more information on regex performance, read these articles by Russ Cox http://swtch.com/~rsc/regexp/ and check out http://www.regular-expressions.info/ too.

edited Dec 01 '10 at 20:47

answered Dec 01 '10 at 04:03

Emil Sit

22,894
7
53
75

2

I don't know if Java's regular expressions are Unicode-aware (I would be surprised if they weren't), then `\b` would be a *much* more complicated check than just `[a-zA-Z]` or even `[a-zA-Z0-9_]`... – Dean Harding Dec 01 '10 at 04:12
4

This is *wrong*! `\b` **NEVER EVER** means `[^a-zA-Z0-9_]`. For one thing, that has width, and `\b` does not. What `\b` really means is `(?:(?<=\w)(?!\w)|(?<!\w)(?=\w))`. That assumes that you have a sane `\w` definition, of course. Java does not, so you have to use my rewrite function or ` (?:(?<=[\pL\pM\p{Nd}\p{Nl}\p{Pc}[\p{InEnclosedAlphanumerics}&&\p{So}]])(?![\pL\pM\p{Nd}\p{Nl}\p{Pc}[\p{InEnclosedAlphanumerics}&&\p{So}]])|(?<![\pL\pM\p{Nd}\p{Nl}\p{Pc}[\p{InEnclosedAlphanumerics}&&\p{So}]])(?=[\pL\pM\p{Nd}\p{Nl}\p{Pc}[\p{InEnclosedAlphanumerics}&&\p{So}]]))`. Scary but true. – tchrist Dec 01 '10 at 04:37
3

@Dean: Yes, `\b` is Unicode-aware (in its own, funny little way), and it *is* a much more complicated test. And it has to be applied at every single position, because pass or fail, it never consumes any characters. – Alan Moore Dec 01 '10 at 06:28
`split` only compiles the pattern once: `public String[] split(String regex, int limit) { return Pattern.compile(regex).split(this, limit); }` is from `j2se/src/share/altclasses/java/lang/String.java`. – tchrist Dec 01 '10 at 20:24
@tchrist: Thanks for the great responses; as I read the OP's question, it sounds like s/he is running some loop over a big set of strings. So for each string, calling `split`, I'd think each call will compile the same pattern. – Emil Sit Dec 01 '10 at 20:50
@tchrist: If you do multiple "split" calls, on the same regex, it would get compiled every time, wouldn't it? Or does the `Pattern` class maintain a hashtable of compiled patterns? – Platinum Azure Dec 01 '10 at 20:52
1

@Platinum: Please remember there are two split methods: [`Pattern#split`](http://download.oracle.com/javase/6/docs/api/java/util/regex/Pattern.html#split%28java.lang.CharSequence%29) and [`String#split`](http://download.oracle.com/javase/6/docs/api/java/lang/String.html#split%28java.lang.String%29). Calling `Pattern#split` repeatedly does not result in recompilation of the pattern. Calling `String#split` repeatedly does result in recompilation of the pattern. – Mike Clark Dec 01 '10 at 22:07
@Mike Clark: Look at tchrist's example: He shows the source of String#split but claims that the pattern is only compiled once. I was calling him on that claim. – Platinum Azure Dec 01 '10 at 22:44

Regex speed in Java

2 Answers2