[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

This is an old revision of the document!


Table of Contents

Uložení uzlů

Parsito používá vector<node> nodes; a pak nodes.emplace_back(nodes.size(), form);.
Tedy objekty uzlů se vytvářejí přímo v poli (vectoru). To ale jde jen v C++, nikoli v Perlu, Pythonu, Javě.
Tam mohu udělat jen pole referencí/pointerů na objekty typu Node.

V Parsitu v node.h je int head; vector<int> children;, tedy odkazy na rodiče a děti jsou inty, odkazy do toho pole.
V Perlu (64bit) zabírá int (tedy scalar) 24 bajtů, což je stejně jako reference.
(A pole milionu intů zabírá 32MB, což je stejně jako pole milionu referencí.)
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íčů

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 __slots__ nebo Python > 3.3 nebo dědit od Atom nebo namedtuple.

Sdílení hodnot

Mnoho uzlů má stejné lemma, formu, formém, tag atd.
Mohl bych tedy vytvořit slovník těchto stringů (mapující string na integerové idéčko a naopak) a do instancí uzlů ukládat místo stringů jen ta idéčka.

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, 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
perl -MDevel::Size=:all -E 'my $s="s"; say total_size {map {$_=>$_} 1..1_000_000}' # int     96M
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 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á.
Mám-li v uzlu 4 stringové atributy (form,lemma,upostag,deprel), tak ušetřím 128 bajtů na uzel.

Samozřejmě by bylo mnohem úspornější tyto datové struktury implementovat v Céčku a jen udělat binding pro Perl a Python.

Je dobré testovat i celkovou paměť virtuální i resident:

perl -MDevel::Size=:all -E 'my $s="s"; say total_size {map {$_=>$_} 1..1_000_000}; system "ps -ovsz,rss,size $$"'
96277560
  VSZ   RSS  SIZE
292780 271456 270416

Zde je vidět, že Devel::Size::total_size hlásí 96MB, ale ps hlásí 292MB.

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
A-lv-check-sentinel    735 179/s
A-set-check-perl     2 366 578/s
H-set-check-perl     2 383 127/s
---
H-set-lemma-perl     2 725 258/s
A-set-lemma-perl     2 780 315/s
A-lv-lemma-perl      3 143 931/s
H-lv-lemma-perl      3 174 754/s
---
A-set-lemma-xs       4 542 098/s
H-set-lemma-xs       4 955 017/s
H-lv-lemma-xs        5 090 174/s
A-lv-lemma-xs        5 716 536/s
---
H-direct             9 442 579/s
A-direct            10 180 350/s
Čtení atributu:
h-lv_check_sentinel  1 147 836/s
a-lv_check_sentinel  1 147 836/s
---
h-get_lemma_perl     2 453 219/s
a-get_lemma_perl     2 572 440/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
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?

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:

  1. Jakých hodnot mají identifikátory nabývat
  2. 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é, 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í?

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 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 ]