Differences

This shows you the differences between two versions of the page.

--- treex:api-implementation [2015/12/11 11:09]
popel
+++ treex:api-implementation [2016/01/08 23:17] (current)
popel
@@ Line 1: / Line 1: @@
-==== 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);''.
@@ 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).
-=== 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.
-=== Sdílení hodnot ===
+==== Sdílení hodnot ====
 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ů.
 Int zabírá 24 bajtů a v poli 32 bajtů.
-Když dám stringy/inty do hashe (místo do pole), tak je to taky 64/32 bajtů, jen je tam samozřejmě ještě nějaká režie na ten hash. Viz
+Když dám stringy/inty do hashe (místo do pole), tak je to taky 64/32 bajtů, jen je tam samozřejmě ještě nějaká režie na ten hash, takže to vychází 128/96 bajtů. Viz
   perl -MDevel::Size=:all -E 'my $s="s"; say total_size {map {$_=>$s} 1..1_000_000}' # string 128M
@@ Line 27: / Line 27: @@
   perl -MDevel::Size=:all -E 'my $s="s"; say total_size {map {$_=>\$s} 1..1_000_000}'# ref     96M
-Reference v Perlu zabírá stejně jako int, a to těch 24 až 32 bajtů (v céčku na 64bitech má typicky pointer 8 bajtů, int 4 bajty a long long int 8 bajtů, což je vše samozřejmě mnohem míň než v Perlu).
+Reference v Perlu zabírá stejně jako int (a to těch 24 bajtů samostatně, 32 bajtů v poli, 96 bajtů v hashi).
+(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).
 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::Size::total_size hlásí 96MB, ale ps hlásí 292MB.
-==== Benchmark Perlích accessorů ====
-  Zápis i čtení
-  LV V::Magic H        64759/s
-  LV V::Magic A        74649/s
-  LV Sentinel H       169605/s
-  LV Sentinel A       170267/s
-  Moose              1155163/s
-  object H           1193837/s
-  object A           1233004/s
-  LV C::XSAccessor H 2880212/s
-  Mouse              3111529/s
-  LV C::XSAccessor A 3111529/s
-  C::XSAccessor H    3558344/s
-  Moops              3688969/s
-  Moo                3738065/s
-  O::Tiny::RW::XS    3764547/s
-  C::XSAccessor A    4228110/s
-  hash               4969215/s
-  array              5386997/s
+===== 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::XSAccessor H 2 880 212/s
+  Mouse              3 111 529/s
+  LV C::XSAccessor A 3 111 529/s
+  C::XSAccessor H    3 558 344/s
+  Moops              3 688 969/s
+  Moo                3 738 065/s
+  O::Tiny::RW::XS    3 764 547/s
+  C::XSAccessor A    4 228 110/s
+  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
   H-lv-check-sentinel    714 566/s
@@ Line 82: / Line 85: @@
   A-direct            10 180 350/s
   Čtení atributu:
-  h-get_lemma_perl  2 453 219/s
+  h-lv_check_sentinel  1 147 836/s
-  a-get_lemma_perl  2 572 440/s
+  a-lv_check_sentinel  1 147 836/s
-  h-lv_lemma_perl   3 206 187/s
-  a-lv_lemma_perl   3 406 574/s
   ---
-  h-lv_lemma_xs     5 825 422/s
+  h-get_lemma_perl     2 453 219/s
-  a-lv_lemma_xs     6 412 374/s
+  a-get_lemma_perl     2 572 440/s
-  h-get_lemma_xs    6 859 843/s
+  h-lv_lemma_perl      3 206 187/s
-  a-get_lemma_xs    7 489 828/s
+  a-lv_lemma_perl      3 406 574/s
   ---
-  h-direct         10 144 688/s
+  h-lv_lemma_xs        5 825 422/s
-  a-direct         12 112 263/s
+  a-lv_lemma_xs        6 412 374/s
+  h-get_lemma_xs       6 859 843/s
+  a-get_lemma_xs       7 489 828/s
+  ---
+  h-direct            10 144 688/s
+  a-direct            12 112 263/s
+Co z toho plyne?
+  * Všechny čtení i zápisy jsou zřejmě "dostatečně rychlé na Perl" (krom lvalue přes ''Variable::Magic'', ale to jsem hned po prvním experimentu zavrhl ve prospěch [[https://metacpan.org/pod/Sentinel|Sentinel]]).
+  * 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 (''iset'' bude objekt držící všechny features).
+  * Čtení je podobně rychlé jako zápis atributu obdobnou metodou.
+  * Nejrychlejší je přímý přístup do hashe/pole (tedy ''$node->{lemma}="ahoj"'' a ''$node->[0]="ahoj"''), ale to lze používat jen uvnitř implementace, zvnějšku chceme samozřejmě encapsulation.
+  * XS implementace jsou asi dvakrát rychlejší než perlové (a to v těch perlových dělám, ''$_[0]->{lemma} = $_[1];'' -- kdybych udělal ''my ($self, $new_lemma)=@_;'', tak to bude ještě pomalejší).
+  * Největší otázka z hlediska API je, zda povolit **lvalue accessory**, tedy abych mohl jako v Pythonu psát ''$node->lemma = 'ahoj';'' místo ''$node->set_lemma('ahoj');''.
+    * Obzvlášť užitečné je použití typu ''$node->lemma =~ s/a/b/;''.
+    * 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í,...) než uložit tu hodnotu, tak jsou lvalue accessory dost rychlé (pro zápis dokonce se zdá rychlejší), navíc mohou být v XS.
+    * Jakmile chci nějakou kontrolu v setteru (třeba že ord je kladný integer nebo deprel je jen z těch povolených), tak nemůžu použít XS implementaci (ledaže bych si ji napsal sám v Céčku). I oproti pure-perl řešení je to samozřejmě pomalejší, právě o čas strávený tou kontrolou (v *check* metodách výše jsem testoval jen, že to není undef).
+    * Pokud chci dělat kontroly (či logování atd.) u lvalue accessoru, musím použít (něco jako) [[https://metacpan.org/pod/Sentinel|Sentinel]]. To už je třikrát pomalejší než (pure-perl) řešení přes setter.
+    * 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 "hezky" používalo, takže chci mít jednu metodu "lemma", která bude fungovat jako property (půjde z ní číst i do ní zapisovat). Kdybych měl dvě metody, tak to ztrácí smysl. Jenže v Perlu je Sentinel lvalue udělané tak, že se vrátí skalár, který má v sobě "magic", takže když se do něj **pak** přiřadí nějaká hodnota, tak se ve skutečnosti zavolá nějaká metoda (která provede tu kontrolu, logování...). A Perl neví, když se volá "lemma", zda se výsledek bude jen číst, nebo do něj i zapisovat, takže to neumí optimalizovat. Zde je Python jednoznačně lepší, protože properties jsou součástí návrhu objektů (byť jsem je zatím nebenchmarkoval).
+    * Když bych tedy v Perlu používal lvalue accessory, tak jakmile se rozhodnu přidat nějakou kontrolu/logování při zápisu, tak se mi **čtení zpomalí pětinásobně** (oproti XS implementaci). Kdybych nepoužíval lvalue, tak čtení zůstane rychlé, protože getter je jiná metoda než setter (předpokládám, tedy že názvy setterů mají dle PBP prefix "set_").
+    * Přidáním kontroly/logování se lvalue zápis zpomalí sedminásobně, zatímco bez lvalue (tj. setter a getter) se zápis zpomalí jen dvojnásobně. Tedy použitím lvalue se zápis s kontrolou/logováním **zpomalí trojnásobně**. Samozřejmě pokud by ta kontrola/logování dělala něco složitějšího než kontrolu undefu, tak se asi rozdíl mezi lvalue accessorem a setterem ztratí.
+    * To 3x zpomalení při zápisu by mi nevadilo. Ale to 5x násobné zpomalení při čtení je nepříjemné, protože čtení bývá mnohem častější než zápis.
+    * 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 =====
+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í.
+Nabízí se znovu zvážit:
+  - Jakých hodnot mají identifikátory nabývat
+  - Jak má být realizováno indexování identifikátorů
+) Hodnoty identifikátorů
+- atomické nebo strukturované (hierarchicky složením id dokumentu+bundlu+zóny+uzlu)?
+- pokud hierarchické, nedal by se přece jenom nějak využít ord? (jasně, pak by se muselo občas přepočítávat, otázka ale je, jak je v reálu vkládání uzlů časté)
+- v jakém scopu musí být id unikátní?
+) 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 ''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.
+=== 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, ale seznam všech potomků (a obdobně dětí) nacpat do 8 bajtů, tedy 64 bitů. Uloží se tam indexy uzlů. Pokud má věta víc než 64 slov, tak se to uloží jinam jinak. Musím tedy udržovat pole všech uzlů (dle slovosledu). Přidání jednoho uzlu znamená posunout část tohoto pole o jeden prvek a přepočítat atributy _children a _descendants v podstatě všech uzlů. Asi by se to muselo dělat v Céčku, aby ty bitové operace byly rychlé.
+Č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 ''add_self'' vloží jejich rodič na správnou pozici. Metoda ''descendants'' uloží potomky do pomocného pole (klasickým průchodem do hloubky) a pak dotřídí. Perl i Python mají sort optimalizovaný na předtříděné sekvence (každý trochu jinak, Perl asi o něco lépe než pythoní timsort, který bere jen sekvence začínající na indexu 2^k, ale pro naše krátké sekvence to je asi úplně jedno). Nejde to implementovat jako iterátor bez toho pomocného pole.
+=== 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 (''process_anode''). Tedy je důležité zrychlit tento častý případ, kdy se ''descendants()'' volá na kořeni celého stromu.
+Každý uzel má atribut ''ord'' (to předpokládám ve všech zde diskutovaných implementacích, i když i to stojí za zvážení). Takže jde efektivně implementovat i metody ''prev_node'' a ''next_node'' (současná perlí implementace prochází neefektivně všechny uzly, než najde ten s ord+1).
+Volání ''descendants'' na nekořeni je stále pomalé, protože vyžaduje alokaci pomocného pole a dotřídění jako SORTED-CHILDREN.
+=== PROJECTIVE-OPTIMIZED ===
+V praxi jsou neprojektivity relativně řídký jev.
+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'').
+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.
+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).
+===== Profiling načítání CoNLL-U v Perlu =====
+Načítám cs-ud-train-l.conllu (68 MB, 41k sentences, 0.8 MWords). Časy v sekundách. Excl(usive) časy se sčítají, krom těch označených "x", což jsou pomocné (alternativní) experimenty.
+|excl.|incl.| code                                   | note|
+| 0.5 | 0.5 | ''while (<$fh>) {chomp;}''             | načtení řádka po řádce |
+| 0.3 | 0.8 | ''$line eq "" or $line =~ /^#/''       | test prázdné řádky a komentáře |
+| 0.6 | 1.4 | ''split /\t/, $line''                  | split 9 atributů dle tabů (výsledek se zahodí) |
+| 4.1 | 5.5 | ''($id, $form, $lemma,...) =...''      | uložení těch hodnot do proměnných |
+|x5.6 | 7.0 | ''my ($id, $form, $lemma,...) =...''   | uložení těch hodnot do nově alokovaných proměnných (které se asi odalokují, až vypadnou ze scope) |
+|x4.7 | 6.1 | ''@pole =...''                         | uložení těch hodnot do pole |
+|x3.9 |     | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů se stejnými atributy, tedy 200K uzlů za sekundu, viz [[#Benchmark konstruktorů v Perlu|následující benchmark]]|
+| 4.8 |10.3 | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů ze skutečných dat|
+|x0.4 |10.7 | ''push @all_nodes, $node''             | uzly se ukládají do pole|
+| 1.9 |12.2 | ''weaken($node->{_parent}=$root)...''  | uzly se ukládají do dokumentu, věší se na kořen, přidávají do jeho seznamu dětí|
+| 1.2 |13.4 | ''weaken($node->{_parent}=$parent)...''| uzly se věší na skutečného rodiče (v druhém průchodu, pomocné pole ''@parents'')|
+| 1.4 |14.8 | ''set_parent_nocheck($parent)''        | set_parent_nocheck místo optimalizovaného kódu (který neřešil předchozího rodiče atd.)|
+| 1.8 |**16.6**| ''set_parent($parent)''             | testování cyklů |
+|10.0 |26.6 | ''$root->create_child...''             | původní implementace, kde se uzly převěšují z kořene na skutečného rodiče a děti jsou pole|
+  * 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á. Samotné převěšení trvalo 7s (a ještě 3s asi kvůli ''$root->create_child(...)'' místo ''UD::Node->new(...)''). Kdyby byly děti implementované spojákem místo pole (to mám stále v plánu), tak to bude míň než 7s, 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.
+  * Vypuštěním testování cyklů v CoNLL-U závislostech se ušetří 1.8s, což za to asi nestojí.
+  * Původně jsem používal ''set_parent($parent, {cycles=>'no-check'})'', jenže vytváření toho hashe s parametrem spolklo asi polovinu času ušetřeného vypuštěním kontroly cyklů.
+  * Optimalizací kódu set_parent bez volání této metody se ušetří 1.4s. To za to asi taky nestojí.
+  * Poměrně dost času (4.1s) zabere naplnění 9 proměnných ''$form, $lemma,...''. Při ''UD::Node->new(form=>$form,...)'' se tyto proměnné kopírují do hashe, který bude instancí objektu. Celkem to trvá 4.8s, tedy zřejmě 4.1s kopírování a 0.7s vytvoření hashe a jeho blessování, ale celé je to v XS (asi o 20% rychlejší než v Perlu), takže kdo ví.
+  * Zdá se, že deklarováním 9 'my' proměnných až ve vnitřním cyklu přes uzly/řádky si přidám 1.5s. Možná proto, že se musejí odalokovávat (nebo přepisovat na undef), když vypadnou ze scope.
+  * Myslel jsem si, že by místo 9 proměnných mohlo být rychlejší jedno pole, ale to je pomalejší (už jen naplnění toho pole, zatím bez vytváření uzlu), a to o 0.6s. Vlastně se není co divit, protože perlí pole má krom nějakou režii navíc.
+  * Když jsem všechny uzly z celého souboru ukládal do jednoho pole, tak odalokování pole (s 0.8M uzlů) trvalo cca 1s. To jsem do profilingu nezahrnul, ale benchmark jsem musel ručně spouštět víckrát.
+===== 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;}

[ Back to the navigation ] [ Back to the content ]

Institute of Formal and Applied Linguistics Wiki

Differences