Za vším hledej new/malloc

17.7.2009 18:13 | Přečteno: 1982× | programování |

Nejbizarnejší performance bugy měly vždy do činění s new/malloc. Když 65% času algoritmu se stráví v new/malloc, je to znamení že alokátor bude třeba nejspíš vyměnit.

Dlouho jsme řešili proč některé operace naší aplikace trvají extrémně dlouho na msvc. Stejný testcase přeložen s msvc 7.1 na windows zabral klidně i 10x víc času než na linuxu s gcc 4.1.2 (opět extrémní případy).

Malé kousky paměti

Pokaždé v testcase figuroval celkem veliký syntaktický strom (AST) s řádově 500 tisíc uzlů a tím pádem veliké tabulky křížových referencí. Uzel v AST stromu navíc obsaje atributy, typicky několik pointrů na referencované deklarace, někdy několik textových atributů nebo seznam elementů (třeba pro volání metody). Každý uzel je alokován přes new jako smart pointer (tzn. mnoho alokací malých kousků paměti).

Testcase pozůstával z nalezení tranzitivního uzávěru části stromu (aby se posléze skopírovaly i deklarace referencované přes weak pointery), kopie uzávěru a vybudování tabulek referencí pro skopírovaný podstrom (pak nějaké další operace).

Profiler odhalil že 50-75% času ve windows bylo stráveno v - new/malloc !!!. Přesněji ve systémových funkcích RtlAllocateHeap, RtlReAllocateHeap, RtlInitializeCriticalSection volané přes new/malloc. Výsledky profileru jako na následovném obrázku vůbec nebyly výjimečné:

Co uděláte když vám kód zpomaluje builtin malloc/new? Windows nemá mechanizmus typu LD_PRELOAD, výměna builtin alokátoru (new/malloc) je celkem "chlupatá" záležitost. Dlouho jsme to řešili minimalizací kopírovaní struktur s velikým počtem malých kousků paměti (části AST, rebuild tabulky referencí). Vždy to alespoň částečně zabralo, ale nakonec to nebylo dostačující.

Specializované alokátory

(Téměř) každá STL "kontejnerová" šablona má jako poslední argument alokátor, který je možno změnit ze std::allocator na vlastní alokátor. Podle profileru by specializovaný alokátor pomohl nejvíc AST stromu a tabulkám referencí. Nejjednodušší to bylo vyzkoušet u tabulky referencí (velká hash_mapa mapující ukazatel symbolu na ukazatel strukturu XrefEntry s třema std::sety).

Volba náhradního alokátoru padla na pythoní alokátor, protože jsem ho celkem dobře znal - kdysi jsem ho ladil kvůli možným memory leakům (nebyly nakonec v alokátoru, ale ve volajícím kódu). Pythoní alokátor není thread-safe, ale pro dané omezené použití v tabulkách referencí to nevadilo. Jediný trik navíc je nutnost přeložit pythoní alokátor s překladačem C a ne C++ (předpokládá specifické chování překladače C, co sice není úplně čisté, ale je to hodně dobře vyzkoušeno - psát vlastní alokátor je zábava na tak dva roky).

Pythoní alokátor je specializován na alokování velkého množství malých bloků (inty, listy apod). Různé bloky strká do různých "arén" s granularitou 8 bajtů (do limitu 256 bajtů, větší alokace jsou žádány od builtin mallocu). Pro podrobný popis se podívejte se na komentáře v Pythoním Objects/obmalloc.c.

Pro použití pythoního alokátoru se STL se přidala šablona implementující model STL alokátoru, který volá PyObject_Malloc a PyObject_Free místo běžných alokačních funkcí. Tato šablona se použila jako alokátor v tabulkách referencí (u zmíněný hash_mapy a členských std::setů XrefEntry). Pak ještě zlepšily výkon per-class operatory new a delete u XrefEntry, které taky volaly pythoní alokátor.

Low Fragmentation Heap (LFH)

Výměna std::allocator za pythoní alokátor zrychlila ve windows problematické speciální případy o cca 40%. I když stále to bylo viditelně pomalejší než na linuxu.

Snad s úplně podivně zvráceným štestím jsem po tisícere googlení a po roku řešení msvc/windows alokátoru další náznak našel na stackoverflow.com. Dotaz byl na úplně jiný problém, ale v komentářích byla zmínka o Low Fragmentation Heap (LFH). LFH je vhodná zrovna pro případy, kdy se alokuje velké množství po malých kouscích. LFH interně pak obsluhuje požadavky do 16 kB, větší jsou alokovány "starým" alokátorem. Od Vist výše je LFH defaultní heap.

V MSDN jsem našel způsob, jak nastavit LFH pro heap aktuálního procesu, ale navíc zabralo to pokroucené štěstí a zkusil jsem to nastavit pro všechny heapy procesu (použití LFH pro heap získanou přet GetProcessHeap to nemělo žádný výsledek v rychlosti). Zázrak! Spousta operací zahrnující kopii části AST stromu se zrychlila navíc o 25-50% !

Jinak LFH je celkem černá magie a existuje spousta důvodů, proč se LFH nemusí povést zapnout.

Zapnutí Low Fragmentation Heap (LFH)

Nastavení LFH pro všechny heapy procesu.

Porovnání alokátorů

Hlavný rozdíl je v bezpečnosti použití v multi-thread aplikacích. (Dále budu psát zkráceně pyalloc místo pythoní alokátor). Pyalloc thread-safe není, ostatní dva jsou (gcc/glibc, msvc). Ve speciálních případech v tomhle zápisku neměl pyalloc žádný měřitelný efekt oproti linuxovému gcc/glibc (gcc 4.1.2, glibc 2.5), jak v rychlosti tak ve množství spotřebované paměti. Nejspíš by měl efekt při fragmentaci paměti u hash_setu (viz minulý zápisek).

U msvc/windows byl lepší pyalloc jak v rychlosti a i v memory footprintu proti msvc/windows alokátoru bez LFH (v množství použité paměti byl pyalloc většinou o 2-5% lepší, nejhorší naměřený případ byl 0.5% overhead pyallocu). U msvc/windows byl pyalloc vždy lepší v množství použité paměti proti čistému LFH (o cca 5-10%).

msvc/pyalloc+LFH proti msvc/LFH:
pyalloc+LFH vždy lepší o 2-10% v množství spotřebované paměti a o 10-20% lepší v rychlosti v případech kde hodně záviselo na budování a hledání v tabulkách referencí.

       

Komentáře

[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