0xDEADBEEF

RSS odkazy english edition
««« »»»

Java, Scala, D, Javascript, PHP a regulární výrazy #8

9. 10. 2020

Už tu párkrát padlo, že regexy v Javě nemusí být příliš rychlé. Jak na tom ale jsou ve srovnání s jinými jazyky? Například s D, který ve standardní knihovně nabízí hned dvě varianty regexů: Jednak ty obyčejné, které jsou za běhu přeloženy do IR (v případě D jde o bytekód namísto AST) a pak compile-time odrůdu regexů, které kompilátor přeloží přímo do x86 binárky. To na první pohled vypadá jako to nejlepší možné řešení.

Vzal jsem náhodný Apache log dlouhý přibližně 220k řádků a změřil rychlost parsování standardními regexy v Javě (java.util.regex), Java knihovnou jregex, regexy v D, PHP a Javascriptu/Node a pak mini-nástrojem Slurp, o kterém bude řeč později.

Regex vypadal takhle:

^(\S++) (\S++) (\S++) \[([^\]]++)\] "((?:\\"|[^"])++)" (\d++) (\d++|-) "((?:\\"|[^"])*+)" "((?:\\"|[^"])*+)".*+$

A vyšla takováhle čísla:

java.util.regex879 ms
jregex1597 ms
D regex2100 ms
D ctRegex1625 ms
node v8.10.0 / v8200 ms
php 7.3 +173 ms
php 7.3 ++162 ms
Slurp138 ms
Slurp cheat62 ms

jregex je nějaká náhodná Java implementace regexů, která (stejně jako D) neumí posesivní regexy. Přihodil jsem ji do testu pro případ, kdyby něco specializovaného mimo JDK bylo rychlejší. Nebylo. Jak je vidět, java.util.regex není v porovnání s běžnými alternativami úplně pomalá. jregex je 2x pomalejší než standard z knihovny.

Compile-time regex v D (kompilováno s GDC 10.2) je skutečně o něco málo rychlejší než jeho run-time varianta, ale oba jsou v tomto případ pomalejší než Javovská verze. Člověk by čekal opak.

Bylo by zajímavé vystopovat důvod, proč je JVM verze 2x rychlejší, jakou roli hraje dobrý optimalizovaný kód a jak velkou roli hraje JIT. To nechám jako cvičení pro čtenáře. Nastartujte JITWatch a podělte se o zjištění v komentářích.

Kapitolu sama pro sebe tvoří regex enginy ve v8 a PHP. Může se to zdát překvapivé, ale nejrychlejšími regexy disponuje PHP, který jinak není známý svou rychlostí. PHP pod kapotou používá knihovnu PCRE (Perl Compatible Regular Expressions) vybavenou JITem a je to znát. Parsování je velice rychlé. Řádek + místo possesive regexů (ty nemusí dělat backtracking a proto by měly být efektivnější) používá normální greedy variantu a je o něco málo pomalejší.

Poslední dva řádky ukazují jednoduchou třídu Slurp, která vznikla pro asciiblog. Ve své podstatě jde o dva ukazatele a smyčku. Nesnaží se ani vzdáleně přiblížit síle a kryptické expresivitě regexů, ale jen o něco zjednodušuje zápis hledání v possesive stylu, které posouvá ukazatele pouze vpřed a logiku musí obstarat uživatel sám. Na druhou stranu jde o velice rychlou věc, nedochází k vytvoření AST, která se pak interpretuje, volají se maličké nevirtuální metody, jež může JIT snadno inlinovat a nedochází k žádným nebo jen minimu alokací.

Výsledky neberte jako definitivní evangelium o tom, co je rychlejší a co pomalejší, ale jako demonstraci rozsahu hodnot, na které můžeme narazit. Jako vždy nevěřte číslům na internetu a když na tom záleží, proveďte vlastní měření na reprezentativních datech.


+1: Někdo mě upozornil na knihovnu C++ compile-time regexů, ale ta je pomalá a při kompilaci výše uvedeného regexu kompilátor sežral všechnu RAM s takovou vervou, že se počítač zasekl a pomohl až restart. Takže za mě špatenka.

píše k47 (@kaja47, k47)