C++: non-heap custom allocator for std::string

C/C++

Sziasztok!

C++-hoz keresek olyan allocatort, ami előre lefoglalt memóriaterületen dolgozik, a "munkaterület" kezdeti lefoglalása után nem indít újabb foglalásokat a heap-en, hanem a munkaterületet osztja ki. Az allocator-nak std:string -re és std::vector-ra kell működnie, vagyis std::allocator -t szeretném kiváltani egy heap-et nem használó változatra. Ismertek erre már létező megoldásokat vagy érdemes magamnak megírni? Ha esetleg tudtok küldeni erre kód példákat, ne kíméljetek :)

Üdv:
Dandor

  • 2492 megtekintés

( zsolt | 2009. 01. 24., szo – 22:07 )

Korábban én is kísérleteztem ilyesmivel, de hamar beleütköztem pár problémába.
Magát az allokátort nem nagy kunszt megírni, a BS könyvben is van rá példa.
A gond az, hogy a töredezéstől pillanatok alatt elfogy a pool, ha nem valami jobb algoritmust használsz.
A másik gond, hogy a többszálú működést nem egyszerű megcsinálni.

A lényeg, hogy én egy C-ben megírt pool alloc megvalósításra építettem rá a C++ allokátoromat és így egész jó lett, bár éles üzembe soha nem került, mert dobtam az egész koncepciót egy jobb ötlet miatt.

Sajnos már nem emlékszem mi volt ez a C nyelvű implementáció, de az még rémlik, hogy valami public domain kód volt és régen a Linux kernelben is ezt használták, amíg nem írtak sajátot GPL licenc alatt.

( uid_2813 | 2009. 01. 24., szo – 23:45 )

Nedmalloc-rol eddig csak jot hallottam. Igaz nem ugy mukodik ahogy te szeretned es sima c, de egy probat talan meger.

( dandor | 2009. 01. 25., v – 01:24 )

Valószínűleg a boost segítségével fogom megoldani a problémát.

Két irányba tudok elindulni:
1.) A kényelmesebb az lenne ha a boost:pool_allocator-t tudnám használni,mert az kapasbol stl kompatibilis allocator:
http://www.boost.org/doc/libs/1_37_0/libs/pool/doc/interfaces/pool_allo…
Viszont ezzel az a baj, hogy a doksi alapján nem adható meg a pool kezdeti mérete, nekem viszont a program indulásakor a nem kritikus részben kéne a heap foglalást megtenni. Elképzelhető, hogy egy nagy memóriaterületre vonatkozó malloc/free hivassal a program elején lefoglalná a számomra szükséges blokk méretet(csak ez eléggé gányolós), és később a kritikus pontokon már nem történne több heap használat. Esetleg valaki tudna segíteni abban, hogy hogyan tudnám mégis megadni ennek a blokkméretet?

2.) Második lehetőség: a boost::singleton_pool-t (http://www.boost.org/doc/libs/1_35_0/libs/pool/doc/interfaces/singleton…) egy adapterrel stl kompatibilis allocatorrá alakítanám. Mivel a singleton_poolnak van egy RequestedSize nevre hallgato template paramétere, ezzel nem is lenne gond csak meg kell írni hozzá az adaptert.

Szóval a kérdésem az lenne hogy tudtok-e lehetőséget arra, hogy a blokkméretet megadjam a pool_allocatornak

Dandor

Végülis a korábban vázolt 1.) megoldast választottam. Nekem a boost::pool_allocator -ának default UserAllocator-a megfelelő (a new és delete-en alapuló). Számomra a pool algoritmus memóriaterületének előzetes allokálása volt lényeges, hogy ne a kritikus programrészekben kelljen az operációs rendszertől memóriát kérnem. Ezt így értem el az inicializáló részben:


typedef std::basic_string< char,std::char_traits< char>,boost::pool_allocator< char> > mystr_t;
mystr_t *tmp_str = new mystr_t();
tmp_str->reserve(1000000);
delete tmp_str;

Ezzel a boost által "backend"-ként használt singleton_pool-ban létrejön egy számomra elegendően nagy char pool a stringjeim számára.
Ez úgy néz ki eddig, hogy megoldja a problémámat, persze,ha van szebb,jobb megoldásod szívesen venném ha megosztanád.

Üdv:
Dandor

Ez végülis jó, bár ha sokáig fut a programod, a pool töredezett lesz, és elkezd plusz területeket lefoglalni...

Ha saját allokátort írsz akkor ezzel tudsz valamit kezdeni.
(pl mindig fix méretű területeket foglalsz le akkor nincs töredezettség).

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Én úgy tudom hogy a boost pool algoritmusai fix méretű foglalásokat végeznek, ezért is kell megadni template paraméterként a típust. Ezen típus alapján a "backend" esetemben a boost::singleton_pool már sizeof(tipus)-al fog paramétereződni, azaz az azonos méretű allokálások azonos poolba fognak kerulni.
A szabad területet egy lancolt listán tartja számon, így az allokálás és a felszabadítás is konstans idő alatt elvégezhető. Így a töredezettség itt nem gáz,csak bele kell férnem az elején reserve()-elt memóriamennyiségbe, ha el akarom kerülni, hogy az os-től kelljen kérni még pluszba.
Az alábbi linken bővebben le van írva:

http://www.boost.org/doc/libs/1_37_0/libs/pool/doc/concepts.html

És ez igaz is POD típusok esetében. Azaz amikor előre tudod, hogy mekkora terület kell egy elemhez.

A string viszont nem ilyen. Eleve két részből áll: az egyik maga az osztály a másik pedig a szöveg amit tartalmaz.
Ehhez a szöveghez tartozó terlet az, amit saját hatáskörben foglalgat a string osztály.

Tehát ha egy POD típust használsz object_pool-lal, akkor igaz amit mondtál, minden oké.

Ha egy string-et használnál object_pool-lal, akkor csak a string class adattagjai kerülnének a pool-ba, maga a szöveg nem.

Te pool_allocator-t használsz string-gel, aminek char típust adtál meg, ami azt jelenti, hogy a szövegeket a poolban tárolod.
Méghozzá az általad linkelt oldal alapján a területeket 4 byteonként adja.
Mivel te változó hosszúságú string-eket tárolsz, ezért tuti, hogy elaprózódik a terület...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Ha nem hiszed el, ki is próbálhatod:
Foglalj le egy random hosszú string-et, mondjuk 100-200 karakter között.
Foglalj le 1 karakternyi stringet.
Az elsőt szabadítsd fel.
Ezt ismételd meg sokszor.

Ha neked van igazad, az egész végén a pool csak 4x akkora mint ahányszor ismételted. Ha nekem van igazam, akkor sokkal több.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Ebben termeszetesen igazad van, de ha megnezed a fenti kodot itt char tipusu adatokra hoztam letre a pool allocatoromat, vagyis az stl a stringet mint char tipusu adatok tarolojat fogja fel (basic_string< char >). A char pedig tekintheto POD tipusnak :D

typedef std::basic_string< char,std::char_traits< char>,boost::pool_allocator< char> > mystr_t;

Hali!

Ezt a problémát az alábbi, korábban már leírt pre-allokációs programrészlettel oldottam meg.
Itt a reserve() hivással annyi char-t foglalok le az inicializalaskor amennyi biztosan elegendő lesz (itt:1000000) a kritikus programrészben.


typedef std::basic_string< char,std::char_traits< char>,boost::pool_allocator< char> > mystr_t;
mystr_t *tmp_str = new mystr_t();
tmp_str->reserve(1000000);
delete tmp_str;

A boost pool algoritmusa pedig biztositja, hogy ne okozzon gondot a töredezés,amiért azt az árat fizetem hogy csak fix méretű allokalasokat tudok vegezni egy pool-on belül (esetemben sizeof(char) ). A korábban belinkelt oldal elmondja, hogy hogyan.

Üdv:
Dandor

Látom nem érted...

A pool-on belül töredezik a memória.

"azt az árat fizetem hogy csak fix méretű allokalasokat tudok vegezni egy pool-on belül (esetemben sizeof(char) )."

A baj az, hogy te nem különálló char-okat használsz, hanem összefüggő char tömböket. Tehát megjelenik a töredezettség.
(Mellesleg a sizeof(char)==1, azaz byte-onként foglalsz. Miben is különbözik ez a sima memóriafoglalástól töredezettség tekintetében?)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

En ertem, hogy mirol beszelsz, sztem te nem ertesz engem ;)

http://www.boost.org/doc/libs/1_37_0/libs/pool/doc/concepts.html

nezd meg a fenti linken az utolsó két ábrát. Ez a free list-et és az allokalast mutatja be. Ez alapjan lathatod hogy fix meretu allokalas eseten ezzel az algoritmussal nincs toredezes.

"A baj az, hogy te nem különálló char-okat használsz"

Szerintem kulonallo charokat foglalok, ha nem az stl default allokatorat hasznalom. Szerintem a default allokatoros esetre az stl egy optimalisabb specializalt megoldast hasznal, ahol tenyleg blokkosan foglalja a charokat,de az altalanos esetben, ahol sajat allokatort adsz meg ott nem.
Szerintem ezert lehetseges hogy a fenti algoritmust hasznalo boost::pool_allocator < char > -t elfogadja a basic string,mint allocator-t.
Persze lehet hogy tévedek, a foglalás blokkosságáról van konkrét infod a basic_string esetere nem default allocatorral?

És ha összevissza vannak a char-ok, akkor az operator[] honnan tudná hol vannak? Letárolja a címeket egy tömbbe? Azért ugye érzed, hogy nem lenne túl hatékony azon felül, hogy értelmetlen...

Használhatna persze listát, ahol minden elem max 50 karaktert tárol.
Ezzel bizonyos műveletek gyorsulnának (beszúrás, konkatenáció, stb.), egy csomó másik viszont lassulna. Pl. az operator[] nem lenne konstans futásidejű, amit viszont a szabvány előír.

Nem mellesleg a szabvány előírja hogy az &s[0] mutasson a folytonos karaktertömbre.

Részletek itt.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Tr3w, meg kell, hogy kövesselek, valószínűleg a pool interface t.ordered_malloc(n) -jet hasznalja az std::string a folyamatos terulet lefoglalasara (http://www.boost.org/doc/libs/1_38_0/libs/pool/doc/interfaces/pool.html),ami valoban toredezest eredmenyez, bar mivel a programomban az a stringjeim egy részét inicializalaskor letrehozom es utana nem modositom, a maradék része pedig lokális változóként él és minden ciklusban megszűnnek és újjászületnek, ezért engem nem érint kellemetlenul a töredezés a boost:pool_alloc-al,mivel a boost pool ok,ha jol ertelmeztem, rendezett free listet használnak, így újra és újra könnyen fog találni egybefüggő területet. Persze a rendezett lista használata miatt a free sajnos drágább lesz.
Végülis ezzel a modszerrel sikerult megoldanom a problémámat (realtime rendszerben időnként kiszaladtam az időszeletemből),valószínűleg ez a pool-os memóriahasználat,még mindig hatékonyabb mint az oprendszeré.

Nem akarok butaságot írni, de a biztonság kedvéért: nem megfontolandó a sztring feltöltése is, csak hogy a terület "meg legyen írva" (resize())? OOM killer meg ilyenek. (Már ha létezik ilyesmi azon a platformon, amin dolgozol.) Ui. nem tartom valószínűnek, hogy a fenti kód önmagában megírja a területet, akár a string-ben, akár az allokátorban; és inkább ne a kritikus területen érjen a meglepetés.

Szerk: igazából talán mindegy is, megírod-e előre, az OOM killernek mindegy. Kinyírhatja a processzedet akkor is, amikor egy másik (általa fontosabbnak ítélt) program fut ki a memóriából.

Mire gondolsz? Hogy a new operátor bad_alloc-ot dob? Amiről én próbáltam beszélni, az jóval alatta van a C++ kivételeknek.

man malloc (kiemelés tőlem)

BUGS

By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available. This is a really bad bug. In case it turns out that the system is out of memory, one or more processes will be killed by the infamous OOM killer. In case Linux is employed under circumstances where it would be less desirable to suddenly lose some randomly picked processes, and moreover the kernel version is sufficiently recent, one can switch off this overcommitting behavior using a command like 


# echo 2 > /proc/sys/vm/overcommit_memory

See also the kernel Documentation directory, files vm/overcommit-accounting and sysctl/vm.txt.

( Joejszaka v | 2009. 01. 27., k – 12:06 )

Amikor nekem volt ilyen parám, én írtam egy nekem megfelelőt. sok munka, de legalább jó.