Výkon regulárních výrazů v Java

Když jsem programoval jednu aplikaci narazil jsem na zvláštní chování na produkčním prostředí. Pomocí profilace nástrojem Java Visual VM bylo jednoduché během chvíle dohledat, že velký čas aplikace tráví zpracováním regulárních výrazů. Pak stačilo pár malých změn a rázem aplikace začala regulární výrazy zpracovávat mnohem efektivněji.

Pozadí

Následující vysvětlení a výkonový test ukazují rozdíly mezi java.lang.String, java.util.regex.Pattern a java.util.regex.Matcher. Všechny tyto třídy obsahují metody pro práci s regulárnímy výrazy.

Existují dvě základní možnosti, jak porovnávat regulární výraz:

  1. Přímé užití metody třídy String – boolean result = ((String)text).matches(regex);
  2. Kompilací výrazu třídou Pattern – boolean result = Pattern.compile(regex).matcher(text).matches();

Pokud regulárním výrazem porovnáváme čas od času, je první metoda jednoduchá a plně dostačující. Avšak pokud mnohokrát užíváme stejný regulární výraz, je příliš pomalé je pokaždé kompilovat, proto je lepší kompilaci provést předem, raději než se po každé znovu provádí v metodě String.matches(String).

Dalším myšlenka spočívá v tom, že nejen regulární výraz se často opakuje, ale v řadě případů se opakuje i porovnávaný text, zejména pokud se vybírá z konkrétní množiny. Jednoduchý nápad je připravit cache na objekty Matcher vytvořené k porovnávanému řetězci. Je je jasné, že vhodným typem pro cache je mapa java.util.HashMap, která je dostatečně rychlá a jednoduchá na implementaci.

Ačkoliv nápad je jednoduchý, není opravdu jasné, zda to opravdu funguje, zejména díky limitacím jako je garbage collector a ostatní faktory, které mohou snížit výkon, ačkoliv optimalizujeme.

Testovací scénář

Následující test ukazuje rozdíly mezi užitím Pattern a cache pro Matcher ve srovnání s metodou String.matches(String). Všechny testy probíhaly pro různé délky porovnávaných textů a různé náhodně vybírané regulární výrazy. Jednoduchý testovací kód využívá knihoven JUnit4 a log4j, které jsou snadno pomohou test naimplementovat a zobrazit výstupy.

Testované metody:

  1. Užití metod třídy String (StringMatcher)
  2. Užití předkompilovaných objektů třídy Pattern z regulárního výrazu (PatternMatcher)
  3. Užití cache objektů třídy Matcher v mapě HashMap, pokud cache neexistuje, je vytvořena z předkompilovaného objektu třídy Pattern (CachedPatternMatcher)

Vždy jsou k dispozici dva vzorky dat, dlouhý a krátký test, tedy test obsahující pouze krátké nebo krátké a dlouhé porovnávané řetězce (long/short). Dále jsou ve vzorcích různé délky opakování testu, které jsou mocniny deseti, tedy 1000 (10^3), 10'000 (10^4), 100'000 (10^5), 1'000'000 (10^6) a 10'000'000 (10^7).

Test probíhal na notebooku s procesorem řady Intel i7, v prostředí Oracle Java 7 nad systémem Linux Fedora 18.

Výsledky testu

Výsledky testu

Krátků a dlouhý test nevykazuje žádné zvláštní rozdíly v délce vykonávání testu. Tudíž zjevně nepotřebujeme řešit, jak dlouhý porovnávaný text je.

Obě metody metody porovnávání jsou vždy rychlejší než StringMatcher, což je předpokládaný výsledek. Předkompilovaný Pattern je vždy zákonitě rychlejší, protože jej není potřeba znovu kompilovat pokaždé, když chceme porovnávat.

Graf

Ačkoliv rychlost metod PatternMatcher a CachedPatternMatcher je velmi podobná, jsou zde drobné rozdíly v případech, jak často porovnáváme, ačkoliv s rostoucím počtem porovnávání se výsledky srovnávají. Přesto však lze říci, že užití předkompilovaného objektu třídy Pattern je vždy jednoznačně lepší. Je vhodné si prostudovat zdrojový kód tohoto testu k pochopení rozdílu.

Závěr

Pokud aplikace často užívá regulární výrazy, je lepší používat java.util.Pattern namísto metod třídy java.util.String's, které také obsahují funkcionalitu pro práci s regulárními výrazy. Cache pro Matcher a ukládání do map zjevně není zase až tak moc efektivní, jak by se na první pohled mohlo zdát. V řadě případů se může stát, že cache Matcherů má negativní dopad na výkon díky času potřebnému pro zpracování algoritmu pro cache. Pochopitelně však lokální reference na Matcher je odlišný případ a standardně se využívá pokud metody Matcheru potřebujeme opakovaně za sebou volat v rámci metody nebo kratšího algoritmu.

Když Matcherem porovnáváme text, není skoro rozdíl, zda je tento text krátký či dlouhý, pokud se bavíme o textu přibližně v řádech desítek znaků.

Hodně štěstí s optimalizováním regulárních výrazů :-)

Článek obsahuje 5 komentářů

  • 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í.