Regex speed in Java

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 tha开发者_开发知识库t?

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.

\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.