V několika posledních dnech jsem se zaměřil na optimalizace phpegu. phpeg poskytuje dva typy výstupu – parser využívající rekurzivního sestupu, nebo „parsovací stroj“. Jelikož parsovací stroj byl (ano, byl, už není) pomalejší než rekurzivní sestup, zaměřil jsem se v optimalizacích hlavně na něj.
Parsovací stroj
Jak vůbec ten parsovací stroj funguje? Jedná se o registrový stroj s jednoduchou instrukční sadou (momentálně 16 instrukcí). Základem je 5 registrů – %stack, %value, %fail, %p a %s. %stack slouží k odkládání dat a návratových adres. %value obsahuje sémantickou hodnotu posledního výrazu. %fail je příznak značíčí úspěch (hodnota FALSE), nebo naopak selhání (TRUE) posledního výrazu. %s je vstupní řetězec a %p pozice v něm.
PEGy mají tři základní výrazy – nějaký znak (.), daný řetězec (např. "peg") a znak z určitého rozsahu (např. [a-zA-Z0-9_]). Každému ze základních těchto výrazů odpovídá jedna instrukce – any, literal a range.
any zkontroluje, jestli existuje nějaký znak v řetezci %s na pozici %p a uspěje-li zapíše do %fail hodnotu FALSE, %p zvýší o jedničku a %value bude obsahovat daný znak. Jestliže znak na pozici %p neexistuje, registr %fail bude obsahovat TRUE.
Podobné je to s range, akorát že ta ještě otestuje, že přečtený znak je ze zadaného rozsahu. literal ze vstupního řetězce přečte N znaků a porovná je s řetězcem délky N – jestliže se řetězce shodují nastaví %fail na FALSE, zvýší %p o N a do %value uloží přečtený řetězec.
Sekvence
Prvním ze složených výrazů je sekvence výrazů. Ta uspěje tehdy, uspějí-li všechny podvýrazy. Řekněme, že máme výraz <e1> <e2> <e3>.
START: <e1>
jumpif %fail, END
<e2>
jumpif %fail, END
<e3>
END: …
Pro ty, co o assembleru ani neslyšeli: Každý řádek je jedna instrukce. Na začátku řádku může být tzv. „label“ oddělený od instrukce dvojtečkou (např. END:). Pak následuje název instrukce a poté již seznam argumentů oddělených čárkami. Používám AT&T řazení argumentů, takže u instrukcí se zdrojovým registrem / hodnotou a cílovým registrem je vždy první zdroj, pak cíl.
(V příkladech s instrukcemi parsovacího stroje bude <e> či <eN> /kde N je nějaké číslo/ znamenat instrukce pro daný výraz z předchozího příkladu zapsaného v gramatice phpegu.)
jumpif skočí na label ve svém druhém argumentu, je-li hodnota prvního argumentu TRUE. Obecně neuspěje-li některý z podvýrazů sekvence, skočí se na první instrukci po instrukcích sekvence.
Aby byla výsledkem správná sémantická hodnota, kód by vypadal trochu složitěji. (Jsou-li všechny podvýrazy, v hantýrce phpegu, „jednoduché“, neboli je jisté, že vrátí řetězec, výsledná sémantická hodnota bude spojením řetězců vrácených z podvýrazů /to aby se pravidlo pro identifikátor dalo napsat jednoduše jako id = [a-zA-Z_] [a-zA-Z0-9_]*/).
Volba
Mějme volbu <e1> / <e2> / <e3>. Ta uspěje tehdy, uspěje-li první podvýraz, nebo druhý, nebo třetí.
START: push %p, %stack
<e1>
jumpif !%fail, END
set %stack[0], %p
<e2>
jumpif !%fail, END
set %stack[0], %p
<e3>
END: pop %stack
push uloží hodnotu svého prvního argumentu na vrchol zásobníku předaného v druhém argumentu. set uloží hodnotu prvního argumentu do registru v druhém argumentu. %stack[0] je hodnota vrcholu zásobníku (%stack[1] je první hodnota pod vrcholem, %stack[2] druhá atd.).
Nejdříve tedy na zásobník uložíme aktuální pozici v řetězci. Poté vyzkoušíme vyhodnotit první výraz. Uspěje-li (!%fail), vyhodíme uloženou pozici ze zásobníku a jde se na další výrazy. Jestliže ale podvýraz neuspěje, nastavíme pozici v textu na pozici uloženou na vrcholu zásobník (set %stack[0], %p) a vyzkoušíme další podvýraz.
Predikáty
PEGy obsahují dva predikáty – &<e> a !<e>. První, tzv. and predikát, uspěje tehdy, uspěje-li daný podvýraz. not uspěje tehdy, neuspěje-li daný podvýraz. Sémantická hodnota predikátů je NULL (alespoň v phpegu) a ať uspějí nebo ne, neposunou pozici v řetězci.
Instrukce pro and predikát:
START: push %p, %stack
<e>
pop %stack, %p
A not predikát:
START: push %p, %stack
<e>
pop %stack, %p
set !%fail, %fail
pop %stack, %p uloží hodnotu sejmutou z vrcholu zásobníku %stack do registru %p.
Je vidět, že instrukce pro oba predikáty jsou prakticky stejné. Akorát not predikát na konci obrátí pravdivostní hodnotu %fail registru.
Nepovinný výraz
<e>? znamená, že na dané pozici v textu se může daný podvýraz vyskytnou, ovšem také nemusí. V obou případech je výsledkem celého výrazu úspěch. Neuspěje-li podvýraz, pozice v textu se vrátí na původní místo a v phpegu bude mít celý výraz sémantickou hodnotu NULL.
START: push %p, %stack
<e>
pop %stack, %a
jumpif !%fail, END
set FALSE, %fail
set NULL, %value
set %a, %p
END: …
Opakování
Jsou dva druhy opakování – <e>*, kdy se podvýraz může opakovat nula a vícekrát; nebo <e>+, kdy se podvýraz na dané pozici v textu musí vyskytnou minimálně jednou. (Mohlo by vás napadnout, že <e>* je to samé jako (<e>+)?. Ale není. V případě, že <e> na momentální pozici v textu neuspěje, bude sémantická hodnota prvního prázdné pole /array()/, zatímco u druhého výrazu to bude NULL.)
Instrukce pro <e>*:
START: push %p, %stack
push [], %stack ; [] je prázdné pole
LOOP: <e>
jumpif %fail, END
arrayappend %value, %stack[0]
set %p, %stack[1]
jump START
END: pop %stack, %value
pop %stack, %p
set FALSE, %fail
arrayappend přidá hodnotu prvního argumentu na konec pole, které je v registru specifikovaném druhým argumentem. jump je nepodmíněný skok (jump LABEL je ekvivalentní zápisu jumpif TRUE, LABEL).
Pokud by byl podvýraz <e> jednoduchý, místo prázdného pole by se na zásobník uložil prázdný řetězec a místo arrayappend by tam byla instrukce append (která připojí řetězec z prvního argumentu do registru udaného druhým argumentem).
Kód pro <e>+ je trochu složitější, protože musíme ještě zjišťovat, jestli se nejedná o první iteraci, a když ano, nastavíme %fail na TRUE.
Volání jiného pravidla
Chceme-li zavolat pravidlo <r> dané gramatiky, phpeg vygeneruje následující instrukce:
START: push RET, %stack
jump r
RET: …
Neboli uloží adresu první instrukce po vygenerovaném volání na zásobník a skočí na adresu volaného pravidla. Na konec každého pravidla je přidán kód podobný následujícímu:
pop %stack, %a ; v %a je adresa RET
jump %a
Ze zásobníku je tedy sejmuta hodnota návratové adresy a na tu skočíme.
Optimalizace parsovacího stroje
phpeg zkompiluje každé pravidlo zvlášť, poté je slinkuje dohromady, takže vznikne jedna velká kupa instrukcí (kterážto představuje program parseru) a tu phpeg instrukci po instrukci převede na jejich PHP reprezentaci. Díky goto v PHP 5.3>= je to víceméně přímočará operace, až na pár drobností.
push & pop
Jak je vidět z příkladů, se zásobníkem se pracuje dost. Nejdříve byl implementován velmi přímočaře. Na začátku byla inicializována proměnná $_stack = array();, push byl array_push($_stack, $value); a pop $value = array_pop($_stack);.
Problém je, že funkce array_push() je neuvěřitelně pomalá (což bych věděl i dřív, kdybych si jen přečetl komentáře v dokumentaci). Tak pryč s array_push() a $_stack[] = $value; místo toho!
Jenže array_pop() je taktéž pomalá.
Jako nejrychlejší se ukázalo udržovat si „stack pointer“ ($_stack_sp). Takže inicializace vypadá následovně:
$_stack = array();
$_stack_sp = -1;
$_stack_sp je inicializováno na -1, protože ukazuje na vrchol zásobníku (takže přístup k vrcholu znamená pouhé $_stack[$_stack_sp], což je taky rychlé) a když tam ještě žádný prvek není… A takhle vypadají push a pop operace:
// push
$_stack[++$_stack_sp] = $value;
// pop
$value = $_stack[$_stack_sp];
unset($_stack[$_stack_sp--]);
Návrat z pravidel
PHP bohužel nepodpoje (nebo o tom nevím) něco jako:
$_stack[++$_stack_sp] = &&LABEL; // ulož adresu labelu na stack
// …
$_addr = $_stack[$_stack_sp];
unset($_stack[$_stack_sp--]);
goto $_addr;
Proto člověk musí použít nějakou návratovou „tabulku“. Nejjednodušší je:
$_stack[++$_stack_sp] = "LABEL";
// …
$_addr = $_stack[$_stack_sp];
unset($_stack[$_stack_sp--]);
goto TABLE;
// …
TABLE:
switch ($_addr) {
case "LABEL": goto LABEL;
// …
}
Leč nejrychlejší způsob to zrovínka není. Proto phpeg předvypočítá všechny adresy, na které by se pravidlo mohlo vrátit a vygeneruje následující kód:
L123: $_stack[++$_stack_sp] = 125;
L124: goto L422;
L125: // …
// …
L422: // …
// … kód pravidla …
L489: $_addr = $_stack[$_stack_sp];
unset($_stack[$_stack_sp--]);
L490: if ($_addr === 125) {
goto L125;
} else if (/* … */) {
// …
} // …
Více zábavy s parsovacím strojem
Věřím, že se ještě pár optimalizací generovaných instrukcí najde. Krom toho bych řekl, že by výkonu pomohlo kompilovat nejběžnější vzory v gramatikách do specializovaných instrukcí – např. ze sekvence [a-zA-Z] [a-zA-Z0-9_]* by se mohl vytvořit regulární výraz a ten předhodit preg_match() (což mě odrazuje, poněvadž by se phpeg stal závislý na pcre extenzi; ovšem kde byste sehnali PHP bez nainstalovaného pcre, že…). Anebo velice běžné (!<e> .)*, kde <e> může být kupř. "\n" / "\r" "\n"?, by se mohlo dost zrychlit, kdyby se s tím zacházelo specielně.
Když jsem psal shell pro pssh, naštvalo mě, že elegantní phpeg gramatiku pro shell prostě nenapíšu (tak jsem se nakonec uchýlil k ručnímu recursive descent parseru).
Napíšu-li totiž v shellu program $a, není jisté, kolik argumentů programu vlastně předávám – obsahuje-li totiž proměnná $a řetězec "foo bar", program nedostane v argv dvouprvkové pole ["program", "foo bar"], nýbrž tříprvkové ["program", "foo", "bar"]. Obnášelo by to na rozvíjení proměnných a příkazů pouštět parser několikrát. Lepší by bylo, kdybych přímo v parseru mohl obsah proměnné uložit do bufferu, který by se zpracoval dříve, než by se pokračovalo dál v původním vstupním textu.
A chci-li parsovat shell interaktivně, hodilo by se, aby parser nemusel znát celý vstupní řetězec předem. Takže v případě, že parser potřebuje další znaky (jinak by parsování skončilo chybou), parser si uloží svůj stav, vrátí běh program zpátky shellu, ten si po uživateli vyžádá další znaky, pošle je parseru a parsování může pokračovat. U rekurzivního sestupu asi nemožné implementovat (kdybychom se tedy nespokojili s tím, že parser nenavrátí běh programu o úroveň výš, ale bude volat nějaký kód, jenž vrátí další znaky), u parsovacího stroje hračka – stačí poupravit generovaný kód základních instrukcí a přidat ukládání stavu a jeho znovuobnovování.
Parsovací stroj tedy dospěl do stavu, kdy je stejně rychlý (né-li rychlejší) jako rekurzivní sestup, místo pro další optimalizace je myslím větší než u rekurzivního sestupu a poskytuje možnost dalšího rozšíření funkčnosti (ukládání a znovuobnovování stavu). Je ale jen PHP 5.3>=. Uvažuji, jestli se vyplatí generátor pro recursive descent parser stále udržovat, nebo ho odstranit ve prospěch parsovacího stroje.
