The Tale of Two (.NET) Heaps

Konstanta, která rozlišuje, kdy objekt spadne do normální haldy nebo LOH je 85000B (nikoliv 85KiB). Toto platí alespoň do verze .NET4.0 .

Více o LOH http://msdn.microsoft.com/en-us/magazine/cc534993.aspx .
Jak lze zapříčinit fragmentaci normální haldy http://blogs.msdn.com/b/yunjin/archive/2004/01/27/63642.aspx .
Pozor oba články jsou starší.

Obecně lze na GC psát efektivně jen člověk musí vědet jak funguje.

Kdo si s tím chce hrát, může použit pin_ptr a alokovat jako o závod. Po uvolnění objektů profiler ukáže spoustu volné paměti a správce úloh celou zaplněnou, přičemž nebude možné alokovat dál.

Máte někdo nějaký návod, jak napsat lepší alokátor v STL?

Já jsem měl tuhle sen, že by vektor v sobě nesl předalokovaný prostor. Nepovedlo se. Alokátor je naprosto šílený.

V mé knihovně je to jednoduche

AutoArray<int, StaticAlloc > pole;

(funguje jako std::vector, ale obsahuje prostor pro 1000 prvku int)

@3 zatracená diskuze. Je tam StaticAlloc a v šipečkách tisícovka

Až dodnes jsem si myslel, že až tak mizerný programátor v C# (v .NETu) nejsem :)

Mohl bych poprosit autora blogpostu nebo kohokoliv jiného o nasměrování, kde je vhodné pro začátek nastudovat pár low-level věcí týkajících se .NETu abych mohl povýšit na pomyslném žebříčku kvalit programátora? Dík

@5 MSDN? C# používá jen managed haldu a zásobník, to je jednoduché. Jinak je těch hald vlastně 5 (a 2 zásobníky) :-)

[3], Ondra Novacisko: Napsat dobrý alokátor je věda.

Není to sranda a řeší se tam daleko více věcí, než je fragmentace, nebo využití místa. Špatný alokátor může také program pekelně zpomalit, protože se zasahuje i do low level procesorových a low level operačně systémových záležitostí. Jako základ, je třeba zajistit, aby program minimálně cachoval, aby se minimalizoval počet výpadků stránek, apod.

Napsat dobrý alokátor, který by byl skutečně dobrý, tedy alokoval paměť tak, aby program běžel maximální rychlostí, měl navíc rychlý postup alokace a dealokace, zároveň minimálně fragmentoval a měl minimální overhead co do využití paměti i výkonu procesoru – je věc, se kterou klidně obhájíte i 10 doktorátů.

Stále je místo pro výzkum i nové vědecké objevy a pro Vaše bádání v matematické teorii. Klidně na tom můžete postavit celý svůj život, ba dokonce, pokud uděláte průlomový objev, možná i Nobelova cena se vyskytne.

Ale pro Vás je vše easy peasy.

[7] nobelova cena za matematiku sa neudeluje :)

[8]: moje chyba, lhal jsem :-)

Nicméně za kvalitní teoretické práce v oblasti vylepšení alokátorů získá věhlas a nejlepší světové univerzity mu budou nabízet místo za plat, který jistě minimálně desetinásobně přesáhne jeho plat u seznamu.

Zkrátka za přelomovou práci v oblasti alokace paměti je do konce života boháč.

A pokud vylepší Microsoftu jeho alokátor, tak taky.

Způsob alokace paměti totiž neovlivňuje jen fragmentaci, ale také rychlost alokace, stejně jako rychlost programu. Způsob alokace ovlivňuje i efektivitu procesorové cache při běhu programu, stejně tak jako četnost swapování a výpadků stránek, stejně jako mnoho dalšího.

Je až příliš parametrů a věcí, které by měl dobrý alokátor udržet na příznivých hodnotách. Není divu, že se v tom i po desítkách letech, co lidstvo řeší alokátory paměti stále tápe a stále se hledají cesty.

A to nemluvím o co těžší je úkol zvládnout alokátor do multithreadového prostředí, kde alokační strategií se snadno dostanete do situace kdy zamykáním brzdíte program či thready tak intenzívně, že rychlost programu je slimák.

Že se tak hloupě zeptám, navíc trochu off topic ale
co je špatného na boehms gc?

Taky se blbě zeptám, ale v tom článku se tvrdí, že LOH se nekompaktí kvůli výkonu. Ale jaký výkon je potřeba pro přesun na stránky zarovnaných kusů virtuální paměti? Na to přece stačí změnit překladovou tabulku VM, není třeba nikam nic fyzicky přesouvat.

@11 To je oficiální zdůvodnění Microsoftu. Jde o přesuny "přeživších" objektů v rámci haldy, s virtuální pamětí to nemá nic společného.

Roger: Trochu pletete kompetence. Normální program běžně nemá pravomoci upravovat procesorové registry týkající se stránkování.

Od té doby co se vyrostlo z počítačového pravěku tu existuje operační systém, jehož hlavní úlohou je správa procesů a zdrojů počítače. A aby to operační systém mohl dělat, tak omezuje možnosti programů a nedovolí jim určité věci dělat.

Takže kdyby program začal upravovat registry VM, tak je z toho bordel na kolečkách a všechno se složí.

Pomíjím to, že ani změna překladových tabulek není zadarmo a výkon snižuje. Protože to, že změníte registr neznamená, že procesor v pozadí nemusí následně natahat další údaje v paměti, vyhodit předchozí z keše, načíst další data z paměti, uložit je to stínových registrů a keší a pak teprve jste tam kde jste chtěl být. A to vše stojí určitý čas, tedy snižuje výkon.

@13: Ehm, cože? Co brání OS při požadavku na přesun bloku paměti přesně odpovídajícímu fyzické stránce procesoru změnit jednoduše překladovou tabulku VM daného procesu? To je poměrně jednoduchá operace, procesor ani nemusí invalidovat cache, protože fyzická adresa je stále stejná.

@11: Pochopil jsem to tak, že tam tvrdí, že jim vznikají díry ve VM (na heapu). A že šoupat daty je drahá záležitost.

Možná to, že pokud je mi známo, tak operační systémy službu přesunu stránky na jinou virtuální adresu běžně nenabízejí. Stránkování totiž není povinnou součástí každého procesoru ani každého operačního systému.

Uvědomte si, že .NET není operační systém. Z hlediska operačního systému je .NET obyčejný program jako každý jiný.

Samozřejmě, že operační systém může teoreticky přesouvat stránky, ale uvědomte si ještě druhou věc. Operační systémy dneška z větší části ví o procesoru kulové. 99 %, ale spíše ještě více, kódu operačního systému je psáno multiplatformně. Jen maličká část je psána na konkrétní procesor. Dokonce i většina kódu operačního systému pracující se stránkami je multiplatformní, tedy nezávislá na procesoru.

K tomu je další věc.

Bylo by dobré se ve Vašich úvahách oprostit od toho, že existuje pouze x86 procesor a nic jiného. Jak Windows, tak Linux, tak unixy obecně, tak .NET virtuální mašina běží i na jiných systémech, než je x86 procesor.

Například jak operační systém na mobilním telefonu na ARM procesoru, který nemá sebemenší důvod stránkování vůbec obsahovat, bude přesouvat stránky jinak než kopírováním? A na těchto některých mobilech třeba .NET program běží také.

„Pochopil jsem to tak, že tam tvrdí, že jim vznikají díry ve VM (na heapu). A že šoupat daty je drahá záležitost.“

Jenomže šoupání daty potřebuje taky, abyste jim nešoupal s adresami pointerů jen tak mýrnix týrnix. Nemůžete prostě jen tak přesunout data na jinou adresu, i kdyby to hypoteticky šlo pomocí změny stránkovacích registrů, protože celý program může obsahovat odkazy na adresu, kterou mu změníte.

Změna a setřesení heapu (třeba i pomocí změny adresy stránek, připusťme to hypoteticky) musí nutně obsahovat opravy pointerů s adresami po celém programu.

Což občas virtuální mašiny Javy, nebo .NETu dělají. Takže tak jako tak musí obsah dat být prozkoumán a musí být jasno co je co. Nejde tedy při přesouvání bloků dat na heapu o prosté kopírování, ale také o analýzu dat samotných a opravy změněných adres pointerů, které budou sestřesením heapu změněny.

Data nejsou v programu samoúčelně, obsahují něco co program potřebuje. Neleží to tam jen tak ladem, a program samozřejmě na data odkazuje pointery, tedy adresami. Změnou adres heapu musíte opravit všechny pointery v programu, jinak jste program rozmetali atomovkou na cimpr camprt a zhroutí se.

Presouvat stranky po pameti jde, ale musi jit o namapovany soubor, nebo sdilenou pamet. Neni problem si otevrit libovolne dlouhe view od skoro libovolneho offsetu na libovolne neobsazene kolekci stranek. Ale neni to tak prakticke, presouvani je mozne jen o cele bloky stranek a se v praxi malokdy vyuzije

@7 Napsat alokator je sice veda, ale napsat specializovany alokator je jednoduche. Ve svem repertoaru mam alokatory ruzne, treb ClusterAlokator, ktery se hodi pro alokaci bloku stejne velikosti a mnohonasobne zrychluje praci s mapou. ted pracuji na shortAlloc, ktery je urcen pro kratkodobe alokace ruzne velkych objektu, napriklad stringu a jenz ma v idealnim pripade rychlost 1 akorat sem tam musi provest defragmentaci der se slozitosti n*log n. Nejrychlejsi je, pokud se alokuje extra pamet pro objekty na zasobniku, kdy dealokace probiha v opacnem poradi. Dal tam mam cacheAlloc, kde se dealokovana pamet uklada do cache aby byla rychle k dispozici, static allokator, ktery vytvari heap v zasobniku, smallalloc pro alokaci poli malych velikosti, kdy vetsi pole pak fallbackujou na std new a delete. Zalezi na pouziti,

Vsechny alokartory mam striktne instanciovatelne, coz umoznuje pouzivat je v MT prostredi bez nutnosti je zamykat ,pokud zamek resi ten objekt, ktery jej pouziva (treba vlastni mapa). Mit alokator pro kazdy vlakno separatne no problem. Ale tohle vsechno mi funguje bez STL. Prizpusobovat to STL znamena pokouset se letat s pristrizenymi kridly

@15: Samozřejmě že je .NET runtime obyčejný program. Ale i ty si mohou, jak ostatně bylo zmíněno v @17, namapovat (téměř) kamkoli třeba soubor nebo paměťový prostor jiného procesu.
K nenabízení - překopíruju si nějaké stránky o kus vedle (hezky zarovnaně). Co udělá kernel? Deduplikuje mi je, tj. nastaví jejich mapování na stejnou fyzickou adresu a zapne cow.
Stránkování samozřejmě nemůžete napsat, když ten procesor neznáte - minimálně potřebujete vědět, jak velké jsou fyzické stránky a jak funguje ochrana paměti, TLB a podobné záležitosti, bez toho žádnou správu nenapíšete. Ale jakmile máte tyhle věci hotové, je zbytek "brnkačka" a multiplatformní kód.
Jednak řešíme MS implementaci .NET runtime na Windows. A MMU/chráněný mód je, pokud mě pamět nešálí, povinný požadavek na Linux, a ačkoliv existují varianty bez MMU (uCLinux), ochrana paměti je jedna ze základních vlastností operačních systémů (sám jste se jí oháněl v @13). Navíc dnes už i "obyčejné" ARM11, používané v (hloupých) mobilech, MMU obsahují.

@16: Jenže SOH se kompaktí - a s ohledem na velikost tam ukládaných objektů bych čekal, že těch úprav bude mnohem víc. Nezáleží na velikosti objektů, ale na počtu referencí. Při GC stejně musíte projít stromy referencí, takže víte, co opravovat. A v managed kódu samozřejmě žádné pointery nemáte, takže odpadá ono procházení celé paměti a hádáni, co by tak mohl být ukazatel. Vždycky máte přehled o referencích na všechny objekty, to je tak nějak jeden ze smyslů celé té srandy. Takže tenhle argument nedává smysl.

Roger: „Stránkování samozřejmě nemůžete napsat, když ten procesor neznáte - minimálně potřebujete vědět, jak velké jsou fyzické stránky“

Ale houby s octem. Uvědomte si, že procesory nejsou náhodné generátory, které generují miliardu různých a naprosto odlišných velikostí stránek.

Taky si to můžete stanovit jako u Windows, kde se prostě rovnou rozhodli, že v rámci přenositelnosti vše bude zarovnávat na hranici 64 KB a vše se bude chovat, jako kdyby existovaly stránky o velikosti 64 KB.

---

„a jak funguje ochrana paměti, TLB a podobné záležitosti, bez toho žádnou správu nenapíšete.“

Na to napíšete maličný kernel v kernelu, který bude nabízet služby těm multiplatformním vrstvám většiny operačního systému.

Zkuste si občas představit, že tvůrci operačního systému nejsou blbci. A že se taky neučili jak věci očúrat a jak v rámci lenosti si ulehčit práci a získat tak volný čas na alkohol a návštěvy nevěstince.

---

„Jednak řešíme MS implementaci .NET runtime na Windows.“

To řešit můžete, ale nic to nemění na faktu, že v MS řeší běhovou mašinu .NETu pravděpodobně multiplatformně. Tedy tak aby na Windows ani x86 nezávisela. Kdyby to nedělali, špatně by dopadli.

---

„A MMU/chráněný mód je, pokud mě pamět nešálí, povinný požadavek na Linux, a ačkoliv existují varianty bez MMU (uCLinux)“

A jak vidíte, povinný požadavek na něco je něco co je k ničemu. Prostě jediný povinný požadavek je přizpůsobit se hw, na který implementujete.

---

„ochrana paměti je jedna ze základních vlastností operačních systémů“

Ovšem nikoli povinných vlastností procesorů či hw řešení počítačů. V řadě situací je dokonce zbytečné něco takového na hw úrovni mít.

---

„Navíc dnes už i "obyčejné" ARM11, používané v (hloupých) mobilech, MMU obsahují.“

V dodnes používané architektuře ARM žádná MMU není. Nejsou jen mobily.

---

„Jenže SOH se kompaktí - a s ohledem na velikost tam ukládaných objektů bych čekal, že těch úprav bude mnohem víc.“

Čekat sice můžete, ale otázka jestli to tak je. Já bych si tím jistý nebyl.

Celé je to prostě zoufalstvím všech tvůrců správců paměti, kdy se snažíte o kompromis a občas si trháte vlasy.

Oni se taky mohli setkat s nějakým problémem, jehož vyřešení by si vyžádali delší dobu.

Taky zapomínáte z hlediska teorie na praxi. Ti programátoři prostě mají nějaké termíny, manažeři jsou schopni jim dát výpověď, nebo snížit výplatu, když je nedodrží. A tak se prostě správce paměti naprogramuje do půlky toho co by chtěli naprogramovat – tak aby to v termínu daného managery prostě stihli.

To je obyčejný život. Programátoři nemají vždy možnost dotáhnout věci do konce a do dokonalosti, protože to je kapitalismus, neviditelná ruka trhu. A oni mají nad sebou biče a represe vedoucích a nadřízených, a občas musí vypustit něco méně dokonalého, ale musí to udělat v termínu.

Proč ve všech hledáte jen technické důvody?

---

„Nezáleží na velikosti objektů, ale na počtu referencí.“

Ha ha.

Chcete tedy říci, že kopírování jednoho terabajtu paměti je stejně rychlé jako jednoho bajtu paměti?

Asi ne, že. Proč mě ksakru zkoušíte jako malého kluka jestli se nachytám?

---

„Při GC stejně musíte projít stromy referencí, takže víte, co opravovat. A v managed kódu samozřejmě žádné pointery nemáte, takže odpadá ono procházení celé paměti a hádáni, co by tak mohl být ukazatel.“

No cement. Raději.

---

„Vždycky máte přehled o referencích na všechny objekty, to je tak nějak jeden ze smyslů celé té srandy. Takže tenhle argument nedává smysl.“

Ano, je dohledatelné co kde leží. Virtuální mašina to ví.

Všiml jsem si už dříve, že čas pro Vás neexistuje. Viz moje poznámka, že mě zkoušíte. Tak vězte, že vše se dělá v reálném čase a v paralelním prostředí. Něco to stojí – prostředky, mezi jinými je i čas. A zabírání času je posílání výkonu, tedy rychlosti programu do zadele.

Takže musíte se ve správci krotit a chovat se trochu připotentovaně a impotentně. Protože když to budete dělat na plné pecky, tak zase spotřebujete tolik runtime času, že uděláte ze všeho emulátor nejpomalejšího počítače.

---

Jinak dále už nebude reagovat. Jsou tu chytří lidé, a radost to tu číst. Diskuse je zajímavá, ale čas už nemám.

Oprava, mělo být

V dodnes používané architektuře ARM 7 žádná MMU není. Nejsou jen mobily.

@20: Negenerují jich miliardu, ale o tzv. "huge pages" jste už možná slyšel. V opačném případě doporučuji dostudovat (s různými velikostmi stránek se potkáte i na některých ARMech, a při dnešních velikostech virtuálních i fyzických adresových prostorů vás před obřími překladovými tabulkami nezachrání ani inverzní stránkování).
Zbytek asi opravdu nemá smysl komentovat, připadá mi, že jen uhýbáte a chrlíte kusy textu bez hlubší myšlenky (kolik VMM jste napsal, nebo aspoň viděl?). Škoda, z nějakého důvodu jsem od váš čekal trochu víc...

A pro zvídavé nadhazuji třeba vmsplice() - v páru je to docela zajímavá funkce (kdyby fungovalo SPLICE_F_MOVE).

trochu off topic ale
co je špatného na boehms gc?