ARCHIV

Perl (143) - Struktura datových typů, správa paměti

Jednou z nevýhod dynamicky typovaných jazyků je neefektivní spotřeba paměti. Měli bychom aspoň trochu tušit, jak si vede konkrétně Perl.

9.10.2011 00:00 | Jiří Václavík | Články autora | přečteno 11010×

Již jsme několikkrát narazili na měření rychlosti programů nebo jejich úseků. Zatím však vůbec nepřišla řeč na druhý významný systémový zdroj - paměť. Částečně i proto, že na její měření nám nestačí pouhé stopky.

Programátora v Perlu nezajímá, co se kdy do paměti má ukládat. Má na to své "lidi". Alokaci a s tím související věci vůbec neřeší. Přesto je dobré, minimálně kvůli informaci, jak Perl funguje (nebo i kvůli jiným věcem, například debugging XS programů), alespoň tušit, jak Perl s pamětí přidělenou operačním systémem pracuje.

Jako vždy jde mezi pamětí a rychlostí o kompromis. Pro dobrý příklad se vraťme k memoizaci. Pomocí ní můžeme zvýšit rychlost, ale vždy za cenu větších paměťových nároků.

Jak na tom Perl tedy je? Vzhledem k velké rychlosti programů v Perlu se dá o paměťových nárocích leccos usuzovat a asi to nikoho moc nepřekvapí. Perl je významným spotřebitelem paměti, a tak si pro dnešek sundáme růžové brýle (ale jen na chvíli).

Není tajemstvím, že Perl preferuje výkon nad úsporou paměti. Perl si raději i jednoduchou věc uloží, než aby ji musel znovu vypočítat (později se podíváme na konkrétní příklady). Když přidáme pokročilé datové typy a dynamické typování (v důsledku čehož má například integer minimálně 16 bajtů, float 24, řetězec 28 atd.), pramení z toho vysoká paměťová náročnost.

Když libovolný proces potřebuje paměť, požádá o ni operační systém. Ten mu přidělí adresy, které může využívat. Perl se operačnímu systému nebojí říct si vždycky o velký kus (který celý momentálně ani nepotřebuje) a k zabírání paměti celkově přistupuje s filozofií "na horší časy". Když přestane část paměti využívat, tak ji operačnímu systému nevrací - co kdyby ji ještě na něco potřeboval.

Vnitřní reprezentace proměnných

Prozkoumejme však práci s pamětí a s tím související vnitřní strukturu datových typů podrobněji pomocí několika z CPANu dostupných modulů. Budou nás zajímat hlavně tyto dva základní.

use Devel::Peek qw(Dump);
use Devel::Size qw(size total_size);

Proměnná obvykle mívá hodnotu. Ta může být jedním z následujících typů.

• SV - skalární
• AV - pole
• HV - hash
• RV - odkaz
• GV - typeglob
• CV - podprogram

Tyto zkratky jsou vlastně datovými typy v jazyce C a každý typ má nějaké API, se kterým lze pracovat. Pro skalární hodnoty jsou všechny tyto funkce deklarovány v hlavičkovém souboru sv.h, který můžeme použít v našem C programu. Bývá umístěn v adresáři jména typu /usr/lib/perl5/5.12.3/i586-linux-thread-multi/CORE. Jsou zde nízkoúrovňové funkce pro vytvoření nového skaláru, přiřazení do skaláru (zvlášť pro celé číslo, desetinné číslo, řetězec atd.) a podobně. Například pro funkci, která z řetězce vytvoří novou skalární hodnotu, máme deklarovanou následující hlavičku.

SV* newSVpv(char* str, int len);

Tomu se zde nebudeme více věnovat, ale koho by více zajímalo použití těchto hlavičkových souborů nebo vnitřní struktura jazyka obecně, nechť se podívá na manuálovou stránku perlguts(1).

Skalární proměnná v paměti

Skalární proměnná může obsahovat buď celé číslo (IV), celé číslo bez znaménka (UV), desetinné číslo (NV), řetězec (PV) nebo speciální magickou hodnotu (MG). Později uvidíme, že může obsahovat i kombinace některých hodnot.

Vytvořme na začátku nějakou proměnnou. Nic do ní nebudeme přiřazovat, pouze ji deklarujeme. Pomocí funkcí Dump a size můžeme zkoumat některé nízkoúrovňové informace.

my $skalar;
print Dump($skalar);
print "Velikost: ", size($skalar);

Výstupem Dump je následující text.

SV = NULL(0x0) at 0x832d31c
  REFCNT = 1
  FLAGS = (PADMY)

Jak již víme, SV znamená Scalar Value. Za SV následuje NULL(0x0), což znamená, že proměnná je prázdná a na konci řádku máme její adresu. V REFCNT je počet odkazů na tuto proměnnou a ve FLAGS jsou různé flagy (například, že je proměnná deklarovaná pomocí my, také zde ale můžeme mít informaci, že jde o objekt atd.).

Výstupem funkce size pak je počet bajtů, které proměnná zabírá. V našem případě je to 16! To je dost vysoké číslo na to, že tato proměnná nedrží žádnou informaci. Každá proměnná tedy zabírá minimálně 16 bajtů v paměti.

Dále můžeme zkusit do proměnné přiřadit řetězec.

my $skalar = "qwerty";
print Dump($skalar);
print "Velikost: ", size($skalar);

Opět se můžeme podívat na výstup Dump.

SV = PV(0x830e724) at 0x832d31c
  REFCNT = 1
  FLAGS = (PADMY,POK,pPOK)
  PV = 0x8328024 "qwerty"\0
  CUR = 6
  LEN = 8

Přibylo zde několik nových řádků. CUR je počet znaků a LEN počet alokovaných míst pro znaky. Ještě tedy můžeme trochu přidat a pak bude potřeba přialokovat další paměť. LEN je vždy alespoň o 1 větší, protože je zde započítán i jeden speciální znak.

S tím souvisí i velikost. Ta vzrostla na 32 bajtů. Zajímavé je zkusit si přidávat nebo ubírat postupně znaky. Uvidíme, že velikost vždycky jednou za čas podle LEN a CUR skočí, ale často se nemění. Také je zajímavé vyzkoušet přidávat jiné než ASCII znaky.

Dále zde je PV (pointer value), což, znamená, jak opět víme, že jde o řetězec. Zajímavé je, že pokud řetězec někde použijeme jako číslo, změní se PV na PVIV a bude mít jak řádek PV tak i IV - tedy pro oba datové typy bude celá informace uložena zvlášť. Toto lze udělat i pro další dvojice, například můžeme dostat PVUV nebo PVNV. Podívejme se tak potom vypadá výpis Dump pro následující situaci.

my $c = 1;   # použijeme jako celé číslo
print "$c";  # použijeme jako řetězec
print Dump($c);

Zde je výsledek.

SV = PVIV(0x8323378) at 0x832d31c
  REFCNT = 1
  FLAGS = (PADMY,IOK,POK,pIOK,pPOK)
  IV = 1
  PV = 0x8328024 "1"\0
  CUR = 1
  LEN = 4

Takové chování se samozřejmě se projeví i na paměťové náročnosti - uložené je obojí, takže celkem je zabráno 32 bajtů. Tady je pěkně vidět, jak Perl s pamětí hospodaří.

Ještě jsme na začátku zmínili magický typ. Taková proměnná se vyznačuje tím, že má nějakou speciální vlastnost, například spojení s nějakou akcí. To, že k takové proměnné přistoupíme může například způsobit spuštění nějakého jiného procesu. Typicky jde o navázané proměnné. Několik speciálních proměnných má magický typ, například $!. Funkce Dump zde odhalí následující.

SV = PVMG(0x83536a0) at 0x832d334
  REFCNT = 1
  FLAGS = (GMG,SMG)
  IV = 0
  NV = 0
  PV = 0
  MAGIC = 0x833b8e4
    MG_VIRTUAL = &PL_vtbl_sv
    MG_TYPE = PERL_MAGIC_sv(\0)
    MG_OBJ = 0x832d324
    MG_LEN = 1
    MG_PTR = 0x8334f44 "!"

Další způsob, jak získat magickou hodnotu, je režim nakažení. Každá nakažená proměnná je typu MG. S využitím této vlastnosti pak funguje například modul Safe, který umožňuje s nakaženými daty například i provedení eval, pokud není výsledkem vyhodnocení nějaká zakázaná instrukce.

Odkaz v paměti

Dump zobrazuje u odkazů hierarchii. Takto mohou vypadat informace pro odkaz na číslo 123.

SV = IV(0x832d4f8) at 0x832d4fc
  REFCNT = 1
  FLAGS = (PADMY,ROK)
  RV = 0x832d31c
  SV = IV(0x832d318) at 0x832d31c
    REFCNT = 2
    FLAGS = (PADMY,IOK,pIOK)
    IV = 12

Funkce size ukazuje v případě odkazu velikost toho, na co se odkazuje, což taky většinou chceme. V případě odkazu na odkaz na hodnotu však již dostaneme skutečně velikost odkazu na hodnotu, nikoliv hodnotu.

Volání Dump pro odkazy se bude hodit zejména pro zkoumání polí a hashů.

Pole v paměti

Podívejme se i na ostatní datové typy. Pole (AV) je ve skutečnosti dynamickým seznamem odkazů na skaláry. V perlguts(1) nebo hlavičkovém souboru av.h opět nalezneme API seznamů.

Tiskneme-li výstup Dump u odkazu na pole (například pole [1 .. 8]), získáme jak celkovou analýzu (počet prvků, poslední prvek, typ hodnot, kolik paměti je alokováno a kdy bude potřeba přialokovat atd.) tak i postupně informace o několika úvodních prvcích. Výstup tedy vypadá takto.

SV = IV(0x832d318) at 0x832d31c
  REFCNT = 1
  FLAGS = (PADMY,ROK)
  RV = 0x8310874
  SV = PVAV(0x83118dc) at 0x8310874
    REFCNT = 1
    FLAGS = ()
    ARRAY = 0x832c6e4
    FILL = 7
    MAX = 7
    ARYLEN = 0x0
    FLAGS = (REAL)
    Elt No. 0
    SV = IV(0x83109c0) at 0x83109c4
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 1
    Elt No. 1
    SV = IV(0x83115d0) at 0x83115d4
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 2
    Elt No. 2
    SV = IV(0x83115c0) at 0x83115c4
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 3
    Elt No. 3
    SV = IV(0x8311600) at 0x8311604
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 4

Funkce size nám u polí přestává fungovat tak, jak bychom si představovali. Měří pouze velikost struktury, nikoliv už dat v ní uložených. Pro každé stejně velké pole vrátí size stejnou hodnotu. Abychom získali velikost i s daty, je třeba použít total_size, která následuje reference.

Například struktura následujícího desetiprvkového pole zabere 28 bajtů. S obsahem je to však dohromady už 1028.

my $pole_r = ("." x 100) x 10;

Hash v paměti

Podobné informace získáme i pro hashe. Hash je dvojice jednoznačného řetězce a ukazatele na skalár. Řetězec lze přitom namapovat na celé číslo a pak lze hash reprezentovat jako obyčejné dynamické pole. Mapování přitom funguje poměrně zajímavě. Na bázi nějakého hashovacího algoritmu (poznamenejme, že odtud pochází název pro datový typ hash) totiž ke každému klíči přiřadíme celé číslo mezi 1 a 2ⁿ, kde n je nějak zvolené.

Přitom může docházet ke kolizím! To znamená, že se dva klíče mohou namapovat na stejné číslo. Skutečnost je taková, že se vlastně uchovává pro každé číslo spojový seznam všech hodnot, jejichž klíče se na toto číslo zobrazily hashovací funkcí.

Ideální stav by byl, kdyby byly prvky hashe v poli co nejrovnoměrněji rozloženy (to jest, aby spojové seznamy měly pokud možno právě jeden prvek). To zajišťujeme za prvé vhodným hashovacím algoritmem. S ním mimochodem můžeme pomocí API manipulovat (třeba i proto, že máme nějak specificky zvolenou množinu klíčů hashe a výchozí algoritmus tím pádem nevyhovuje, protože tyto klíče mapuje často na stejné hodnoty). Stačí předat číslo prvku (tj. námi alternativně zahashovanou hodnotu) funkci hv_store deklarované v hlavičkovém souboru hv.h, která ukládá prvek hashe do tabulky. Výchozí hashovací algoritmus je definován jako makro PERL_HASH(hash, key, klen), kde klen je délka klíče.

hash = 0;
while (klen--)
    hash = (hash * 33) + *key++;
hash = hash + (hash >> 5);        /* od verze 5.6 */

Zopakujme, že pokud tedy proženeme náš klíč tímto algoritmem, získáme v proměnné hash nějaké číslo, pod které se uloží jako další prvek spojového seznamu naše hodnota.

A za druhé co nejrovnoměrnější rozdělení zajišťujeme vhodnou volbou n. Jak hash roste na velikosti, roste i n. Pokud počet prvků hashe dosáhne 2ⁿ (tj. na jedno číslo jeden prvek hashe), rozšíří se tabulka automaticky zvýšením n o 1.

Dodejme, že tiskneme-li hash ve skalárním kontextu, získáme dvě čísla oddělená lomítkem:

• Počet prvků hashe, tj. počet klíčů
• 2ⁿ, tj. velikost tabulky, do které se mapují prvky hashe na základě hashovacího algoritmu

Například následující kód vytiskne 2/8.

%x = (prvni => 1, druhy => 2);
print scalar %x;

Kdybychom přidali dalších 6 prvků, dostali bychom na výstupu 8/8. Kdybychom však dostali ještě jeden další prvek, již by se vytisklo 9/16, protože by se zvýšilo n. Jakmile se zvýší, není třeba nic přepočítávat. Prvky již přítomné si svoje číslo ponechají nadále.

Čím vyšší je poměr těchto dvou čísel, tím je algoritmus paměťově úspornější. Naopak, čím je poměr nižší, tím rychleji jsme schopni z hashe číst, protože je menší pravděpodobnost, že budeme nuceni prohledávat delší spojový seznam.

Uveďme nevýznamnou, avšak zajímavou poznámku na okraj. Pokud očekáváme hodně prvků, lze velikost tabulky nastavit přímo v programu následujícím příkazem.

keys %x = 1000;

Díky němu bude překladač vědět, že má dynamické pole naalokovat větší než původně chtěl, protože to časem bude potřeba. Po jeho zavolání se n nastaví tak, aby 2ⁿ byla nejbližší vyšší mocnina dvou. Přidáním tohoto řádku by tak měl předchozí kód za následek vytisknutí 2/1024.

Podívejme se ale, jak bude vypadat výstup funkce Dump u hashů. Nyní k němu asi už není třeba podrobného komentáře.

SV = IV(0x83115a0) at 0x83115a4
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x832d35c
  SV = PVHV(0x83186dc) at 0x832d35c
    REFCNT = 3
    FLAGS = (OOK,SHAREKEYS)
    ARRAY = 0x83351f4  (0:1022, 1:2)
    hash quality = 125.0%
    KEYS = 2
    FILL = 2
    MAX = 1023
    RITER = -1
    EITER = 0x0
    Elt "prvni" HASH = 0x84356c8d
    SV = IV(0x8310870) at 0x8310874
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 1
    Elt "druhy" HASH = 0xa05ccdc7
    SV = IV(0x83109f0) at 0x83109f4
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 2

Ostatní datové typy

Samozřejmě to nejsou všechny datové typy. Typegloby jsou reprezentovány hashovou tabulkou a funkce Dump ukáže například následující.

SV = PVGV(0x8346888) at 0x832d334
  REFCNT = 4
  FLAGS = (MULTI,IN_PAD)
  NAME = "x"
  NAMELEN = 1
  GvSTASH = 0x8310764   "main"
  GP = 0x8334f8c
    SV = 0x832d344
    REFCNT = 1
    IO = 0x0
    FORM = 0x0
    AV = 0x832d3b4
    HV = 0x0
    CV = 0x0
    CVGEN = 0x0
    LINE = 1
    FILE = "-e"
    FLAGS = 0xa
    EGV = 0x832d334     "x"

Pro úplnost se podívejme na výstup Dump pro anonymní podprogram.

SV = IV(0x8310870) at 0x8310874
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x832d32c
  SV = PVCV(0x83290dc) at 0x832d32c
    REFCNT = 2
    FLAGS = (PADMY,ANON,WEAKOUTSIDE)
    COMP_STASH = 0x8310764      "main"
    START = 0x8334d48 ===> 0
    ROOT = 0x8327cb0
    GVGV::GV = 0x832d36c        "main" :: "__ANON__"
    FILE = "-e"
    DEPTH = 0
    FLAGS = 0x90
    OUTSIDE_SEQ = 94
    PADLIST = 0x832d33c
    PADNAME = 0x832d34c(0x8334ebc) PAD = 0x832d3ac(0x8334f64)
    OUTSIDE = 0x8310a04 (MAIN)

Pro více informací lze opět doporučit stránku perlguts(1).

Memchmark

Existuje analogie modulu Benchmark pro měření paměťových nároků. Memchmark exportuje funkci cmpthese, která spočítá, kolik paměti zabírá který podprogram. Funguje tak, že vytvoří nový proces, zjišťuje v intervalech jeho paměťové nároky a hledá maximální hodnotu. Díky tomu se však nemusí modul vždy chovat 100% správně. Zde je malý příklad použití.

use Memchmark qw(cmpthese);
cmpthese(
    maly  => sub { ("." x 1000) x  10_000 },
    velky => sub { ("." x 1000) x 100_000 }
);

Na výstupu dostaneme přibižnou paměťovou náročnost jednotlivých podprogramů.

test: maly, memory used: 9871360 bytes
test: velky, memory used: 99872768 bytes

Verze pro tisk