Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
treex:api-implementation [2015/12/11 10:31] popel |
treex:api-implementation [2016/01/07 18:02] popel |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ==== Uložení uzlů ==== | + | ===== Uložení uzlů ===== |
[[https:// | [[https:// | ||
Line 10: | Line 10: | ||
Přijde mi tedy výhodnější ukládat rovnou referenci na daný uzel (než int, který by se musel měnit, pokud bych přidal uzly na začátek věty). | Přijde mi tedy výhodnější ukládat rovnou referenci na daný uzel (než int, který by se musel měnit, pokud bych přidal uzly na začátek věty). | ||
- | === Sdílení klíčů === | + | ==== Sdílení klíčů |
V Perlu a Pythonu jsou objekty implementovány jako hash table. Má-li třída Node atributy form, lemma,... a chceme milion uzlů, bylo by vhodné neukládat řetězce " | V Perlu a Pythonu jsou objekty implementovány jako hash table. Má-li třída Node atributy form, lemma,... a chceme milion uzlů, bylo by vhodné neukládat řetězce " | ||
- | === Sdílení hodnot === | + | ==== Sdílení hodnot |
Mnoho uzlů má stejné lemma, formu, formém, tag atd. | Mnoho uzlů má stejné lemma, formu, formém, tag atd. | ||
Line 21: | Line 21: | ||
V Perlu zabírá string (o 0-15 jednobajtových znacích) 56 bajtů, ale když dám stringy do pole, tak se to zaokrouhlí na 64 bajtů. | V Perlu zabírá string (o 0-15 jednobajtových znacích) 56 bajtů, ale když dám stringy do pole, tak se to zaokrouhlí na 64 bajtů. | ||
Int zabírá 24 bajtů a v poli 32 bajtů. | Int zabírá 24 bajtů a v poli 32 bajtů. | ||
- | Když dám stringy/ | + | Když dám stringy/ |
perl -MDevel:: | perl -MDevel:: | ||
Line 27: | Line 27: | ||
perl -MDevel:: | perl -MDevel:: | ||
- | Reference zabírá stejně jako int. | + | Reference |
+ | (V Céčku na 64bitech má typicky pointer 8 bajtů, int 4 bajty a long long int 8 bajtů, v poli to zůstává stejné, v hashi přibude režie dle míry naplnění tabulky, ale v Céčku se objekty nedávají do hashe, leda snad wild atributy.) | ||
Z hlediska rychlosti by bylo lepší ukládat přímo referenci na string (místo intu, kterým by se pak muselo indexovat pole). | Z hlediska rychlosti by bylo lepší ukládat přímo referenci na string (místo intu, kterým by se pak muselo indexovat pole). | ||
Ušetřil bych 32 bajtů na každém stringovém atributu (a pokud by měl ten string víc než 15 znaků, tak ještě víc) a navíc bych potřeboval paměť pro slovník, která je ale (díky zipfovskému rozdělení lemmat, na větších dokumentech) zanedbatelná. | Ušetřil bych 32 bajtů na každém stringovém atributu (a pokud by měl ten string víc než 15 znaků, tak ještě víc) a navíc bych potřeboval paměť pro slovník, která je ale (díky zipfovskému rozdělení lemmat, na větších dokumentech) zanedbatelná. | ||
Line 43: | Line 44: | ||
Zde je vidět, že Devel:: | Zde je vidět, že Devel:: | ||
- | ==== Benchmark Perlích accessorů ==== | ||
- | Zápis i čtení | ||
- | LV V::Magic H 64759/ | ||
- | LV V::Magic A 74649/ | ||
- | LV Sentinel H | ||
- | LV Sentinel A | ||
- | Moose 1155163/ | ||
- | object H | ||
- | object A | ||
- | LV C:: | ||
- | Mouse 3111529/ | ||
- | LV C:: | ||
- | C:: | ||
- | Moops 3688969/ | ||
- | Moo 3738065/ | ||
- | O:: | ||
- | C:: | ||
- | hash | ||
- | array 5386997/ | ||
+ | ===== Benchmark Perlích accessorů ===== | ||
+ | Nejdřív jsem porovnal různé implementace a měřil kolikrát za sekundu se provede zápis následovaný čtením (stejného) atributu. H=hash-based object. A=array-based object. LV=lvalue (viz níže). | ||
+ | LV V::Magic H 64 759/s | ||
+ | LV V::Magic A 74 649/s | ||
+ | LV Sentinel H 169 605/s | ||
+ | LV Sentinel A 170 267/s | ||
+ | Moose 1 155 163/s | ||
+ | object H 1 193 837/s | ||
+ | object A 1 233 004/s | ||
+ | LV C:: | ||
+ | Mouse 3 111 529/s | ||
+ | LV C:: | ||
+ | C:: | ||
+ | Moops 3 688 969/s | ||
+ | Moo 3 738 065/s | ||
+ | O:: | ||
+ | C:: | ||
+ | hash 4 969 215/s | ||
+ | array 5 386 997/s | ||
+ | |||
+ | Pak jsem vybral několik implementací a porovnával zápis a čtení zvlášť | ||
Zápis atributu | Zápis atributu | ||
H-lv-check-sentinel | H-lv-check-sentinel | ||
Line 82: | Line 85: | ||
A-direct | A-direct | ||
- | Čtení atributu: | + | Čtení atributu: |
- | h-get_lemma_perl | + | h-lv_check_sentinel |
- | a-get_lemma_perl | + | a-lv_check_sentinel |
- | h-lv_lemma_perl | + | |
- | a-lv_lemma_perl | + | |
--- | --- | ||
- | h-lv_lemma_xs | + | h-get_lemma_perl |
- | a-lv_lemma_xs | + | a-get_lemma_perl |
- | h-get_lemma_xs | + | h-lv_lemma_perl |
- | a-get_lemma_xs | + | a-lv_lemma_perl |
--- | --- | ||
- | h-direct | + | |
- | a-direct | + | a-lv_lemma_xs |
+ | h-get_lemma_xs | ||
+ | a-get_lemma_xs | ||
+ | --- | ||
+ | | ||
+ | a-direct | ||
+ | |||
+ | Co z toho plyne? | ||
+ | * Všechny čtení i zápisy jsou zřejmě " | ||
+ | * Pole jsou jen o málo rychlejší než hashe. Možná by se rozdíl zvětšil, kdybych měl v objektu více atributů než jeden, ale víc než 16 jich asi mít nechceme ('' | ||
+ | * Čtení je podobně rychlé jako zápis atributu obdobnou metodou. | ||
+ | * Nejrychlejší je přímý přístup do hashe/pole (tedy '' | ||
+ | * XS implementace jsou asi dvakrát rychlejší než perlové (a to v těch perlových dělám, '' | ||
+ | * Největší otázka z hlediska API je, zda povolit **lvalue accessory**, | ||
+ | * Obzvlášť užitečné je použití typu '' | ||
+ | * V Perlu to není moc zvykem (byť to byla jedna z hlavních motivací uživatelských lvalue funkcí). | ||
+ | * Dokud při zápisu nechci dělat nic jiného (kontroly, logování, | ||
+ | * Jakmile chci nějakou kontrolu v setteru (třeba že ord je kladný integer nebo deprel je jen z těch povolených), | ||
+ | * Pokud chci dělat kontroly (či logování atd.) u lvalue accessoru, musím použít (něco jako) [[https:// | ||
+ | * Hlavní problém vidím v tom, že se mi pak zpomaluje i čtení atributu, při jehož zápisu je lvalue-check. Celé to dělám proto, aby se to " | ||
+ | * Když bych tedy v Perlu používal lvalue accessory, tak jakmile se rozhodnu přidat nějakou kontrolu/ | ||
+ | * Přidáním kontroly/ | ||
+ | * To 3x zpomalení při zápisu by mi nevadilo. Ale to 5x násobné zpomalení při čtení je nepříjemné, | ||
+ | * Na druhou stranu je otázka, zda se podaří zrychlit zbytek Treexu natolik, aby se projevil rozdíl v řádu 200 **nano**sekund na čtení jednoho atributu (pesimisticky předpokládejme, | ||
+ | |||
+ | ===== Identifikátory ===== | ||
+ | |||
+ | V dosavadním Treexu byly identifikátory (uzlů) považovány za nevyhnutelnou režii a byly zpracovávány (generovány, | ||
+ | |||
+ | Nabízí se znovu zvážit: | ||
+ | - Jakých hodnot mají identifikátory nabývat | ||
+ | - Jak má být realizováno indexování identifikátorů | ||
+ | |||
+ | 1) Hodnoty identifikátorů | ||
+ | - atomické nebo strukturované (hierarchicky složením id dokumentu+bundlu+zóny+uzlu)? | ||
+ | - pokud hierarchické, | ||
+ | - v jakém scopu musí být id unikátní? | ||
+ | |||
+ | 2) Indexování identifikátorů | ||
+ | - zanášet do indexu automaticky jako nyní, nebo líně (při prvním využití), nebo ještě nějak jinak? | ||
+ | - kde držet index (asi nadále mapu id-uzel)? U dokumentu jako teď, nebo u runneru? | ||
+ | |||
+ | |||
+ | ===== Setřídění dle ord ===== | ||
+ | Jak implementovat metody '' | ||
+ | |||
+ | === PRECOMP-NAIVE === | ||
+ | Předpočítat children i descendants pro každý uzel. | ||
+ | Čtení je tedy rychlé, editace velmi pomalá, paměťová náročnost (zbytečně) velká, implementace v celku jednoduchá. | ||
+ | |||
+ | === PRECOMP-BITARRAY === | ||
+ | Taky předpočítat, | ||
+ | Čtení rychlé, editace velmi pomalá, paměťová náročnost dobrá (+16 bajtů na uzel), implementace složitější. | ||
+ | |||
+ | === SORTED-CHILDREN === | ||
+ | Děti se ukládají setříděně buď do pole, nebo do spojáku (tedy každý uzel má pointer _next_node, případně i obousměrně _prev_node). Buď se ukládají pravé a levé děti zvlášť, nebo se při vracení dětí s přepínačem '' | ||
+ | |||
+ | === SORTED-CHILDREN + ALL-NODES === | ||
+ | Navíc se udržuje (setříděné) pole všech uzlů. Hlavní motivace je, že většina bloků cyklí přes všechny uzly ('' | ||
+ | Každý uzel má atribut '' | ||
+ | Volání '' | ||
+ | |||
+ | === PROJECTIVE-OPTIMIZED === | ||
+ | V praxi jsou neprojektivity relativně řídký jev. | ||
+ | Každý uzel má v atributu _leftmost a _rightmost pointer (referenci) na nejlevější/ | ||
+ | Metoda '' | ||
+ | Problém je jen s neprojektivitami, | ||
+ | |||
+ | Vylepšení1: | ||
+ | Při zavolání z kořene stromu by se vrátil speciální iterátor, který vůbec nekontroluje seznamy neprojektivit (takže se ušetří to if, ale hlavně procházení všech seznamů). Toto vylepšení mi přijde zcela jasně přínosné. | ||
+ | |||
+ | Vylepšení2: | ||
+ | V seznamech neprojektivit budou uzly setříděné vzestupně dle hloubky. Jakmile narazím na uzel s vyšší hloubkou než uzel, který testuji (ze kterého jsou '' | ||
+ | |||
+ | Alternativa: | ||
+ | |||
+ | |||
+ | ===== Benchmark načítání CoNLL-U vPerlu ===== | ||
+ | Načítám cs-ud-train-l.conllu. | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | 10.917s nedělá se split ani rehang, všechny atributy jsou prázdný řetězec, stromy ale mají uzly | ||
+ | 13.460s korektní načtení, netestují se cykly, nevolá se set_parent (ale zopakuje se jeho kód) | ||
+ | 15.903s korektní načtení, netestují se cykly, volá se set_parent($parent, | ||
+ | 16.646s korektní načtení, testují se cykly | ||
+ | 26.666s původní implementace načítání, | ||
+ | 19.029s totéž, ale bez převěšování, | ||