Both sides previous revision
Previous revision
Next revision
|
Previous revision
Next revision
Both sides next revision
|
treex:api-implementation [2015/12/14 03:43] popel |
treex:api-implementation [2016/01/08 14:48] popel |
==== Uložení uzlů ==== | ===== Uložení uzlů ===== |
| |
[[https://github.com/ufal/parsito/tree/master/src/tree|Parsito]] používá ''vector<node> nodes;'' a pak ''nodes.emplace_back(nodes.size(), form);''. | [[https://github.com/ufal/parsito/tree/master/src/tree|Parsito]] používá ''vector<node> nodes;'' a pak ''nodes.emplace_back(nodes.size(), form);''. |
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 "form", "lemma",... do každé instance. V Perlu jsou naštěstí klíče všech hashů sdílené (stále je zde ale nějaká režie za hash, která by se odstranila použitím array-based objektů a vytvořením hashe pouze pro "wild" atributy). V Pythonu je potřeba použít [[http://tech.oyster.com/save-ram-with-python-slots/|__slots__]] nebo [[https://www.python.org/dev/peps/pep-0412/|Python > 3.3]] nebo dědit od [[https://github.com/nucleic/atom|Atom]] nebo namedtuple. | 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 "form", "lemma",... do každé instance. V Perlu jsou naštěstí klíče všech hashů sdílené (stále je zde ale nějaká režie za hash, která by se odstranila použitím array-based objektů a vytvořením hashe pouze pro "wild" atributy). V Pythonu je potřeba použít [[http://tech.oyster.com/save-ram-with-python-slots/|__slots__]] nebo [[https://www.python.org/dev/peps/pep-0412/|Python > 3.3]] nebo dědit od [[https://github.com/nucleic/atom|Atom]] nebo namedtuple. |
| |
=== 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. |
| |
| |
==== Benchmark Perlích accessorů ==== | ===== 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). | 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 H 64 759/s |
* 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, že všechny atributy mají kontrolovaný/logovaný zápis, což snad nebude pravda). Odhaduji, že na parsing (plus tagging, nebo načtení z CoNLL-U) jedné věty (20 slov) potřebuji číst tak 1000 krát číst a 100 krát zapsat nějaký atribut, tedy s lvalue ztratím 200 **mikro**sekund. Přitom samotný parsing trvá aspoň několik **mili**sekund. | * 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, že všechny atributy mají kontrolovaný/logovaný zápis, což snad nebude pravda). Odhaduji, že na parsing (plus tagging, nebo načtení z CoNLL-U) jedné věty (20 slov) potřebuji číst tak 1000 krát číst a 100 krát zapsat nějaký atribut, tedy s lvalue ztratím 200 **mikro**sekund. Přitom samotný parsing trvá aspoň několik **mili**sekund. |
| |
==== Identifikátory ==== | ===== Identifikátory ===== |
| |
V dosavadním Treexu byly identifikátory (uzlů) považovány za nevyhnutelnou režii a byly zpracovávány (generovány, indexovány) automaticky. Je otázka, jestli je to opravdu nutné za všech okolností, popř. jestli by to nešlo nějak zjednodušit, když víme, že valná část bloků identifikátory uzlů k ničemu nepotřebuje, navíc drtivá většina referencí je uzavřených uvnitř bundlu. Pokud se podaří sloučit a-stromy a t-stromy, velká část referencí odpadne, zbývající případy budou souviset asi hlavně s alignmentem a koreferencí. | V dosavadním Treexu byly identifikátory (uzlů) považovány za nevyhnutelnou režii a byly zpracovávány (generovány, indexovány) automaticky. Je otázka, jestli je to opravdu nutné za všech okolností, popř. jestli by to nešlo nějak zjednodušit, když víme, že valná část bloků identifikátory uzlů k ničemu nepotřebuje, navíc drtivá většina referencí je uzavřených uvnitř bundlu. Pokud se podaří sloučit a-stromy a t-stromy, velká část referencí odpadne, zbývající případy budou souviset asi hlavně s alignmentem a koreferencí. |
| |
| |
==== Setřídění dle ord ==== | ===== Setřídění dle ord ===== |
Jak implementovat metody ''children'' a ''descendants'' (a ''siblings'', ale to je skoro jako ''node->parent->get_children()'' až na vynechání ''node'' a jiné chápání přepínačů ''add_self'', ''preceding_only'' atd.) a tedy celou datovou strukturu stromu, aby metody (rychle) vracely uzly v pořadí podle slovosledu (i u neprojektivních stromů) a přitom šlo stromy editovat, tedy přidávat a mazat uzly (i z prostředka věty), převěšovat, měnit slovosled. | Jak implementovat metody ''children'' a ''descendants'' (a ''siblings'', ale to je skoro jako ''node->parent->get_children()'' až na vynechání ''node'' a jiné chápání přepínačů ''add_self'', ''preceding_only'' atd.) a tedy celou datovou strukturu stromu, aby metody (rychle) vracely uzly v pořadí podle slovosledu (i u neprojektivních stromů) a přitom šlo stromy editovat, tedy přidávat a mazat uzly (i z prostředka věty), převěšovat, měnit slovosled. |
| |
Každý uzel má v atributu _leftmost a _rightmost pointer (referenci) na nejlevější/nejpravější uzel svého podstromu a v atributu _next pointer na následující uzel dle slovosledu (čili spoják). | Každý uzel má v atributu _leftmost a _rightmost pointer (referenci) na nejlevější/nejpravější uzel svého podstromu a v atributu _next pointer na následující uzel dle slovosledu (čili spoják). |
Metoda ''descendants'' tedy začne nejlevějším a iteruje až do nejpravějšího (a vynechá uzel, ze kterého to volám, pokud není ''add_self''). | Metoda ''descendants'' tedy začne nejlevějším a iteruje až do nejpravějšího (a vynechá uzel, ze kterého to volám, pokud není ''add_self''). |
Problém je jen s neprojektivitami, takovéto uzly musím přeskočit. Každý uzel má tedy seznam (spoják) uzlů, v jejichž spanu (leftmost..rightmost) se slovosledně nachází a přitom není jejich potomkem. Většina uzlů je projektivních a má tedy tento seznam prázdný, takže při iteraci mám jen jeden if navíc. | Problém je jen s neprojektivitami, takovéto uzly musím přeskočit. Každý uzel má tedy seznam (spoják) uzlů, v jejichž spanu (leftmost..rightmost) se slovosledně nachází a přitom není jejich potomkem. Většina uzlů je projektivních a má tedy tento seznam prázdný, takže při iteraci mám jen jeden if navíc. Zatím se mi tato implementace líbí nejvíc. |
Zatím se mi tato implementace líbí nejvíc. | |
| 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 ''descendants'' zavolané), tak skončím a neprocházím zbytek seznamu. Zde si vůbec nejsem jist, zda to má cenu, protože sice ušetřím procházení části seznamu u některých uzlů, jenže zase přibude testování hloubky (kterou bych musel mít v tom seznamu asi předpočítanou, a tedy ji aktualizovat, když se změní). |
| |
| Alternativa: atribut _leftmost (a obdobně _rightmost) by se vyplňoval pouze tehdy, pokud by se sledováním nejlevějšího dítěte nedalo dostat do nejlevějšího potomka. Tedy v projektivních stromech by se ty atributy nemusely vyplňovat vůbec (vůbec by nezabíraly místo v hash-based objektech). Editace by pak mohly být o něco rychlejší, pokud detekuji, že projektivní strom měním na projektivní. Čtení ale bude pomalejší, protože budu muset iterovat do těch nejlevějších dětí (a ještě navíc testovat, zda není v uzlech vyplněn _leftmost). |
| |
| |
| ===== Benchmark načítání CoNLL-U v Perlu ===== |
| Načítám cs-ud-train-l.conllu (68 MB, 41k sentences, 0.8 MWords) . |
| |
| 0.479s while (<$fh>) {chomp;} |
| 0.844s + test $line eq '' or $line =~ /^#/ |
| 1.409s + split /t/, ale hodnoty se zahodí a neukládají do proměnných |
| 5.722s totéž, ale hodnoty atributů se uloží do proměnných (které se hned zahodí) |
| 7.724s + uzly se vytvoří jako undef, uloží do pole @nodes, které se zahodí, vytváří se bundly |
| 3.500s vytvoření pole s 0.8M uzlů se všemi atributy (žádné čtení souboru, všechny uzly stejné) |
| 7.887s totéž, ale atributy se vytvářejí splitem jedné řádky |
| 12.552s vytváří se uzly ze souboru, ale nedávají se do stromů, jen do pole, toto by mělo odpovídat 5.722s+3.500s |
| 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, {cycles=>'no-check'}) |
| 16.646s korektní načtení, testují se cykly, volá se set_parent($parent) |
| 26.666s původní implementace načítání, kde se uzly vytvářejí pomocí $root->create_child a převěšují se pak z kořene na skutečného rodiče a děti jsou pole |
| 19.029s totéž, ale bez převěšování, tedy vše visí na kořenu |
| |
| |
| * Původní implementace byla velmi neefektivní, protože se při převěšování z kořene musely uzly odebrat z pole dětí kořene, čili se muselo to pole překopírovat a zmenšit o jeden prvek a složitost byla kvadratická. Převěšení trvalo 7s. Kdyby byly děti implementované spojákem místo pole (to mám stále v plánu), tak to bude rychlejší, ale stejně je zbytečné při načítání CoNLL-U uzly dávat do spojáků dětí kořene, ze kterého vím, že je budu za chvíli odebírat. |
| * Ušetřil jsem 10s, tedy víc než 7s. Volám přímo ''UD::Node->new(...)'' místo ''$root->create_child(...)''. |
| * Ještě víc by šlo ušetřit vypuštěním testování cyklů v CoNLL-U závislostech (1s) a optimalizací kódu set_parent bez volání této metody (další 2s). |
| * Nyní se nejvíc času stráví samotným vytvářením uzlů (10.917s-0.844s). To musím ještě prozkoumat. |
| |
| ===== Benchmark konstruktorů v Perlu ===== |
| Kolik objektů (uzlů s 9 stringovými atributy) se vytvoří za 1 sekundu: |
| MooseMut 4509 Moose bez __PACKAGE__->meta->make_immutable |
| Moose 65941 |
| Moo 78156 |
| ManualA 99508 Manual array-based object, konstruktor vytvoří hash, aby zjistil, které atributy byly zadány |
| ManualH 191911 Manual hash-based object |
| XSAccHp 197371 Class::XSAccessor ale sub new {my $c=shift; bless {@_}, $c;} |
| XSAccAs 224108 Class::XSAccessor::Array, new bez parametrů, třeba volat settery |
| XSAccH 235633 Class::XSAccessor { constructor => 'new'} |
| --- následující implementace mají konstruktory, které berou jen hodnoty atributů, nikoli jména, tedy musejí být zadané ve správném pořadí |
| XSAccAf 324620 Class::XSAccessor::Array, sub fastnew {my $c=shift; bless [@_], $c;} |
| ManualAf 333188 Manual array-based object, sub fastnew {my $c=shift; bless [@_], $c;} |
| |