Differences

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

--- treex:api-implementation [2015/12/11 12:29]
popel
+++ treex:api-implementation [2015/12/14 03:43]
popel
@@ Line 43: / Line 43: @@
 Zde je vidět, že Devel::Size::total_size hlásí 96MB, ale ps hlásí 292MB.
 ==== Benchmark Perlích accessorů ====
-  Zápis následovaný čtením atributu
+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
@@ Line 64: / Line 65: @@
   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 101: / Line 103: @@
 Co z toho plyne?
-  * Všechny čtení i zápisy přístupy 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]]).
+  * 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.
@@ Line 116: / Line 118: @@
     * 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.

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

Institute of Formal and Applied Linguistics Wiki

Differences