Jucerasnje Elinkino predavanje o heap memoriji i pokazivacima u Pascalu pratilo je relativno malo ljudi tako da nekima na listi nece biti bas sasvim jasno zasto pisem ovo sto pisem, ali ne smeta...

HEAP

Goran Paulin

Heap je jedna od onih stvari koje se uvuku u informatiku zato jer se svojevremeno cini dobrom idejom, a onda se toliko iskomplicira teoretiziranjem da uskoro svima postane kristalno jasno o cemu je rijec (obzirom da je objasnjeno na sve moguce nacina na koje se moze objasniti), a sam pojam se zacementira do te mjere da u najmanju ruku ispada kako bez njega ne bi bilo ni danasnje informatike.

Yeah, right.

Prvo sto mi pada na pamet je analogija s imenovanjem varijabli tipa integer slovima "i", "j"... Ovome naizgled nije ovdje mjesto, ali dobar dio nastavnika informatike takvo imenovanje smatra Bozjom zapovjedi. Kako nas matematicka notacija od malih nogu nauci baratanju sa "x", "y" i "z" - eto problema. Tesko je dobiti smislen odgovor zasto se koriste bas "i", "j" i druzina usprkos tome sto je odgovor zapravo jednoznacan - Fortranova konvencija. Ako varijabli nije specificiran tip (integer ili real), ona po defaultu postaju integer ukoliko joj je prvo slovo u rasponu od "i" do "n". Sve drugo je real. Dakle, kad se u skoli bude (ponovo) ucio Fortran na vama je da se ovoga i drzite. Dok god prve korake radite u BASICu varijable mozete nazivati i "gefufna". O mnemonicima i razumijevanju sadrzaja varijabli prema imenu - nekom drugom prilikom.

Kakve veze ovo ima s heapom? I jedno i drugo se uzima "as is". O tome se ne raspravlja.

Za bolje razumijevanje problematike kljucan je trenutak do kojeg smo jucer dosli u trenutku kad je Damir konkretizirao problem uzaludnosti koristenja heapa, na kojem sam inzistirao, spomenuvsi dvije stvari - "Pascal" i "640K".

Racunala nisu nikad cula za heap. Mozda su i cula, ali im ne znaci puno u zivotu. Culi su za pojam memorije, za cache i, u najboljem slucaju, za stack. To znaci da je CPU naseg vremena u stanju samostalno razlikovati ta tri termina. Ne treba mu nikakv Wirth koji ce ga uvjeravati da tu postoji jos gomila stvari kojih nije ni svjestan.

Cache nas ovom prilikom ne zanima obzirom da ni stack ni heap nemaju puno veze s njim u daljnjem kontekstu.

Govoreci o stacku dodirujemo jedinu konkretnu granicu konvencionalne memorije. Onu kojoj je Motorola odlucila posvetiti osmi adresni registar (a7) svojih CISC procesora. Spominjem Motorolu jer mi je daleko bliza od Intela. Ljubitelji Intela, slobodno se nadovezite.

Dakle, tipican procesor serije MC680x0 svjestan je postojanja stacka i obilato ga koristi. Postojanja heapa nije svjestan. Na malo visem nivou, tamo gdje jedan od likova nase bajke postaje i sam OS, stack dobiva novo znacenje - o njemu se brine OS. Stack je elementarno jednostavan dok god se radi o OSu koji nije cuo za multitasking. Onaj koji ima prefix "RT" (kao real-time) stack tretira puno dinamicnije.

Ni OS nije cuo za heap. Pod uvjetom da ne zelimo "lupati po metalu" i zamarati se mnemonicima, koristit cemo neki programski jezik kao sto je, gle, gle - Pascal. Wirth se nikada nije uspio dogovoriti sam sa sobom kome zeli koga podrediti - racunalo korisniku, korisnika OSu, OS racunalu, OS kompajleru, korisnika kompajleru... zato je tijekom godina eksperimentirao i napisao Pascal, Modulu, Oberon... da spomenemo samo nesto iz njegove radionice. Svaki put se sve vise priblizio onome sto danas nazivamo objektno programiranje, a vec sa Pascalom odlucio je potuci legendarni quote Billa Gatesa kako bi "640K trebalo biti dovoljno za sve".

Wirth je znao da nije. U biti, znao je i Gates. Jedan je uveo virtualnu memoriju, drugi heap. Virtualna memorija je prilicno samoobjasnjiva. To je memorija koju zapravo nemamo. Heap nije daleko od toga, ali zapravo je rijec o nacinu na koji se Pascal brine za ono za sto bi se inace morali pobrinuti sami.

Ovdje mozemo vuci paralele s vizualnim alatima i nacinima na koji se brinu za GUI i interakciju s istim. S heapom radimo isto to - s memorijom.

Ako u prostor od 21 memorijske jedinice moramo strpati 42 podatka od po jedne memorijske jedinice, ne moramo se pitati hoce li "stati". Nece, naravno, barem ne svi istovremeno, ali ce ih heap preuzeti onoliko koliko mu Pascal dozvoli, obraditi ih i proslijediti dalje. Naravno, uvijek ostaje kljucni problem u kojem program ne smije previse sarati po memoriji u smislu "sad cu obraditi jedan podatak na lokaciji 1, a onda idem malo na 38 pa cu se vratiti na 2". Istina, radilo bi i tako, ali otprilike 21 puta sporije.

Heapu nije puno trebalo da se useli u sve vise programske jezike, a Jobs i njegova vizija MacOSa posluzila se preventivnim alokacijama memorije u kojoj se nekako naslo i mjesta za heap. Obzirom da, koliko mi je poznato, ovdje nitko ne koristi Maca, a jos manje programira na njemu, to cemo preskociti.

Problem heapa? Problem lezi u tome sto kompajler mora pretpostaviti sto vi zapravo hocete. Obzirom da kompajleri ne citaju misli, heap vise uzima nego sto daje. Naime, on savrseno funkcionira ako rjesavamo zadatak u Pascalu i ako nismo u zivotu alocirali memoriju. Medjutim, koliko puta mislite da cete imati problem alokacije, primjerice, polja velicine 1000 integera kojeg cete rijetko kad popuniti preko polovice? Tu suvereno vlada heap.

U stvarnom zivotu ne vrijedi pretpostavljati. Intuicija, kao sto se moglo vidjeti iz traktata o dinamickom programiranju, nema puno zajednickog s racunalima. Doista mi ne znaci puno ako rezerviram 5 polja za integer ako nisam siguran hoce li korisnik upisati nesto sto stane u tri ili cetiri polja. Naravno, glupo je uvijek pitati korisnika koliko on zeli alocirati memoriju jer vjerojatno ne zna ni sto ga pitamo, pogotovo ako s druge strane ekrana sjedi Stefica iz urudzbenog.

U takvim situacijama potrebno je svladati onaj dinamicki dio u programiranju koji nema veze sa samim dinamickim programiranjem, a odnosi se, izmedju ostalog, na dinamicko koristenje memorije. U doba vladavine MS-DOSa to nije bilo nesto na cemu su se lomila koplja, ali svaki multitasking OS to ima zapisano kao imperativ. Zamislite da N malih programcica negdje nesto radi i svaki od njih rezervira "za svaki slucaj" 640K za nekakav heap. Tajvanci bi procvali od srece.

Tipican primjer problematike alokacije memorije i izbjegavanja heapa je ucitavanje datoteke. Datoteka je velicine N bytova i nema nacina na koji mozemo preventivno procjeniti njenu velicinu te alocirati nekekav prostor u memoriji koji ce zauvijek biti dostatan. Tu pada u vodu teorija po kojoj program svoje izvrsavanje zapocinje alociranjem mjesta za varijable (to su one iste varijable koje pisu na pocetku programa "da ih lakse nadje"). Automatsko alociranje gubi smisao iz dva razloga - prvi je taj sto ne znamo velicinu pa mozemo samo nagadjati (makar to bio i educated guess) i nailaziti na prekinuti program jer podataka ima previse ili pak na neracionalno iskoristenu memoriju koja zjapi prazna, uredno alocirana. Drugi je ono sto se naziva "memory pooling", a tice se fragmentiranja memorije kao najnepozeljnijeg nacina rukovanja istom (cak i kad se za nju brine MMU).

Ovo drugo bi nas mozda i zadovoljilo, ali...

Rjesenje je u promjeni tijeka samog programa. Necemo alocirati nikakav prostor za podatke. Zatrazit cemo od DOSa (u smislu necega sto se brine o file-systemu pa nam kao takvo moze vratiti i podatak o velicini datoteke) tu informaciju i pokusati alocirati potrebnu kolicinu memorije. OS nam u vecini slucajeva moze dati dva podatka vezana uz memoriju - ukupnu kolicinu raspolozive memorije i kolicinu najveceg bloka. Problem - alocirati mozemo samo vrijednost unutar najveceg bloka. Drugim rijecima - ako imamo 100 MB memorije koju je necije "pametno" rjesenje iz prethodnog odlomka fragmentiralo tako da sad imamo 100 blokova po 1M i nikakav MMU koji ce to pocistiti za nama (MMU kao memory managment unit, da ne bude "nisam znao"), eto nam problema - ne mozemo alocirati vise od 1M. Imamo memoriju, a nemamo memoriju.

Znaci, sad treba "pjeske" obaviti ono za sto bi se u nekim idelanim uvjetima pobrinuo heap. Zatrazimo od OSa podatak o LMBu (largest memory block) i alociramo ga (ako nam je potrebno bas toliko ili vise). Pametno programiranje na vrlo niskom nivou ne bi zatrazilo LMB nego memory pool koji je velicinom najblizi nasim zahtjevima.

Kad alociramo potrebnu memoriju ili njezin dio, provjerit cemo ima li OS na raspolaganju jos memorije za nas program. Ako nema, morat cemo podatke obraditi unutar kolicine koju nam je dodijelio. Lameri ce ispisati "Not enough memory" i srusiti system da se ne zamaraju.

Ako ima, mozemo se posluziti vezanim listama. Obzirom da ih je Elinka uredno objasnila, necu ponavljati sto su i zasto su, ali to ujedno zaokruzuje pricu o pokazivacima. Naime, kad se varijable inicijaliziraju tijekom izvrsenja programa (dakle, kad su napisane "na vrhu" koda i konkretno definirane), za njih se u memoriji vrsi alokacija putem onog dijela koda koji kompajler priljepi nasem programu kad ga prevodi u exe. U slucaju dinamickih alokacija, ne mozemo znati gdje se nalazi varijabla "i" alocirana naknadno. Razlozi leze u samom nacinu prevodjenja koji takodjer nema smisla sad objasnjavati, ali tice se relokatibilnosti koda i nacina na koji se CPU brine za interpretiranje pojedinih instrukcija. Jedina informacija koju nam alociranje vraca je adresa na kojoj se nalazi alocirani blok. Ako je u pitanju pametniji OS koji na raspolaganju ima i MMU, taj podatak se prosljedjuje i njemu kako bi se mogao preuzeti posao cistaca bazena odnosno onoga sto, primjerice, Javi na daleko visem nivou radi garbage collector.

Rezime - prvo nam nedostaje memorije, potom taj problem pokusavamo rjesiti koristeci automatiku heap memorije i automatizirano upravljanje njome. Nakon toga budimo se u stvarnom zivotu i nailazimo na programiranje multitasking OSa gdje heap jos uvijek radi, ali nam nedostaju terbajati memorije koliko si preventivno prisvaja. Tada upoznajemo alternativu - dinamicku alokaciju memorije. Napustamo automatiku, a pametni kompajler ce nam omoguciti iskljucenje heapa i prepustiti nam da se sami brinemo za memoriju. Tu negdje upoznajemo konkretnu vrijednost pointera i pokusavamo zaboraviti na blagodati GOTO naredbe. Kakve veze ima GOTO? Ono sto vraca alocirana memorija je konkretna adresa memorijskog prostora na koji, gle, gle, mozemo i skociti iz naseg programa! Dakle, otvara se prostor za skakace koji se obicno koristi iskljucivo za dinamicku relokaciju koda (hint: virusi). U praksi ne zelimo skakutati po memoriji jer ne znamo gdje ce nas odvesti i ne zelimo alocirati memoriju na konkretnoj memorijskog lokaciji (iako mozemo) samo zato sto smo u programu napisati da se podatak procita s adrese $00700000. Ovo je ekvivalent skakutanju s GOTO naredbom, naziva se "lupanje po metalu" i potice iz starih dobrih vremena kad su pravi momci nocima pisali introe i silom pokusavali ne samo OSu nego i procesoru oduzeti kontrolu kako bi ustedili memorijski ciklus ili dva.

Skakace su u C-u preduhitrili pokazivacima. Naravno, ostavili su im GOTO naredbu ne bi li se programeri "naviknuli". Khm. Zanimljivo da je i Java tretira kao kljucnu rijec, ali bez konkretne uporabe. Spominjem javu jer je otisla jos dalje zabranivsi manipulaciju putem pokazivaca. Ako mislite da je vizualno razvijanje aplikacija pametno, mozete se sloziti i s uskracivanjem koristenja pokazivaca obzirom da u praksi cesce dovode do pogreske kobne po OS od GOTO zavrzlama!

Pokazivaci u Pascalu nisu (smisleno) najsretnije rjeseni. C-ov pristup je puno prihvatljiviji (proucite pa odlucite sami), a za najlakse razumijevanje uvijek je dobro spustiti se do dna i vidjeti sto o tome misli CPU. Ovdje opet vrijedi spomenuti Motorolu koja programere odmah nauci na pokazivace. Naime, za razliku od Intela, motorola razlikuje samo dva tipa registra - adresne (komada osam) i registre za podatke (takodjer komada osam). U tom smislu oni za podatke (imenovani od d0-d7) sadrze konkretan podatak koji stane u 32-bita, dok adresni (a0-a7) sadrze adresu (takodjer 32-bitnu). Kvaka je u tome sto su adresni zapravo pokazivaci cija se vrijednost (tijekom kodiranja) moze citati jednostavnim stavljanjem imena registra u zagrade cime na neki nacin postaju ekvivalenti data registrima.

Na taj nacin moguce je vrlo brzo pohvatiti konce i logiku koristenja pokazivaca obzirom da se kompletno asemblersko programiranje bazira na njima.

Evo, necu dalje. Pokusajte s vremena na vrijeme stvari stavljati u kontekst i uciti iz onoga sto vec znate. Ovdje bi se sad fino moglo nastaviti s pricom o samim pokazivacima i njihovoj primjenjivosti, ali to cemo pustiti za neki drugi dan.

(c) 06/05/1999 Goran Paulin