Kako alocirati puno memorije?

[krcko]

Gradim stablo koje ce narasti na 100-tinjak megabajta i vise. Jasno, necu alocirati sve odjednom, no zanima me koja je optimalna velicina blokova memorije koje trazim od malloc-a.

Prva ideja je alocirati cvor po cvor. Cini se najprirodnije, no strah me da ce zbog jaaako cestog pozivanja doci do fragmentacije memorije. Pa bi rupe izmedju mogle popapati vise memorije nego iskoristeni dio.

Alternativa je alocirati u blokovima neke razumne velicine, recimo izmedju 100 Kb i nekoliko Mb. Unutra punim cvorove jedan za drugim dok ne potrosim blok, tek onda ponovo trazim memoriju od malloca.

Pitanje je zna li netko kako se to "standardno" radi? Jasno je da implementacija alociranja memorije nije stvar C-a nego ovisi o OS-u. Prema dosadasnjim eksperimentima na W2K isplati se alocirati u vecim blokovima, a za Linux nisam siguran. Zna li netko vise o tome?

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[Matko]

Memory management je nesto sto je uvijek pod kontrolom OS-a i nad time bez odgovarajucih specijalnih API funkcija programer nema nikakvu kontrolu direktno iz samog (ANSI) C-a. S druge strane, memory management bi po defaultu trebao biti dovoljno inteligentan da programeru uvijek omoguci maksimalno mogucu alokaciju memorije. To znaci da onoliko memorije koliko bi mogao alocirati u malim chunkovima bi isto tako trebalo biti moguce alocirati i odjednom.

Fragmentacija memorije je jedna sasvim druga prica i nad time je dosta tesko imati uopce ikakvog utjecaja. Svaki proces u OS-u prilikom startanja dobiva svoj virtualni adresni prostor koji je za njega linearan. Heap (prostor iz kojeg se crpe dinamicki alocirani komadi memorije) jest u tom adresnom prostoru jedan najobicniji segment, i dok iz procesovog kuta gledanja tu moze biti sve uredno poslozeno, dotle u stvarnom fizickom adresnom prostoru (koji je pod vise-manje iskljucivim protektoratom OS-a) moze vladati prilicno razbacano stanje. Naravno, ukoliko program radi puno sitnih alokacija i delakocija, tada ce i u procesovom privatnom heapu stanje moze biti itekako razbacano, dajuci sve skupa razbacanost^2.

Iz tog razloga vec u samom startu nije dobro razmisljati o tome da se u programu radi puno alokacije i dealokacije. U ovisnosti o kvaliteti memory management rutina i fragmentiranosti memorijskog prostora (sto je tesko predvidljiva velicina) malloc() i free() su po svom vremenu izvrsavanja spore do jako spore funkcije, pa zbog toga ucestalost njihovih pozivanja ne bi smjela biti jako velika (ukoliko se ne zele nepotrebno narusiti performanse programa). Standardno (i najjednostavnije) rjesenje jest alocirati odmah prilikom startanja programa dovoljno veliki komad memorije (i 100 MB ako treba ukoliko to dopustaju resursi) kao memory pool, dealocirati ga, naravno, tek prilikom izlaska iz programa, te definirati vlastite alokacijske rutine za alokaciju i dealokaciju chunkova koje ce koristiti memory pool (a koje ce vjerojatno biti moguce implementirati efikasnije ukoliko se uzmu u obzir specificnosti osnovnih struktura podataka za koje se alocirava memorija).

Naravno, ne treba previse razbijati glavu s time ukoliko ti se sve to ne da programirati. Postoji vec hrpa gotovih open source implementacija za memory management (ja imam neke za C++, ali sigurno isto tako postoje i za C) koje se mogu naci na netu (afaik, obicno dolaze kao dio implementacije garbage collectora za C, pa ces ih searchajuci zajedno s tim keywordom vjerojatno lakse uspjeti naci).