Scheme snadno a rychle - 0. sprava pameti

28.12.2006 22:38 | Přečteno: 1739× | Programování

rad bych zde zacal maly tutorialek o tom jak si napsat interpetr programovaciho jazyka. kazdy spravny programator, by si mel za zivot urcite nejaky programovaci jazyk napsat. vite, jaky to dela dojem na zenske, kdyz je balite se slovy: "nechcete, abych vas uvedl do taju sveho interpretru?" jelikoz z urcitych duvodu pisu dialekt schemu, tak bych se o nektere poznatky rad podelil a jelikoz se to vleze na par set radku nebude to ani tezke. berte to spis jako inspiraci, nez nejake fundamentalni cteni.

0. Sprava pameti

vetsina clanku o jazycich zacina popisem gramatiky. zacnu trosku netradicni modelem prace s pameti. hodne zasadnim rysem jazyka byva jak pracuje s pameti. sice se muze zdat, ze automaticka sprava pameti je domenou trendy jazyku jako java nebo c# a opravdovi muzi ji nepouzivaji, ale garbage collector je tu uz nekdy od konce 50. let, kdy byl vymyslen pro lisp.

0.1. Pocitani odkazu

jednoduchy model automaticke spravy pameti vychazi z myslenky, ze kazdy kousek pameti si u sebe drzi pocet odkazu (pocitadlo) na dany blok v pameti. a pokud je vytvoren odkaz na dane misto, zvysi se pocitadlo, pokud je odkaz zrusen pocitadlo se snizi. kdyz pocet odkazu spadne na 0, je pamet uvolnena. tento princip je pouzity treba ve smart pointrech.

krasna je teorie, oskliva je praxe. tento pristup ma velkou radu neduhu -- at uz je to rezije, kterou spotrebuje pocitadlo na sve ulozeni a operace scitani/odecitani taky nejaky cas zaberou. to nemluvim o tom, ze kdyz se jedna o vice vlaknovou aplikaci, je nutne, aby pocitadlo bylo chranene nejakym mutexem a to taky neco stoji. nejhorsi na tom je, ze pocitani odkazu nemusi vubec fungovat a muze delat osklive memory-leaky kvuli cyklickym odkazum. pocitani odkazu, i pres to, ze jde snadno pouzit a implementovat, se v praxi moc nepouziva, co vim, tak jej pouziva visual basic 6.0 a delphi na nektere typy datovych struktur.

0.2. Sber odpadku

bezne garbage collectory vychazi opet z myslenky, ze pamet se nebude pouzivat (a tudiz je uvolnitelna) v pripade, ze na ni nevede odkaz z nejakeho jineho kousku pameti. z teoretickeho pohledu je pamet rozdelena na kousky, ktere jsou provazany jako orientovany graf skladajici se z nekolika komponent. jenomze jak poznat, ktere casti jsou dostupne a ktere uz ne? neni to tezke. dostupne casti pameti jsou ty, ktere jsou odkazovany od nekud ze zasobniku nebo ze staticke promenne.

garbage collectoru je vicero druhu a jednotlive rysy se mezi sebou kombinuji. ale to je na uplne jiny clanek. napsat slusny garbage collector je docela veda. osvedcil se mne boehmuv konzervativni garbage collector, ktery jde velice snadno zaclenit do stavajicich c/c++ aplikaci. nekteri o nem rikaji, ze je pomaly, ale z open source collectoru je jeden z nejrychlejsi, podporuje slusnou radku platforem (vcetne amd64, coz je u rady collectoru problem) a ma vynikajici vykon ve vicevlaknovych aplikacich. nasel jsem par clanku, ze v ibm maji neco lepsiho... ale zdrojaky nejak nedali k dispozici. kdyby nekdo vedel o necem podobnem, dejte mne vedet.

pouzivani je proste, jak bulharska stripterka: staci linkovat proti knihovne "gc", pridat na zacatek kazdeho souboru "#include <gc/gc.h>" a pouzit nekterou funkci pro alokaci.

• GC_MALLOC(x) -- je obdobou bezneho mallocu, jedna se o nejobecnejsi funkci a pokud opravdu provedete v stavajici aplikaci nahradu mallocu za GC_MALLOC a odstraneni volani free(), mela by aplikace bezet
• GC_MALLOC_ATOMIC(x) -- alokuje pamet stejne jako predchozi funkce (potazmo makro), jenom s tim rozdilem ze dava collector napovedu, ze dana oblast neobsahuje odkaz do jine oblasti pameti (napr. pole doublu, intu, atp.), teoreticky by to melo zrychlit beh, ale osobne jsem moc velky rozdil nevidel

pokud aplikace ma bezet ve vicevlaknovem prostredi je nutne v souborech pouzivajici neco z knihovny pthread, pred inkluzi gc.h deklarovat makro GC_THREADS a collector nektere funkce obali svymi.

co je ale hezka vec, boehmuv kolektor se umi optimalizovat, aby kazde vlakno si alokovalo data zvlast a nemuselo dochazet k zamykani. staci pouzivat funkci GC_local_alloc(x), popr. deklarovat makro GC_REDIRECT_TO_LOCAL a to prevede vsechny volani GC_MALLOC na "optimalizovane". ma to ale jednu neprijemnou vlastnost. collector si uklada informace pomoci pthread_set_specfic, takze pokud je funkce volajici GC_local_alloc zavolana primo z procesu a ne z vlakna, zacne se chovat nepredvidatelne (teda segfaultuje). ale to jde resit, ze se v procesu spusti samostatne vlakno a predaji se mu jenom argumenty aplikace. (no jo, thready jsou v unixu cizorody element a prace s nimi neni tak komfortni jako treba ve windows)

pro vetsi nahled do problematiky garbage collectoru muzu doporucit stranky pana boehma, ktery vyvraci nektere myty a pak velice pekne pocteni http://www.sidhe.org/~dan/blog/archives/000200.html, kde jsou collectory popsane mnohem srozumitelneji nez ode me.        

Komentáře

[Kyosuke]

Nikdy bych nevěřil, že je možné o tak krásném jazyku psát tak odporným jazykem.

[deda.jabko]

a bude hur! zatim jsem o scheme nenapsal ani radku... ;-]

ale jinak, co vam vadi? absence velkych/malych znaku, carky tam kde nemaji byt, amerikanismy? mozna se pro priste polepsim....

[Käyttäjä 11133]

Mi osobně pouze velké a malé písmena

[Kyosuke]

Ano, to je poznat už z toho nepřízvučného osobního zájmena v přízvučném postavení.

[Kyosuke]

BTW, ostraváci říkají „velké a malé písmena“?

[Käyttäjä 11133]

jo :-p

[Kyosuke]

Jo, tohle a pak třeba ještě „režije“ a podobně. BTW, slyšel jsem, že coding standards značně zlepšují čitelnost a udržovatelnost kódu, tak v češtině programuju podle best practices.

[helemesecotonese]

Jee, super! Tak tady na to se moooc tesim! Uz dlouho potrebuju napsat malicky interpret Scheme v intepretovanem jazyce. Doufam, ze se dozvim jak na to. Programovat trochu umim, ale nevystudoval jsem technickou skolu a tak mam problemy to zalgoritmizovat...

PS: jakym jazykem pisete je mi narozdil od kolegy fuk kdyz prilozite zdrojak micro-scheme (zakladni funkcionalita) treba v ANSI C, budu blahem chrochtat traktaty...

[Kyosuke]

Nejlepší je psát interpret Scheme ve Scheme a úplně nejlíp Tě to naučí pánové s fezy, kouzelnickými klobouky a jinými pokrývkami hlavy.

[deda.jabko]

on se z didaktickych ucelu rad implementuje scheme ve schemu, treba tady http://www.federated.com/~jim/schintro-v14/schintro_toc.html, ale neni to kompletni... (chybi treba call/cc... to treba ten "muj" bude umet, hec!) ale jako inspirace hezke, jsou tam popsany a vysvetleny nektereny terminy... ktere tak dobre nepopisu... :-/

kdyby vas to zajimalo, tak implementace bude/je v ansi c.

[helemesecotonese]

Super! To by me teda moc zajimalo. Doufam, ze to bude krasny a cisty kod. Uz se tesim.

[Lukáš Rýdlo]

> ale nevystudoval jsem technickou skolu a tak mam problemy to zalgoritmizovat

A jak to souvisí s technickou školou (ne, vůbec se nenavážím do obsahu výuky na našem ústavu ).

[Ladicek]

Pokud vím, tak počítání referencí se používá třeba v Perlu.

Jinak, líbí se mi (čistě na teoretické rovině) Io. Garbage collector je pár set řádek v Céčku, které se honosí označeními non-moving, tri-color, write-barrier, generational nebo incremental, jimž příliš nerozumím, ale strašlivě mne fascinují

[podlesh]

No, jako úplné základy dobré. O reference counting prakticky ani nemá smysl mluvit, rozhodně pak nemá smysl ho používat.

K té druhé části - konzervativní GC pro C jsou zajímavé, ale jak to souvisí s implementaci Scheme? Jeho použití se může zdát snadnější, ale troufám si říci že ve výsledku se žádná práce neušetří a problémy přibydou (ve srovnání s vlastním GC).

[deda.jabko]

reference counting jsem zminil, protoze presto ze je hodne nedokonaly v praxi se stale pouziva, at uz ve zminenych jazycich, ci aplikacich se smart pointry (a ze tech je). a v implementaci schemu jde docela snadno pouzit (vyzkouseno), ale za cenu degradace rychlosti.

pro spravu pameti jsem zvolil boehmuv gc, protoze odpada samotna implementace garbage collectoru a tudiz napsat interpretr je snadnejsi a rychlejsi ;-] je to proste jak ve vetsine soucasnych jazyku -- alokuj si co potrebujes a o nic vic se nestarej.

mohl byste se prosim rozepsat o potencialnich problemech s pouzitim konzervativniho gc, pred vlastnim? (pominu-li skutecnost, ze konzervativni gc se obcas netrefi)

btw. boehmuv gc pouziva mj. velmi povedena a robustni implementace -- mzscheme.

[podlesh]

reference counting jsem zminil, protoze presto ze je hodne nedokonaly v praxi se stale pouziva, at uz ve zminenych jazycich, ci aplikacich se smart pointry (a ze tech je). a v implementaci schemu jde docela snadno pouzit (vyzkouseno), ale za cenu degradace rychlosti.

V podstatě není důvod proč ho používat jinak než jako nouzovou nadstavbu nad existující správou paměti (to je případ právě těch smart pointerů).

pro spravu pameti jsem zvolil boehmuv gc, protoze odpada samotna implementace garbage collectoru a tudiz napsat interpretr je snadnejsi a rychlejsi ;-] je to proste jak ve vetsine soucasnych jazyku -- alokuj si co potrebujes a o nic vic se nestarej.

To je právě otázka...

mohl byste se prosim rozepsat o potencialnich problemech s pouzitim konzervativniho gc, pred vlastnim? (pominu-li skutecnost, ze konzervativni gc se obcas netrefi)

Nejde ani tak o problémy, jako spíše že není žádný prostor pro vylepšení a přizpůsobení. Vlastní GC umožňuje například řešit fragmentaci paměti nebo může být i plně paralelní, atd. To ale závisí na tom, jaké jsou s tím interpreterem plány.

Konzervativní C garbage collector má ale jednu velkou výhodu - zjednoduší psaní samotného interpreteru.

[deda.jabko]

tak to jsem rad, ze se shodneme.

ono, napsat dobry gc (i treba specializovany) je docela veda a mimo rozsah tohoto clanku. napr. ja ho provozuji v paralelnim prostredi, kde uz to je uplna veda a co jsem tak studoval materialy, tak pan boehm a jeho kolegove jsou v tom docela daleko a hlavne publikuji konkretni reseni.

[Stanislav Bohm]

Pocitani referenci, pokud si to dobre pamatuji, pouziva take Python. Navic k tomu pridava nejaky algoritmus na detekci a rozbijeni zacyklenych referenci.

[freshmouse]

Mě strašně fascinuje tenhle uživatel:

Deda Jabko, blog: blog co se jmenuje "každý den jinak"

A ještě ta patička o ukradených zdrojácích Debianu! To je prostě nářez.

[Kyosuke]

Ty mi povídej o patičkách.

[freshmouse]

Cože?

[Kyosuke]

„Až koffr dostane Nobelovku, ožeru se jako prase.“

[freshmouse]

No jo. Zrovna jsem uvažoval o znovunasazení svojí starší patičky (Prosíme, nevkládejte si do úst stolici nebo její části.), ale ta už je prý okoukaná.

[Kyosuke]

Hmm, co mám říkat já? Moje patička je okoukaná skoro tři čtvrtě tisíciletí.

[Billy The Pilgrim]

Zdrojaky Debianu jsou dobry hlod, to uznavam. Ale "kazdy den jinak" je i nazev kapely (hrajou tusim ponejvic s Redlem)

[deda.jabko]

jojo, presne tak, bohuzel s redlem uz dohrali... kazdopadne to kouzlo rekurze (resp. nekonecne smycky) je uzasne a ta hudba je taky hodne dobra.

[Jary]

Rekurze? Smyčka? Jsem slepý nebo málo inteligentní?

[deda.jabko]

v tom je to kouzlo ;-]

[Lukáš Rýdlo]

Super článek. Možná si taky napíšu nějaký interpretr vlastního jazyka, abych mohl oslňovat slečny slovy "nechcete, abych vas uvedl do taju sveho interpretru?" (a pak se divím, proč se mě lidi, kteří mě neznají, ptají s despektem "Nejseš ty náhodou informatik?" )