This is an old revision of the document!
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 menší než v Perlu.)
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ů
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
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-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