0xDEADBEEF

RSS odkazy english edition
««« »»»

Jazyk D, stringy, paměť a garbage collection

2. 7. 2020

S jazykem D jsem letmo koketoval už nějakou dobu, ale teprve nedávno jsem v něm napsal pár větších programů.

D není hip, není cool, není jako Rust nebo Go nebo jiné jazyky, které teď letí. D se nese v duchu C++: statická kompilace, template meta-programování, maximální možná efektivita, k tomu jako bonus přidává GC a snesitelnou syntaxi. Zdá se, že ho lidé používají, protože potřebují, co nabízí. Nepřitahuje je cool faktor.

Jeden D program mi vybuchnul na nedostatku paměti. Na laptopu mám jen 4 GB RAM, což pravda není mnoho, ale dle letmých odhadů by inkriminovanému programu mělo stačit 800 MB. Co se tady děje? Precizní kontrola nad pamětí je jedna z vlastností, která mě k D přitáhla. Nastal čas zjistit pár skutečností: Jak je uspořádaná paměť dynamicky alokovaných objektů a polí? Jaká je paměťová režie alokací? Jak funguje GC?

Nejspíš nepůjde o compacting kolektor umožňující rychlou bump alokaci. Specifikace výslovně povoluje GC přesouvat objekty, ale dle všeho to současná implementace GC nedělá. Můj tip je ten, že takhle to lépe spolupracuje s jazykem, který má nahé pointery. Vypadá to také na stop the world přístup. Se zapnutým profilováním GC problematický program hlásí "Max Pause Time: 1041 milliseconds", tak to navíc nebude ani příliš sofistikovaný STW, nic co by se přibližovalo state of the art v JVM2 nebo Go světech.

Přítomnost pointerů do velké míry ovlivní, jak je organizována halda. D povoluje interní pointery, které neukazují na začátek objektu ale někam doprostřed. Takový pointer udrží naživu celý objekt. Z toho plyne, že GC musí disponovat efektivním mechanismem jak z libovolného pointeru zjistit začátek objektu do něhož ukazuje.

Tohle se ve velkém týká stringů. Ty jsou v D reprezentovány jako neměnná pole znaků. Pole není víc než pohled do paměti kdesi na heapu. S přivřenýma očima to může vypadat asi takhle:

alias string = immutable(char[]);

struct array(T) {
  T* data;
  ulong length;
}

Slice operace nealokuje nový neměnný string (jak to dělá metoda substring v Javě), ale vrátí jen pohled na podsekci dat. Pohled na jediný bajt udrží celý blok dat na haldě naživu.

string a = "eee fff ggg".dup; // dup, aby došlo o alokaci na heap
string b = a[0..3];           // slice operace

char[] aa = cast(char[]) a;   // zbavit se immutable kvalifikátoru
aa[1] = 'X';                  // změnit data v a

writeln(b);                   // změna se promítne do b a tedy
                              // a i b ukazují do stejné paměti kdesi na heapu

Jeden z možných přístupů jak implementovat kontrolu dosažitelnosti objektů přes vnitřní pointery, je heap segregovaný podle velikosti, jak to dělá Go. Objekty jsou alokovány v regionu obsahující pozice o velikosti mocniny dvou, jeden objekt na slot. Zjistit, do kterého objektu pointer ukazuje, je pak stejně snadné jako odmaskovat několik nejnižších bitů.

Mohl bych to ověřit ze zdrojáků, ale dobrá zpráva je, že D nemaskuje paměť a pointery za závojem abstrakce a (i když jde o nedefinované operace1 ) můžeme snadno zkoumat, jak přesně je paměť organizovaná.

const len = 100;
auto a = new ubyte[len];
auto b = new ubyte[len];
writeln(b.ptr - a.ptr);

Tohle je asi nejjednodušší program, který to ověří. Vytvoří dvě pole stejné velikosti, runtime je alokuje ve stejném regionu těsně vedle sebe. Rozdíl v pointerech pak odpovídá velikosti alokační jednotky.

Pro různé velikosti to vrací tyto hodnoty:

  alokace     zabere místa
 1 -  15 B         16 B
16 -  31 B         32 B
32 -  63 B         64 B
64 - 127 B        128 B

Pro krátké alokace do 256B runtime používá jeden byte pro zaznamenání obsazené velikosti. (Konstanty udávající tyto limity jsou definované v rt/lifetime.d.)

Tohle má za následek, že alokace dat o velikosti mocniny dvou představuje ten nejhorší možný případ pro pro efektivní využití místa. Ten bajt pro velikost způsobí, že se vždy o něco málo přestřelí a alokuje ve větším regionu.

Čísla v tabulce jsou jen surová data na haldě, je k nim potřeba ještě podpůrná struktura obsahující pointer na data a délku pole. Ta zabere dalších 16B.

Java, tak jak je v současnosti implementována v OpenJDK (64bit verze s komprimovanými oopy), potřebuje 16B pro hlavičku pole + alokace je zarovnána na 8B. To mimo jiné znamená, že Java je vždy efektivnější ve využití místa, aspoň co se polí týká.

Pro objekty pevné délky není zaznamenáno kolik bitů obsadily a proto nepřetékají při velikosti 2n, stále ale plýtvá místo, když nemají přesně velikost mocniny dvou. Přesto v tomhle ohledu nad JVM vede, protože D může alokovat structy v souvislém poli, ne jako pole referencí na objekty a to samo o sobě může ušetřit obrovské množství místa.


Pozn:

  1. Pointerová aritmetika v D má podobná pravidla jako abstraktní stroj Céčka. GDC program kompiluje do x86 a tam je jedno, odkud se pointer vzal a derefeferencuje ho bez kecání. Alternativní řešení, jak tomuhle nedefinovanému chování zabránit a předejít těm nejhorším kritickým zranitelnostem, představují capability architektury. Příklad jak můžou vypadat je v prezentaci o architektuře CHERI.
  2. V Java světě to dlouho nebyla žádná sláva, ale teď mají rovnou dva open source kolektory s malými pauzami. Shenandoah a ZGC.

+1: Něco nového výzkumu z oblasti GC. Hlavní myšlenka: Deterministická adresa kam GC přesune objekt umožní efektivně reprezentovat tabulky mapující ze staré na novou adresu.

+2: Historie jazyka D

+3: GC potřebuje extra prostor, aby mohlo dýchat. D ve výchozím stavu směřuje velikost heapu, aby byla dvojnásobek používané paměti. To se dá změnit přepínačem při spuštění programu: --DRT-gcopt="profile:1 heapSizeFactor:1.2". Halda je pak menší, ale runtime stráví víc času úklidem paměti.

+4: D Slices

píše k47 (@kaja47, k47)