RX: parser v Ruby

18. 2. 2007 23:42 (aktualizováno) Petr Cimprich

Tenhle článek jsem si opravdu užil, přestože se Tim Bray hned v úvodu omlouvá za jeho nezáživnost a odhaduje, že na světě může být asi tak šest lidí, které by téma mohlo zajímat. Myslím, že to trochu podcenil. Rozhodně nejsem expert na Ruby (možná leda expert naruby). Článek o efektivitě a optimalizaci parseru XML napsaného pouze v Ruby mě zaujal, protože jsem se před časem zabýval něčím podobným v Perlu. A Perl a Ruby mají, aspoň z hlediska výkonu, dost společného.

Ruby standardně obsahuje parser zvaný REXML. Komu jeho rychlost nestačí, má k dispozici ještě parsery napsané nad céčkovými knihovnami expat a libxml. Tim se pokusil napsat nový parser v Ruby, jako konečný stavový automat (DFA), v podstatě přepsáním svého dávného parseru Lark. Nový parser nazval RX. Dílo se podařilo ale výsledek byl asi desetkrát pomalejší než REXML. Po několika kolech různých optimalizací se podařilo RX urychlit, ale do výkonu REXML mu stále dost chybí.

Zajímavé je, že kromě běžných optimalizací I/O operací pomohlo například rozsekání vstupu regulárními výrazy (místo zpracování po znacích) a odstranění velkého (70 větví) příkazu case. Ukazuje se, že v dynamických jazycích se vyplatí co nejvíc využívat komplexních funkcí jazyka a nesnažit se o vlastní nízkoúrovňové zpracování.

Tim se nevzdal a dál zkoušel a možná ještě zkouší všechno možné, ale v pokračování článku už připustil, že jedinou cestou k rychlému parsování přece jen bude použití expatu nebo libxml, kterému se chtěl na začátku vyhnout. Naprosto stejná je situace v Perlu – pure-Perl parser představuje základní volbu – kdo chce zrychlit, potřebuje expat/libxml.

Další pokračování popisuje pokusy s YARV, virtualním strojem pro Ruby, který by teoreticky mohl mít potenciál oproti interpreteru podstatně urychlit provádění velkého množství jednoduchých operací. K urychlení došlo, ale odstup mezi REXML a RX se skoro nezměnil. RX pravděpodobně doplácí na volbu použít elegantní, ale pro dynamické jazyky málo efektivní algoritmus DFA.

Sdílet