[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
treex:api-implementation [2016/01/07 18:02]
popel
treex:api-implementation [2016/01/08 23:17] (current)
popel
Line 150: Line 150:
  
 === SORTED-CHILDREN === === 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.+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 === === SORTED-CHILDREN + ALL-NODES ===
Line 172: Line 172:
  
  
-===== Benchmark načítání CoNLL-U vPerlu ===== +===== Profiling načítání CoNLL-U v Perlu ===== 
-Načítám cs-ud-train-l.conllu.+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.
  
- 0.479s while (<$fh>) {chomp;} +|excl.|incl.| code                                   | note| 
- 1.409s + split /t/, ale hodnoty se zahodí a neukládají do proměnných +0.5 | 0.5 | ''while (<$fh>) {chomp;}''             | načtení řádka po řádce | 
- 5.722s totéžale hodnoty atributů se uloží do proměnných (které se hned zahodí+| 0.3 | 0.8 | ''$line eq "" or $line =~ /^#/''       | test prázdné řádky a komentáře | 
- 7.724s + uzly se vytvoří jako undef, uloží do pole @nodeskteré se zahodívytváří se bundly +| 0.6 | 1.4 | ''split /\t/, $line''                  | split 9 atributů dle tabů (výsledek se zahodí) | 
-10.917s nedělá se split ani rehang, všechny atributy jsou prázdný řetězecstromy ale mají uzly +| 4.1 | 5.5 | ''($id, $form, $lemma,...) =...''      | uložení těch hodnot do proměnných | 
-13.460s korektní načtení, netestují se cykly, nevolá se set_parent (ale zopakuje se jeho kód) +|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| 
-15.903s korektní načtenínetestují se cykly, volá se set_parent($parent, {cycles=>'no-check'); +|x4.| 6.1 | ''@pole =...''                         uložení těch hodnot do pole 
-16.646s korektní načtení, testují se cykly +|x3.9 |     | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů se stejnými atributytedy 200K uzlů za sekundu, viz [[#Benchmark konstruktorů v Perlu|následující benchmark]]| 
-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 +| 4.8 |10.3 | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů ze skutečných dat| 
-19.029s totéž, ale bez převěšování, tedy vše visí na kořenu+|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řenpř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ůchodupomocné 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 ]