GLib: Alokování paměti pro seznamy a stromy

Popíšeme si dopodrobna mechanizmus alokování paměti pro prvky stromů a seznamů. Ukážeme si také, že v jistých situacích použitá metoda velice „plýtvá“ pamětí a naučíme se, jak obsazení paměti optimalizovat.

Tvůrci knihovny GLib jistě považují stromy a seznamy za velmi důležité datové typy, protože si dali nemalou práci s tím, aby všechny jejich funkce „šlapaly“ co nejrychleji.

Nejvíce se snažili omezit režie spojené s alokováním paměti pro nové prvky – a udělali dobře, protože zrovna tady se ztrácí nejvíce strojového času. Uzly stromů a seznamů jsou relativně malé struktury (jejími prvky je několik málo pointerů). Dá se ale očekávat, že jich při práci v nějakém algoritmu bude mnoho.

Urychlování operací spojených s alokováním paměti pro uzly probíhá dvouúrovňově. Prvním stupněm je použití „chunků“ (Memory Chunks), tedy alokování paměti po větších blocích (více viz 6. část).

Programátoři GLib však šli ještě dále. Vytvořili jakýsi mechanizmus „recyklování“ přidělené paměti. Prvky (uzly) odstraněné ze stromů nebo seznamů se nedealokují, ale umisťují se do speciálního seznamu. Kdykoliv je pak třeba vytvořit nový prvek, paměť pro něj se nealokuje, ale využijí se tyto volné prvky.

Problém nastává, když v jedné chvíli potřebujeme uchovat do stromu nebo seznamu velké množství dat, které v vzápětí po provedení nějaké operace zase odstraníme. Do „seznamu recyklovatelných prvků“ se dostane mnoho položek, které se třeba už nikdy nepoužijí.

Zkrátka je nutno programátorovi umožnit „vynést odpadky“ a uvolnit z paměti všechny prvky čekající na „recyklaci“. To ale může být větší problém, než se zdá. Jak již bylo řečeno, prvky (uzly) se alokují v chuncích po blocích – jak dealokovat jednotlivé položky tak, aby v paměti nevznikaly „díry“, nevytvářela se fragmentace a všechno bylo pekelně rychlé?

Pojďme se podívat, jak se s tímto problémem „zametlo“.

Alokátory

Alokátory jsou struktury, které v sobě obsahují paměťový chunk (Memory Chunk) a onen již zmiňovaný seznam „recyklovatel­ných“ prvků.

Základem je jako obvykle nějaká neveřejná struktura, v tomto případě nazvaná GAllocator:

struct GAllocator;

Pro práci s ní byste měli používat výhradně následující funkce.

GAllocator* g_allocator_new(const gchar *name, guint n_preallocs); 

Vytvoří nový GAllocator. name je symbolické jméno alokátoru a použije se k pojmenování GMemChunk u, který se spolu s alokátorem vytvoří. Řetězec slouží jen k ladicím účelům, funkci můžete klidně předat  NULL.

Parametr n_preallocs je počet prvků na jeden blok alokované paměti. Větší blok znamená menší počet žádostí o alokování paměti a tím vyšší rychlost. Na druhou stranu se tak ale plýtvá pamětí. Standardní alokátory knihovny GLib používají defaultně 128-prvkové bloky paměti. Hodnota n_preallocs musí být v rozmezí od 1 do 65535.

void g_allocator_free(GAllocator *allocator); 

Tento příkaz odstraní celý GAllocator z paměti. Uvolní se tím i všechny prvky, které pomocí něj byly alokovány (včetně prázdných prvků čekajících na „recyklaci“).

Registrování alokátorů pro použití mechanizmy seznamů a stromů

Vytvoříme-li nový alokátor, musíme nějak knihovně GLib říct, aby jej používala. K tomu slouží následující funkce.

void g_list_push_allocator(GAllocator *allocator);
void g_list_pop_allocator(void);

void g_slist_push_allocator(GAllocator *allocator);
void g_slist_pop_allocator(void);

void g_node_push_allocator(GAllocator *allocator);
void g_node_pop_allocator(void);

Alokátory stromů a seznamů se uchovávají ve třech zásobnících (pro každý typ jeden). Ten, který je v zásobníku nejvýše (do zásobníku se dostal jako poslední) je považován za aktivní a právě jeho služeb pro práci s pamětí mechanizmy seznamů a stromů využívají.

Do zásobníku se GAllocator dostane příslušnou funkcí *_push_allocator(), ven pak pomocí funkce *_pop_allocator() (aktivním se stane další alokátor v zásobníku).

Podle toho, kterým datovým typům chcete alokátor přiřadit, použijte příslušné funkce g_list_*, g_slist_* nebo  g_node_*.

Je třeba pamatovat na to, že pro jednosměrné, obousměrné seznamy a stromy nelze dohromady použít stejný alokátor. Pro každý typ musí existovat samostatný GAllocator, který je pak používán všemi instancemi tohoto typu! (Tzn. vytvoříte-li a zaregistrujete nový GAllocator např. pro jednosměrné seznamy, budou jej používat všechny jednosměrné seznamy v programu tak dlouho, dokud jej ze zásobníku zase nevyjmete.)

Použití alokátorů

V podstatě mě napadají dva způsoby využití alokátorů, a sice:

• vytvoření vlastního alokátoru před započetím jakékoliv činnosti se seznamy nebo stromy s nastavením hodnoty n_preallocs na jinou než standardní hodnotu,
• dočasné zaregistrování speciálního alokátoru pro akci, která vyžaduje veliké množství prvků seznamů nebo stromů, přičemž chcete, aby se po jejím skončení veškerá paměť dealokovala a nečekala na „recyklaci“.

Příklad

Následující příklad ukazuje druhý způsob použití alokátorů. V úseku programu se zpracovává velké množství položek v seznamu, který je po skončení akce uvolněn. Aby jeho alokované prvky v paměti nezůstaly a marně nečekaly na recyklaci, použijeme nový alokátor, který po celé akci dealokujeme (a spolu s ním i všechny prvky tímto alokátorem vytvořené).

...
GAllocator *allocator;
GList *list = NULL;
guint i;

/* vytvoreni noveho alokatoru pro typ GList */
allocator = g_allocator_new("Muj GList alokator", 1024);
g_list_push_allocator(allocator);

/* nyni se dela nejaka slozita akce s GListem */
for (i = 0; i < 4096; i++)
  list = g_list_prepend(list, NULL);
list = g_list_reverse(list);

/* TOHLE JE DULEZITE! Pred jakymkoliv volanim externi
 * funkce je treba vratit GListu jeho puvodni alokator,
 * protoze nikdy nevime, co vsechno externi funkce dela
 * a jestli taky nepouziva GList! */
g_list_pop_allocator();
gtk_label_set_text(GTK_LABEL(some_label), "nejaky text");

/* a sup tam zpatky nas alokator... */
g_list_push_allocator(allocator);

/* zase nejaka akce s nasim dlouhym seznamem: */

/* uvolneni GListu z pameti (vsechny polozky zustanou
 * alokovane, jen se presunou do seznamu volnych
 * (recyklovatelnych) prvku */
g_list_free(list);

list = NULL;
for (i = 0; i < 4096; i++)
  list = g_list_prepend(list, NULL);

/* definitivni vraceni puvodniho alokatoru */
g_list_pop_allocator();

/* uvolneni naseho alokatoru z pameti - veskere prvky
 * alokovane timto alokatorem se skutecne uvolni a nebudou
 * cekat na "recyklaci" (volani g_list_free(list) je
 * v tomto pripade zbytecna ztrata casu) */
g_allocator_free(allocator);
...

Důležitá je část programu, ve které se volá funkce knihovny GTK ( gtk_label_set_text()). Před voláním jakékoliv funkce z externích knihoven je nutné vrátit mechanizmům seznamů a stromů jejich původní alokátory. Dělá se to proto, že nikdy nemůžeme vědět, zda-li tato funkce rovněž nepoužívá seznamy a stromy knihovny GLib – kdyby s nimi také pracovala a např. zrovna přidala do nějakého svého vnitřního seznamu další prvek, použil by se pro jeho vytvoření náš alokátor – a to není žádoucí (vzhledem k tomu, že po práci chceme náš alokátor ihned zrušit).

Alokátory jsou spíše specialita. Pokud nepracujete s velkým množstvím dat, nejspíše je ani nebudete potřebovat. Na druhé straně je dobré o nich vědět, až budete své programy optimalizovat na co nejvyšší výkon.