Java Regular Expressions Performance

When I was coding an application I found that there is a performance leak while it run is running in the production environment. Profiling by Java Visual VM tool it was easy to know that a big amount of time consumption is in methods using regular expressions. After that I made a small test and I changed the application to be more efficient when correctly using regular expressions.

Background

The following explanation and performance test shows differences between java.lang.String, java.util.regex.Pattern and java.util.regex.Matcher. All of those classes contains methods to use regular expressions.

There are two ways how to match a regular expression:

  1. Use the String's method directly – boolean result = ((String)text).matches(regex);
  2. Use the Pattern to compile regex – boolean result = Pattern.compile(regex).matcher(text).matches();

If we do it just once a time, the first method is easy and good enough. However, if we use the same regular expression many times, it is too slow to compile it and it is better and faster to compile it once and use it anymore as well as String.matches(String) does itself.

The next idea is that there are some cases when the regular expression is not only the repeating text, however the text or texts are also repeating such as from a set. So the idea is to cache the whole Matcher for the unique text. It is known, we can usually use the java.util.HashMap, that is fast and that is easy to use enough.

Although the idea is easy to understand, it is not easy to know if it really works and what about limitations such as JVM garbage collector and other actors that could possibly decrease performance, even though we optimize regular expressions.

Test Case

The following test shows the differences between using Pattern and cached Matcher and compare it with String.matches(String) method. All tests are also done for different length of tested texts and for different repeats of randomizing text and pattern. The simple tested code uses JUnit4 and log4j libraries those are easy to implement, run and output results.

Three tested methods are

  1. Use the String's method directly (StringMatcher)
  2. Use a precompiled Pattern to match regex (PatternMatcher)
  3. Use cached Matcher in a HashMap, when it doesn't exist it is created from the precompiled Pattern (CachedPatternMatcher)

There are two sets of data. With or without long texts those are going to be matched (long/short). Also there are more repeats of each method as a scale with power of tens, so it is 1000 (10^3), 10'000 (10^4), 100'000 (10^5), 1'000'000 (10^6) and 10'000'000 (10^7).

The test ran on a common Intel i7 processor with Oracle Java 7 on Linux Fedora 18.

Test Results

Výsledky testu

The short and the long result has no real difference in durations. So we needn't take care about that thing if we have similar text to match.

Both of matcher methods are ever faster then StringMatcher. It is the expected result. The Precompiled Pattern is really faster then compiling regular expression string to Pattern each time it is accessed.

Graf

Even it is similar to use PatternMatcher or CachedPatternMatcher, there are some differences depending how many it is used. However in longer time it is nearly equal. Finally it looks, that using just precompiled Pattern is a good idea just with creating matcher ad hoc. See the source code of the test, that is also attached.

Conclusion

When our application uses a lot of regular expressions or it often uses, rather use java.util.Pattern instead of java.util.String's methods those also offer small regular expression functionality. Caching of Matchers and storing them into maps is obviously not effective as we can expect. In most cases using cached Matchers has negative performance impact because there is some overhead in caching algorithm. Of course use a local reference to a Matcher if we want to use it more than once in a method or in a smaller algorithm, but it is not necessary to store it anywhere.

When Matcher is matching a text. It is in nearly no difference between short and long texts, if the text is just in length around tens of letters.

Good luck with regular expressions :-)

Article has 5 comments

  • Filip Jirsák

    1
    Nechápu, k čemu je dobrá cache na Matcher? Vždyť Matcher se skládá z dvojice Pattern + vstupní text, takže Matcher už dává stále stejné výsledky. Smysl by tedy mělo cacheovat až výsledek, ne?
  • Martin Strejc

    2
    Primárně smyslem testu bylo ukázat, jaký je rozdíl v rychlosti mezi vytvářením Patternu a to, že jej již mám předkompilovaný a dále srovnat, zda mít též hotový Matcher je nějakým dalším výrazným zrychlením či nikoliv. Navíc třída Matcher má více metod, než jenom porovnání shody, tedy matches(). Ale jak říkám, smyslem bylo demonostrovat rozdíl rycholosti zpracování různých tříd, které s regulárním výrazem dále pracují. Pro rozdíl mezi přímým zpracováním regulárního výrazu a cache pro výsledek by bylo lepší nejspíše celý test koncipovat jinak. Určitě se na to rád zaměřím, even. pokud tento test někdo provedete, rozhodně dejte vědět, jak to dopadlo.
  • Ariel

    3
    1. Objekt Pattern je vlaknove bezpecny. Lze ho cachovat. Objekt Matcher NENI VLAKNOVE BEZPECNY. Tudiz ho nesmite cachovat!!!!!!
    2. Na cachovani je HashMap absolutne nevhodna. Nema maxPocetZaznamu (= potencial OutOfMemoryError) a nema maxTimeToLive, takze i stare zaznamy, ktere uz nikdo nikdy potrebovat nebude, tam hniji navzdycky. NIKDY NEPOUZIVAT!!

    Obe dve chyby jsou jako vystrizene z mych par pravidel, ktere vsem vyvojarum furt dokola omlacuju o hlavu a pokazde se najde nejaky novy expert :-)

    Nicmene diky za test, jasne to ukazuje, ze regularni vyrazy jsou napsane v Jave pomerne efektivne. (Samozrejme nemluvim o kompilaci regexu, ale o vyuzivani jiz zkompilovaneho Patternu). To je velmi prijemne cist.
  • v6ak

    4
    No, efektivně... Matchování Javových regexpů může dojít i k exponenciální složitosti. Stačí troška backtrackování a nemusíme mít ani moc složitý regulární výraz, vizte https://gist.github.com/anonymous/6018991 . Některé (nevím, jestli i Javové) "regulární" výrazy jsou snad dokonce Turing-complete.

    Toto může být i důležitější než kompilovat pattern pouze jednou.
  • Martin Strejc

    5
    Díky pánům Ariel a v6ak za komenátře. Jak jsem již v minulém komentáři uvedl, jedná se opravdu čistě o test a hlavním cílem bylo srovnat rychlost/výkon regulárních výrazů v java. Zmíněné principy jsou použil jako demonstrativní, aby bylo vidět, jak velký je rozdíl mezi variantami a/b/c. Když jsem tento test psal, tak jsem měl původně jen varianty A a B a matcher jsem sám pak zkusil jen pro zajímavost. Ostatně i u stavových objektů někdy dojde na to, že si vystačíme s opakováním jedné operace v jednom vlákně, ale to je celkem nepodstatné. Určitě pro čtenáře
    tohoto článku je to dobrá připomínka.

    Především principy cache jsem nechtěl v tomto článku v nejmenším záměrně rozebírat, protože v případě jakékoliv pochybení nebo zbytečeného zesložitění cache by mohlo snadno dojít k tomu, že výsledek testu bude méně čitelný či špatně reprezentovatelný. Algoritmy pro cache jsou jinak poměrně dost rozsáhlá kapitola, které bych se zde nechtěl věnovat a pro zmíněný příklad si opravdu vystačíme s hash mapou. Mimochodem, zrovna aplikace, ve které postup používám, má předem známý počet definovavných regulárních výrazů a ačkoliv je relativně hodně, musí
    se z důvodů rychlosti beztak vejít do paměti, protože jsou potřeba skoro pořád. Jinak při zcela obecném využití cache (a zrovna tak mapy) je vždy samozřejmě potřeba myslet na velikost dat atd., což nijak nerozporuji.

    Po přečtení komentářů však docházím k závěru, že bych měl mírně rozšířit závěr, aby z něj více plynulo, že se jedná o test, nikoliv o to, jak kód bezprostředně naimplementovat, a rovněž zmínit vláknovou bezpečnost - viz koment od Ariel. Díky za přispění.