Automatická správa paměti deterministicky

Reference counting je (zbytečně opomíjený) typ garbage collectoru, akorát většina programátorů v Javě či C# si dává rovnítko mezi garbage collectorem a tracingem (který ale trpí halting problemem a spotřebou paměti).

Kromě LLVM (Clang) a WinRT se tato technika běžně používá ve skriptech (např. Python, Ruby, PHP), i když tam se většinou neřeší cykly. Od C++11 je tohle již součástí standardu (std::shared_ptr a std::weak_ptr), předtím byla součástí Boostu. V C++ je sice nutné ty ukazatele obalovat ručně, ale správný typedef (resp. using) tohle dokáže dobře skrýt.

@1 Tak jest. Tato technika je dost rozšířená, v clangu (je to záležitost frontendu, ne LLVM) a WinRT je akorát překladačem skryta a programátor se tak o paměť (téměř) nemusí starat.

Radim se mezi pseudoexperty kteri maji na vec pseudoodborne nazory. Clanek i reakce vyznivaji jako "GC (ve smyslu tracing GCs) akorat zerou pamet, reference counting je stejne dobry, deterministicky a jediny (maly) problem jsou cyklicke reference => full GC je dneska nepotrebny". Rad bych vyjadril svuj pseudonazor, ktery neni - jak asi tusite - zcela souhlasny.

1) "...téměř neexistují úniky paměti - memory leaks" - nesouhlasim tak zcela. Zalezi jak definujete memory leak. Pokud je to "pamet, ktera je referencovatelna" pak ano. Pokud je to "pamet, ktere je alokovana a program ji uz nepouziva", pak ani GC nezaruci, ze zadne memory leaks nejsou...

2) Reference counting ma i jine stinne stranky nez cyklicke reference. Kazde prirazeni znamena 2x load-inc/dec-store navic. Alokace/Dealokace je take relativne draha (predpokladam pouziti podobneho alokatoru jako je malloc. Navic dochazi k fragmentaci pameti. Naproti u modernich "plnotucnych" GC je alokace inkrement pointeru. Dealokace smeti je zadarmo, co stoji cas a energii je to co prezije :-) Pochopitelne, prirazeni je obycejny store ve vsech pripadech. Problem s fragmentaci temer odpada v novych generacich, v tech starsich neni zas takovy problem udelat compact. Neni to tak cernobile.

3) Ze plnotucny GC implikuje velkou spotrebu pameti je do jiste miry povera zavinena Javou. Ano, Java zere hodne. Delam na systemu/VM co ma plnotucny GC (neni to ani JVM ani CLR :-), pod tim beha pomerne velke IDE (rekneme neco podobneho NB/Eclipse). Po tydnu behu IDE (pocitac jen uspavam :-) je bezna velikost okupovane pameti kolem 100-150MB (vyvijene aplikace bezi v ramci stejne VM jako IDE). Jakmile v ramci stejne VM pustim hello world v Jave (za pomoci OpenJDK rt.jar) - velikost alokovane pameti vzroste o cca 70-100MB - GC se pouziva stale stejny, objektovy model je stejny. Muj zaver z toho je, ze mozna v Java neni GC vykrik vedy, ale hodne dela i zakladni knihovna a GC ve spotrebe pameti muze byt i v nevine.

Kazda strana ma dve mince :-)

P.S.: Problem s neuvolnovanou pameti na serveru s kombinaci Apache/WSGI/Python resim asi rok. Neuspesne :-)

@3 Zkusím reagovat stručně:
1) Pochopitelně, nakonec je stejně na programátorovi, aby nikde paměť neunikala. GC nebo RC jen pomáhají.
2) Náklady na přiřazení jsou u GC a RC zhruba stejné. Navíc, jak jsem psal, ARC (jak to je u WinRT nevím) nakonec nepotřebnou manipulaci s čítačem referencí odstraňuje během optimalizace, a to poměrně chytře (mají velmi dobrý statický analyzátor). Fragmentaci by měl řešit alokátor, v C++ je většinou poněkud sofistikovanější než malloc/free. LLVM má podobný alokátor, jaký popsal Alexandrescu ve své "legendární" knize o moderním C++.
3) Mám špatné zkušenosti s GC na mobilních telefon (Androidy, Blackberry i iOS - ano, i na iOS je, i když skrytý). Na počítačích jej také běžně používám (hlavně Javu na serverech). To ale nic nemění na tom, že na mobil dá GC je trouba.

Osobně se mi zamlouvá přístup Microsoftu poskytnout platformu pro tablety (možná bude Windows 8 i na telefonech) napsanou v C++ a k ní rozhraní pro Javascript. Pár UI widgetů v JS spotřebu paměti nijak neovlivní, ale většina systému jede nativně (a bez GC). Stejně to ostatně má nějaký ten pátek i webOS.

U GC je problém hlavně s přerušením práce programu po dobu GC. Samozřejmě existují concurrent a background implementace, ale i ty občas na chvíli zablokují běžící aplikaci. A to se zjevně MS nelíbilo.
Dalším problémem je ta vyšší spotřeba paměti. Na zařízeních s omezeným množstvím paměti to znamená vynutit GC, když paměť dochází, což vede k výše zmíněnému problému s plynulostí běhu aplikace.
MS použil zjevné řešení: výkonově kritické komponenty se píšou ve WinRT, kde se GC nepoužívá. Tyhle komponenty se pak používají z .NETu. Aplikace psaná v .NETu se holt může na krátkou chvíli seknout. Když to moc vadí, napíšete ji (nebo její kritickou část) ve WinRT.

[3] Ad 2 - vsechno prece neni treba mit v heapu (a spravovane nejakym GC ci reference countingem), lokalni docasne objekty muzu vyrobit na stacku. Co se tyce alokace, mam pocit, ze gcc nema pouze primitivni malloc alokator, ale ze pamet nevraci hned a snazi se o jeji znovupouziti. Ale to je mozna jenom muj blud.

[3]
1) Load-inc/dec-store lze dobře optimalizovat, pokud to podporuje hardware (dneska to umí už snad všechno), a je potom prakticky nezměřitelný ve srovnání se samotným tracingem (tou částí, kdy probíhá hledání smetí). Také se dá výrazně optimalizovat buď zavedením move sématiky (v C++ opět od C++11) nebo vhodným optimalizátorem (to je asi to, co má WinRT).

2) Alokace i dealokace v dynamické paměti jsou stejné u jakéhokoliv přístupu, implementuje to totiž alokátor (malloc má problémy s paralelním výkonem kvůli globálnímu zámku, ale za to nemůže reference counting). Samotné ukazatele se ve většině implementací (a to jak u tracingu tak u reference countingu) alokují na zásobníku a taková alokace i dealokace je jenom posun pointeru (u reference countingu potom následuje ještě inc/dec). Reference counting neumožňuje provést compact, ale moderní alokátory jej stejně nepotřebují.

3) Tracing vždycky žere víc než reference counting. To je prostě daň za to, že dokáže vyhledávat cykly a díky tomu nepotřebuje slabé ukazatele.

@6 Pokud je někde GC, tak ani "stack semantics" (jak to nazývá Microsoft) neruší objekty deterministicky a vše je na haldě. Vlastně se jedná jen o skryté IDisposable.

[5] Mel bych dotaz, jake implicitni vyhody ma pocitani referenci primo v objektu (ala COM) misto ve vhodnem wrapperu (shared_ptr). Ja preferuju druhy zpusob uz z duvodu rozdelovani ukolu - nevim, proc by se objekt mel starat o to, zda ho nekdo pouziva.

[8] Jo, proto bych preferoval citani referenci, idealne wrapperem (shared_ptr) :-) Ale koukal jsem, ze treba Java ma tohle pro lokalni promenne alespon trochu zoptimalizovane (uklada je do nejakeho pole).

@9 Typová konzistence. Navíc to usnadňuje práci překladače.

@10 WinRT mimochodem také nemá objekty na zásobníku (ani ObjC). Když v C++/CX nepoužiju ^, jediný rozdíl je přístup přes tečku místo -> (navíc v tom teď má Microsoft bug, ale je to jen preview).

[11] Jaka konzistence? Jako ze je vsechno IUnknown?

@13 Ne. Není rozdíl mezi T* a shared_ptr (to je velká výhoda pro optimalizaci kódu).

[14] Ted jsem se ztratil zcela.

@15 Když mám shared_ptr, překladač neví, kdy aktualizaci čítače ignorovat (optimalizovat). Pokud je RC součástí syntaxe, může kompilátor podle vlastního uvážení kusy kódu vynechat (když tím nic nepokazí). U ObjC je důvodem, že to není C++, ale C, takže chybí přetěžování operátorů.

[4-2] Souhlasim, staticky optimalizatos muze pomoci, ale dost zalezi na charakteru kodu - jak velke jsou basic blocky, apod. Fragmentaci lze minimalizovat, ale cim vic se clovek snazi, tim dele mu to trva.
[4-3] Mozna, telefony jdou mimo me. Ale myslim, ze to je otazka par let, nez budou natolik silne, ze GC nebude to co zdrzuje (podobne jako to dnes neni na velkch pocitacich) Ja mam naopak spatne zkusenosti s cimkoli co nema GC...

[6] Pokud chceme mit objektovy jazyk s podporou polymorfismu, obavam se ze je nutne mit temer vsechno na halde (s vyjimkou tzv. immediate objektu - ty ale ani pro GC neznamenaji zadny problem/zdrzeni). Alternativa je delat analyzu v runtime a nasledne rekompilovat kod. Rezie tohoto reseni je srovnatelna, ne-li vyssi nez GC. O tom, jak se alokuje pamet nerozhodije prekladac, ale knihovna...

[7-2] Jisteze alokaci implementuje alokator. Vzdycky je tam nejaky mmap/brk/sbrk - alespon obcas. Rozdil je v tom, co se deje dal :-)

chtel jsem jen ukazat druhou stranku veci aby to nevyznelo jednostranne. V teto teoreticke rovine o tom asi nema cenu dale diskutovat. Myslim, ze az si kazdy znas napise svuj vlastni memory management a bude ho chvili pouzivat, bude takhle diskuze mnohem zajimavejsi :-)

[16] Záleží na implementaci a na schopnostech jazyka. Boost to neuměl, protože C++ neumělo move, současná implementace std::shared_ptr snad již inc/dec nedělá, když se použije jenom jeden ukazatel.

[17] Co se děje po naalokování paměti? Zavolá se konstruktor a tím to většinou končí. Pokud reference counting není optimalizovaný pro move, tak si ještě zvedne jedno číslo, stejně jako tracking si může uložit, kde se nachází nový ukazatel a kam ukazuje. A to je fakt vše. Co by se ještě mělo dít?

Memory management jsem psal jako náhradu za malloc, používal jsem mmap místo sbrk (sbrk např. nedokáže uvolnit paměť, když vznikne alokace na konci přidělené paměti, což je častější, než se může zdát) a řešil sdílení paměti mezi procesy. A opravdu mě nenapadá, co dalšího se děje.

K tomu RC a k pomalosti přičítání. Opět tu vidím problém v tom, že to někdo řeší na úrovni systému. Já třeba RC implementuju zásadně jako MT unsafe, právě kvůli tomu, že InterlockedIn­crement a InterlockedDe­crement stojí nějaký nemalý výkon. Programátor má také k dispozici i MT Safe varianty, ale ty musí specifikovat explicitně. Přepínání mezi MT Safe a MT Unsafe přitom řeší pointer, nikoliv vlastní objekt, takže výběr správného pointeru je podle použití.

Používání MT Unsafe má hlavní smysl v tom, že sdílení objektů mezi vlákny zas není tak časté. Velice častěji má objekt, nebo objektovou strukturu na starost jedno vlákno, ostatní jen do něj přistupují a ti použivají klasické pointery. U objektů, které se umí klonovat (a u RC-Stringů) pak existuje metoda isolate(), která provádí fork objektu, pokud má ref.count větší než jedna. To je právě určeno pro vlákna, kde se simuluje takový malý fork objektu. Pak už MT Safe countery nemají smysl.

Stejně tak většina mých alokátorů je MT Unsafe, právě proto, že se počítá, že každé vlákno bude mít vlastní instanci. Mám změřeno, že výkon takových aplikací, třeba na mapách, spojových seznamech a podobně , je výrazně vyšší, než klasické STL + malloc

Jinak kromě RC použivám ke sdílení pointerů ještě kruhový seznam, kdy se pointery propojí do kruhu. Každá kopie pointeru přidá sám sebe do spojového seznamu. Kruh je jednosměrně orientovaný.

Výhody: Objekt na to nemusí být připraven, Ukazatel nemusí alokovat counter. Chytrý ukazatel zabere pouze 2x více než normální ukazatel, snadná implementace přesměrování, kdy mohu změnit adresu u všech ukazatelů současně. Hodí se i na sdílení různých neukazujících objektů. jako třeba souborové deskriptory, handly oken a podobně.

Nevýhody: Pomalé odebírání ukazatelů, pokud je jich hodně (musí se oběhnout kruh), prakticky neřešitelný MT Safe sdílení.

Vemli často to používám na obyčejné přenášení pointerů ve výsledku funkce abych měl jistotu, že si pointer někdo vyzvedl.

Největší výhoda moving-mark-and-sweep GC jako má Java je, že funguje ve vícevláknových programech. U počítání referencí musí být buď všechny inkrementace/de­krementace zamčené (což je nezanedbatelná režie), nebo musí programátor zatraceně dobře vědět, co a jak se mezi vlákny sdílí (jak píše ondra.novacisko).

Je pravda, že WinRT se k RC docela hodí, protože místo vláknovosti upřednostňuje asynchronní API. Ale stejně by mě zajímalo, co se stane, když aplikace vytvoří nové vlákno.

[22] To není pravda, zamykat vůči GC musíte při každém přístupu k objektu, aby ten objekt GC pod rukama vláknum nepřesouval. Já jsem se pokoušel psát GC v C++, za pomocí chytrých ukazatelů a vlastních alokátorů (nic jiného k tomu není potreba) a takovách konfliktů je tam hafo. Každý přístup k objektu znamená, že se někde minimálně 1x udělá InterlockedCom­pareExchange, což je minimální varianta SpinLocku.

@22 To je dobrá poznámka. Kód ve WinRT typicky běží v jednom vláknu a systémová volání asynchronně. Objekty ve WinRT mají dva čítače, jeden pro hlavní vlákno a druhý zamykatelný. Když totiž předám objekt systémové metodě, "můj" čítač následně klesne na nulu, ale k tomu systémovému nemám přístup. Systém si pak objekt zlikviduje sám. Pokud vytvořím své nové vlákno, začne se používat zamykatelný čítač.

[23] mark-and-sweep GC taky bývá stop-the-world. Tedy zastaví celou aplikaci, proleze ukazatele, uvolní paměť, defragmentuje paměť (popřesouvá objekty) a pak může aktualizovat pointery a zase pustit aplikaci. Nevím jestli java nepoužívá pointery přes nějakou tabulku (pak stačí aktualizovat ji), ale to na věci nic nemění.

Takže si opravdu myslím, že není potřeba zamykat pořád. Ovšem platí se za to tím zastavením aplikace:-).

[24] Aha, dva čítače, díky. Já si myslím, že je to cesta správným směrem. Vícevláknové aplikace jsou peklo. Lepší je mít jedno vlákno, asynchronní API a paralelní věci dělat v odděleném paměťovém (nebo objektovém) prostoru.

@25 Tak nějak funguje NodeJS. Microsoft teď používá stejné paradigma. Také mi to připadá rozumné. Apple má v Cocoa něco velmi podobného např. pro síťovou komunikaci.