Za vším hledej new/malloc (diskuse)

[snajpa]

Nečetl jsem předchozí diskuze pod podobnými články, možná to tam zaznělo, ale proč mi to připadá jako výstup z google translate?

[12345]

To by u Google byla pořádná oslava, kdyby něčeho takového dosáhli

[snajpa]

Asi to bude tím, že to je klasická programátorština

[limit_false]

Chvili mi trvalo nez mi doslo co se mysli pod "jak kdyby to vypadlo z google translate". Ale std::programatorstina je spravna odpoved, BTW ja tak normalne mluvim a nejsem zdaleka sam

[deda.jabko]

nicmene, kdyz jsem si prosel i vase predchozi prispevky... vychazi mi, ze byste si usetril hromadu casu a nervu, kdybyste s klidem ignoroval datove struktury z STL a napsal si je sam... tolik kodu to zase neni a clovek si je muze prizpusobit aktualnim potrebam.

[limit_false]

Zrovna ten syntakticky strom je napsan "po domacku" a i tak se projevovaly problemy s alokatorem. Alokatoru se proste nezbavite Nemyslim ze by "vlastni STL" prineslo nejake zlepseni navic.

Vsechny zminene performance problemy jsou nejake specialni pripady, "vlastni STL" by mela akorat jine specialni pripady.

[deda.jabko]

moc do projektu nevidim, takze nechci moc kecat...

Nemyslim ze by "vlastni STL" prineslo nejake zlepseni navic.

no, nemyslel jsem prepisovat cele STL (dokazi si predstavit hezci knihovnu)

...ale spis jsem myslel naimplementovat jednotlive datove struktury presne na miru problemu... ja treba z duvodu zlobiveho alokatoru mam jednu implementaci RB-stromu, kde kazdy RB strom si na zacatku naalokuje velky kus pameti a postupne si z nej bere uzly... a jelikoz nepotrebuji odebirat uzly ze stromu... staci mi na konci prace udelat jedno velke free().

"vlastni STL" by mela akorat jine specialni pripady.

ale zase jsou to specialni pripady, ktere muzete lip podchytit...

[limit_false]

Kdyz se jenom pridava, je to o hodne jednodussi nez kdyz se casto strida pridavani/odebirani (muj pripad), protoze pak vznikaji diry v alokovane pameti kam je potreba nacpat nove alokovane veci.

Pro ruzne kontejnery (at jiz STL nebo kontejnery ruznych jinych jazyku) je dulezita rozumna predikce jak moc se jeste bude vkladat a jaka rezerva se udela, kdyz pri nejakem add() misto dojde. Tady jdou dva pozadavky proti sobe: minimalizovat pocet alokaci a minimalizovat velikost spotrebovane pameti.

Mnoho STL kontejneru ma metodu reserve, a muzete si porucit predalokovani pameti. Jenze to moc nepomuze kdyz je hodne instanci malych struktur.

ale zase jsou to specialni pripady, ktere muzete lip podchytit...

Myslim ze to vyjde uplne nastejno. Aby vlastni specializovane struktury fungovaly lepe, musite mit celkem striktni omezujici podmniky, jinak specialni pripady budou proste jine.

 

[deda.jabko]

Kdyz se jenom pridava, je to o hodne jednodussi nez kdyz se casto strida pridavani/odebirani (muj pripad), protoze pak vznikaji diry v alokovane pameti kam je potreba nacpat nove alokovane veci.

to nebyla podstata toho, co jsem chtel rict... jde o to, ze pak budete mit kod pod vetsi kontrolou a nemusite pouzivat ,,general purpose'' reseni, ktera musi delat kompromisy a muzete pouzit ruzne vychytavky...

[pht]

Já bych za vším spíš hledal delete/free.

[deda.jabko]

to muze byt dost dobre mozne... zajimalo by me, co by se stalo kdyby jako alokator byl pouziti nejaky s garbage collectorem... imho, podle me by si nemuseli vest vubec spatne... garbage collectory maji radi spoustu malych objektu...

[limit_false]

Prave na tenhle zpusob je navrzen pythoni alokator (proto mel takovy uspech i kdyz byl pouzit jen v nekolika "hotspot" strukturach). Neni vubec problem uvolnit pamet po objektu, spise efektivne najit misto pro novy objekt. Diry v alokovane pameti budou vznikat at delate co delate.

[deda.jabko]

Neni vubec problem uvolnit pamet po objektu, spise efektivne najit misto pro novy objekt.

tak toto je u rady GC vyreseno velice rychle... ;-]

Diry v alokovane pameti budou vznikat at delate co delate

prave proto jsem zminoval pouziti GC. bezne alokatory maji jeste docela rezii s udrzovani seznamu uvolnenych objektu... navic pri pouziti compacting GC odpada problem s fragmentaci dat...

[Roger]

Compacting GC byla prvni vec, ktera me pri cteni te zoufale historky napadla... Alokace je, ehm, docela rychla a odpadaji problemy s fragmentaci.

Docela by me zajimalo, jak by si vedl.

[limit_false]

Nejvetsi problem by byl s tou "compacting" casti. Tabulky referenci by se daly upravit, aby s presunem pocitaly, u AST stromu je to absolutne vylouceno. Na druhe strane je mozne ztratit dost casu updatovanim pointru po presunu a indirekci navic. Jak by to dopadlo v tomhle pripade by me taky zajimalo, ale to se asi nedovim.

[Deleted [8409]]

V google V8 je trošičku jiný trik, který jsem použil i v knihovně AsmJit. Pokud je potřeba alokovat mnoho objektů a všechny tyto objekty mají krátkou životnost (a třeba i velikost), je možné alokovat tyto objekty pomocí vlastního heapu, který se ve finále celý uvolní a ty objekty zaniknou s ním. Nevim jestli jsem to vysvětlil dobře, kdyžtak mrknout na zdrojáky AsmJit nebo GoogleV8 (hledat Zone objects)

[Ivan]

Hmm je zvlastni ze si wokna vedly tak spatne. Pokud si dobre pamatuju nejaky prednasku tak NT kernel ma mnohem bohatejsi API. Dokonce si od nej muzete vytorit ruzne alokatory pro ruzne velke objekty a on pak prideluje pamet z ruznych poolu. Cele to ma byt efektivnejsi nez alokace pameti na Unixu. Kdovi jestli se tahle super featura NT kernelu jeste dneska pouziva.

 

 

[PaKr]

Kdysi jsem řešil podobný problém a v Microsoftu mi poradili řešení pomocí funkce _set_sbh_threshold() a ono to zafungovalo.

http://groups.google.cz/group/microsoft.public.vc.language/browse_thread/thread/dbbc89b1f7b86021/ff8fb3f72c757725?hl=cs#ff8fb3f72c757725

[limit_false]

Diky za tip, vyzkousime to. Z popisu funkce _set_sbh_threshold zatim nevim, jestli to taky plati na operator new (tipuju ze nejspis jo).

[limit_false]

Tak jsem to vyzkousel. Velikosti jsem volil 70, 256, 504, 1016 (posledni byla default do win 2000, pak se to vyplo nastavenim na nulu). Jednou v kombinaci s LFH, pak bez LFH. Vysledkem je, ze v uvadenych pripadech to bylo vzdy o 20-50% horsi nez jenom LFH.

Pokud vim, LFH se chova hodne podobne jak ten pythoni alokator, tj. zdruzuje po blocich podobne velikosti, tady je celkem pekny schema: http://www.i.u-tokyo.ac.jp/edu/training/ss/lecture/new-documents/Lectures/16-UserModeHeap/UserModeHeapManager.ppt