0xDEADBEEF

GC a granularita alokací v jazyce D

Paměť je levná a hojná, ale přesto je dobré jí zbytečně neplýtvat, zvlášť na velice malých strojích. Představte si, že chcete provozovat nějaký podstatný program na Raspberry Pi s gigabajtem paměti. Proč zrovna Pi? Roční provoz stojí asi 80 korun v elektřině. Třeba proto.

A tady se dostávám zas k jazyku D. Ten jako správný systémový jazyk nabízí kompletní kontrolu nad každým bajtem paměti a každým cyklem procesoru. Zároveň v sobě ale má i GC, můžete ho použít pro pohodlnější život, ale nemusíte. Je to na programátorovi, co chce a co požaduje. Jaká ale je cena toho GC? Zajímá mě hlavně, jak se projeví na využití paměti.

Články o GC v jazyce D obvykle stráví značné množství času vysvětlováním, jak se mu vyhnout. GC v D je stop-the-word typu, vede k (nechtěným) pauzám programu a tak to nejspíš zůstane i nadále. Walter Bright řekl, že nechtějí investovat do lepšího GC bez pauz, protože to by znamenalo použití bariér a ty něco stojí i v případě, kdy GC neběží, což je neakceptovatelné pro systémový jazyk.

Cena GC má dva aspekty: jednak čas pauzy a dopad na rychlost běhu, to mě v tomto případě nezajímá a druhak vede k vyšší spotřebě paměti. GC přestřelí a alokuje si víc RAM, než striktně vzato potřebuje. Alokace nejsou dealokovány okamžitě, ale sedí na haldě do nejbližšího GC cyklu. Volné místo amortizuje práci GC cyklu.

Když v situaci, kdy mám 1 GB živých dat a 1 GB volného místa, dojde k alokaci 1 GB dat, která nepřežijí, alokace toho 1 GB vyvolá práci úměrnou 1 GB živých dat. (Doba GC typicky závisí na velikosti živých dat). Naproti tomu v opačném extrému, kdy bych měl jen jeden bajt volného místa a 1 GB živých dat, 1 B alokace by vedl k práci úměrné 1 GB, tedy amplifikace 1000000000×. GC potřebuje určité místo extra, aby fungoval efektivně.

D poskytuje přístup k GC. Je možné programově ovlivňovat jeho chování.

import core.memory : GC;

GC.malloc();    // alokuje data na haldě spravovanou GC
GC.free();      // okamžitě dealokuje data
GC.collect();   // vynutí GC cyklus
GC.minimize();  // vrátí nevyužitou paměť operačnímu systému

Hodit se může kombinace collect() + minimize(), když se program dostal do stavu, kdy dokončil velké alokace a bude trávit čas prací s tím, co má. collect() vynutí GC cyklus a minimize() signalizuje, že nevyužitá paměť se může vrátit operačnímu systému.

Další věc ovlivňující, kolik paměti program spolyká, je granularita alokací. Posledně jsem o tom začal psát. D má v současné podobně heap segregovaný podle velikosti objektů. Nejmenší má 16B, pak to jde po mocninách dvou až do 4 kB, větší objekty jsou zarovnané na 4 kB. Alokace probíhají v nejmenší oblasti, která je rovná nebo větší požadované velikosti. Pochopitelně.

Můžeme si to snadno ověřit následujícím programem. capacity udává maximální velikost na jakou může pole vyrůst, než ho je třeba přealokovat. Vždy má velikost o něco málo nižší než mocnina dvou (několik bajtů spolykají nutné metainformace).

foreach (size; 0 .. 4096) {
  auto arr = new byte[size];
  writeln(arr.length, " ", arr.capacity);
}

Toto uspořádání má za následek, že mnoho malých alokací může v nejhorším případě spotřebovat 2× víc paměti než je nutné, typicky 1.5× tolik.

Mám jeden program, který alokuje 3.5 milionů polí. Velikost jejich užitečných dat (myArrays.map!(a => a.length).sum) je 168.5 MB, ale celková kapacita myArrays.map!(a => a.capacity).sum odpovídající skutečně zabranému množství paměti, je 201.2 MB. 20% extra.

Je možné ušetřit místo alokací jednoho gigantického pole, které pak slice operace rozsekají na požadované kousky. Velké alokace mají granularitu 4 kB a vyplýtvané místo tak bude zanedbatelné.

Podle zdrojáku to vypadá, že GC má navíc režii až 5% pro bitová pole ve structu Pool, ve němž si GC uchovává informace, které bloky obsahují pointery, které je třeba finalizovat, které už označil, které jsou volné a tak podobně.

Nakonec ještě jeden mini-poznatek:

Funkce array pro konverzi Range na pole vrátí výsledek, ke kterému není možné nic připojit bez další alokace i když se logicky musí nacházet v části heapu, by místo měl.

auto arr = [1, 2, 3, 4].map!(to!long).array;
writeln(arr.capacity); // 0 - append vždy alokuje

Naproti tomu, když sami alokujeme pole potřebné délky a výsledek do něj zkopírujeme, pole ví kolik má extra místa a append operátor ~ nemusí okamžitě alokovat.

auto arr = new long[4];
[1, 2, 3, 4].map!(to!long).copy(arr);
writeln(arr.capacity); // 7 - append nemusí alokovat

(Navíc ~ operátor není nejrychlejší na světě a v určitých situacích představuje úzké hrdlo.)