abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 07:00 | Komunita

Canonical na svém blogu oznámil, že Ubuntu 18.04 LTS získalo certifikaci FIPS 140-2 Level 1. Jedná se o americký vládní standard pro počítačovou bezpečnost používaný ke schvalování kryptografických modulů. Certifikace bývá vyžadována u státních, zdravotnických a bankovních IT systémů.

Ladislav Hagara | Komentářů: 5
včera 11:44 | Nová verze

Linux Kodachi, linuxová distribuce zaměřená na bezpečnost a ochranu soukromí, byl vydán ve verzi 7.0. Vychází z Xubuntu 18.04. Přehled novinek v changelogu.

Ladislav Hagara | Komentářů: 0
včera 11:22 | Humor

Linus Torvalds se v rámci oznámení o vydání Linuxu 5.7-rc7 pochlubil vylepšením svého hlavního počítače: Poprvé za 15 let není uvnitř Intel, není to ještě ARM, je to AMD Threadripper 3970x, allmodconfig je třikrát rychlejší.

Ladislav Hagara | Komentářů: 19
včera 11:11 | Komunita

PGCon 2020, tj. konference vývojářů a uživatelů databázového systému PostgreSQL, proběhne online od úterý 26. května do pátku 29. května. Na programu jsou zajímavé přednášky i tutoriály. Sledovat je lze zdarma a bez registrace.

Ladislav Hagara | Komentářů: 0
včera 00:22 | Nová verze

Po třech a půl letech od vydání verze 016 byla vydána nová verze 017 alternativní linuxové distribuce GoboLinux. Podrobnosti v představení nové verze a v poznámkách k vydání. GoboLinux nedodržuje standardní hierarchii souborového systému (FHS), nýbrž jsou jednotlivé programy instalovány do vlastních adresářů.

Ladislav Hagara | Komentářů: 2
24.5. 16:22 | Nová verze

Byla vydána nová major verze 6.0 multiplatformní digitální pracovní stanice pro práci s audiem (DAW) Ardour. Přehled novinek i s náhledy v oficiálním oznámení.

Ladislav Hagara | Komentářů: 0
24.5. 11:11 | Zajímavý projekt

Sxmo aneb Simple X Mobile je uživatelské rozhraní pro mobilní telefon PinePhone vycházející z projektu suckless aneb "softwaru, který štve méně". Využívá dlaždicového správce oken dwm, dynamické menu dmenu, emulátor terminálu st nebo webový prohlížeč surf. Videoukázky.

Ladislav Hagara | Komentářů: 12
24.5. 08:00 | Nová verze

Krita, tj. svobodný program pro skicování, malování a úpravu obrázků, je nově k dispozici (Google Play) také pro operační systémy Android a ChromeOS. Zatím se jedná o beta verzi.

Ladislav Hagara | Komentářů: 1
24.5. 02:00 | Komunita

Roy Schestowitz se na blogu Techrights dlouhodobě zabývá kauzami Microsoftu souvisejícími s open source a Linuxem. V současné době upozorňuje na četnost článků o Microsoftu v sekci Linux na webu ZDNet nebo že web Softpedia opustil Marius Nestor, který psal o linuxových novinkách, a příslušnou sekci po něm převzal „Microsoft Editor“ Bogdan Popa. Připomíná také dřívější podobné případy.

Fluttershy, yay! | Komentářů: 11
23.5. 09:00 | Nová verze

Po dvou letech od vydání verze 2.94 byla vydána nová major verze 3.00 multiplatformního BitTorrent klienta Transmission (Wikipedie). Přehled novinek na GitHubu. Zdůraznit lze například vylepšenou podporu IPv6.

Ladislav Hagara | Komentářů: 7
Kdy přecházíte na nové vydání distribuce/OS?
 (13%)
 (13%)
 (22%)
 (7%)
 (4%)
 (41%)
Celkem 311 hlasů
 Komentářů: 0
Rozcestník

Fragmentace paměti s hash_setem

12.7.2009 14:42 | Přečteno: 970× | programování

Co se stane když se hash_map/hash_set s alokátorem spojí proti vám? Za velmi specifických podmínek může 15 MB bloků alokovaných hash_mapami/hash_setmi zabírat i 300 MB (resident size).

Bug report

Den začal optimisticky s bug reportem, že jedna operace zabírá na linuxu neskutečné množství paměti (aplikace přeložena pro windows že stejných zdrojaků tímhle bugem netrpěla).

Říkám si, nějaký podivný memory leak. První zvláštní věc byla, že paměť narostla jenom jednou, při opakování daný operace už víc nenarostla. Možná kdesi v paměti zůstala zapomenuta kopie nějaké větší struktury. S debuggerem jsem zjistil že se to děje při vytváření tabulek křížových referencí, ale ani po pečlivém zkoumání jsem nenašel žádný zapomenutý new ani nic podobného.

Tabulky křížových referencí jsou ve zkratce hash_mapa mapující ukazatel symbolu na ukazatel třídy XrefEntry, která obsahuje malý hash_set a dva malé std::sety ukazatelů (malý = řádově do stovky prvků).

Valgrind vs top

Co se dá dělat, podívám se na to s valgrindem. Leak tam nebyl ale ani podle valgrindu. Navíc valgrind ukazuje nárůst jenom o cca 15 MB reachable bloků, jenže top ukazuje nárůst o 300 MB v resident size. Vylučovací metodou zůstala jenom možnost fragmentace paměti. Že něco takového existuje jsem věděl, jenže nikdy předtím jsem na to nenarazil v míře, kdy by se 15 MB malých kousků roztahalo po 300 MB namapovaných stránkách.

Po mnoha náhodných pokusech s tím něco udělat nakonec zabrala výměna hash_set za obyčejný std::set v XrefEntry. Při dané operaci tabulky referencí používají velké množství malých (hash_)setů (jako členy XrefEntry). Instance XrefEntry často vznikaly a zanikaly, tím pádem často vznikaly i členské (hash_)sety, kterých kterých obsah se často měnil (a prudce kolísali ve velikosti, tj. maximum skutečně použité paměti bylo o hodně vyšší než 15 MB malých bloků po skončení operace).

Hash tabulka vs červeno-černý strom

Výhoda std::map a std::set oproti hash_ verzím je nejspíš v tom, že nepotřebuje alokovat extra malé kousky paměti pro buckety (u gcc i msvc je map/set implementován jako červeno-černý strom). Co způsobilo takové roztahaní po paměti byla zřejmě velmi specifická posloupnost alokací a dealokací bucketů u těch hash_setů a std::allocatoru to moc nesedlo.

Zkusil i jiné implementace map a setů. Např. boost::unordered_set měl v daném případě podobné problémy, ale roztahanost po paměti byla menší asi o 25%. Pro zajímavost, tady je porovnání několika dalších implementací (hash) tabulek:

Comparison of Hash Table Libraries

Hash tabulky mají konstantní složitost vkládání/vyhledávání/mazání, člověk by čekal že budou o hodně rychlejší než třeba červeno-černý strom s logaritmickou složitosti vkládání/vyhledávání/mazání. Prakticky u skutečných implementací musí být záznamů v tabulce hodně (nejméně desettisíce), aby byla hash tabulka rychlejší (extra režie). Neměřil jsem samozřejmě všechny implementace, ale boostí unordered a STL implementace (gcc, msvc) se chovají takhle.

       

Hodnocení: 100 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

12.7.2009 16:21 l4m4
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
To je zase benchmark...

For glib and ghthash, what is inserted is the pointer to the integer instead of the integer itself.

A ještě to pak drze diskutuje, že nevýhoda C-implementací generických hash tabulek je, že se to takhle musí dělat. Přitom jsem neviděl kód, který by v do GHashTable integery ukládal jinak než přes GINT_TO_POINTER() (a podobná makra), tj. přímo do tabulky bez dalších alokací...
limit_false avatar 13.7.2009 13:58 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

Njn, ja to cetl asi pred rokem kdyz jsem ten problem s fragmentaci pameti resil (taky jsem potreboval sablonoidne struktury, tim padem glib a ghthash vypadli). IMHO udelat poradny benchmark je neskutecne prace (proto vetsina benchmarku vypada tak jak vypada). Vzdy je lepsi (nebo spis nutny) si vsechno premerit (jine podminky, jine vysledky).

When people want prime order group, give them prime order group.
12.7.2009 20:01 petr_p | skóre: 59 | blog: pb
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Ehm, standardní knihovna je implementovaná z větší části v glibc, ne v gcc. Řekl bych, že i ty hash mapy nebo sety.
12.7.2009 20:10 l4m4
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Podle mne myslel standardní knihovnu C++ (libstdc++ AKA STL). Ta přichází s gcc. Coby podmnožinu z definice zahrnuje i standardní knihovnu C, takže teď bychom mohli začít řešit, co je větší, nicméně STL je v gcc.
limit_false avatar 13.7.2009 13:39 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

STL je urcite implementovana jako soucast gcc/msvc (i kdyz treba existuji separatni implementace jako STLport). C++ sablony navic ani nejde kompilovat (do strojoveho kodu; jedine do predkompilovanych headeru) pokud se neudela konkretni instanciace.

Na druhe strane implementace sablon urcite pouziva funkce z glibc (treba malloc/free pres new/delete a std::allocator), tim padem vykon znacne zavisi i od glibc.

Taky mam domnenku, ze od glibc zavisi rychlost vyjimek (tohle nemam jeste vyreseno, urcite jde o nejakou kombinaci z trojice glibc, binutils, libgcc_s.so), viz nasledujici pripad (__cxa_throw a _Unwind*):

spousta vyjimek v CentOS 4

spousta vyjimek v CentOS 5

Obe mereni je stejny testcase (specialni extremni pripad s 70000 vyjimkama, nemilujete proste specialni pripady? ;-)). Vzdy prelozeno s gcc 4.1.2 (libgcc_s.so je soucasti gcc, tim padem i stejna libgcc_s.so odkud jsou _Unwind* funkce). Jednou na CentOS 4 s glibc 2.3.4 a jednou na CentOS 5 s glibc 2.5. Jedina rozdilna vec krome glibc jsou jiny verze binutils. No a ta CentOS 5 verze beha v danem pripade vic nez 5x rychleji.

(Nejspis ten problem s vyjimkama bude mat neco do cineni s timhle: http://gcc.gnu.org/ml/gcc/2005-02/msg00627.html ).

When people want prime order group, give them prime order group.
limit_false avatar 13.7.2009 14:16 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

Pozn. v tech grafech pochazeji vsechny funkce pod __cxa_throw z libgcc_s.so krome dl_iterate_phdr (je z glibc) a __gxx_personality_v0 (je z libstdc++ i s uzlem pod nim).

When people want prime order group, give them prime order group.
14.7.2009 02:05 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Na druhe strane implementace sablon urcite pouziva funkce z glibc (treba malloc/free pres new/delete a std::allocator)

Ne nutně. Na unixových systémech to tak nejspíš většinou bude, ale nemusí to tak fungovat všude. Standardní C++ knihovna může být teoreticky naprosto nezávislá na standardní C knihovně.

limit_false avatar 14.7.2009 12:36 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

Prilis si neumim predstavit jak by se implementovalo new/delete nebo std::allocator bez malloc nebo mmap. Snad jedine primym volanim do kernelu (pres preruseni), co je prilis low-level pro standardni C++ knihovnu.

When people want prime order group, give them prime order group.
14.7.2009 12:45 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Prostě by si tu alokaci napsali autoři sami, stejně jako ji napsali autoři implementace malloc() a free() v libc. Uvědomte si, že C++ je jazyk zcela nezávislý na C, teoreticky byste mohl mít C++ i na platformě, kde vůbec neexistuje překladač céčka, a tedy ani standardní C knihovna. Koneckonců dřív používala i řada projektů psaných v C své vlastní náhražky za systémové malloc() a free() a autoři to zdůvodňovali tím, že jejich implementace jsou efektivnější, což by nebylo dost dobře možné, kdyby to byly jen nadstavby nad těmi systémovými implementacemi.
limit_false avatar 14.7.2009 14:30 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

Tak tady doslo asi k nedorozumeni. Ja puvodne psal o zavislosti na glibc uz jenom proto (pripad Linuxu), ze na preimplementovani malloc/free potrebujete nejakou systemovou funkci jako mmap/brk, abyste mel _nejakou_ pamet nad ktorou postavite vlastni malloc/free. A mmap/brk je taky soucasti glibc (jinak musite volat kernel primo pres preruseni/syscall).

When people want prime order group, give them prime order group.
14.7.2009 18:07 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
A mmap/brk je taky soucasti glibc (jinak musite volat kernel primo pres preruseni/syscall).

Odpověděl jste si sám: ty funkce nejsou nic jiného než wrappery nad příslušné syscally. A použití céčkových wrapperů není principiálně nutné. Navíc se na to pořád díváte příliš linuxocentricky.

limit_false avatar 14.7.2009 23:23 limit_false | skóre: 23 | blog: limit_false
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem

True :-) Dival jsem se na na jiny implementace new, snad vsechny bezne non-embedded systemy volaji nejakou verzi malloc (vratane msvc). Pak jsem disassembloval mmap, abych videl ze nema extra rezii. K alokatorum se jeste dostanu.

BTW nechapu tvrzeni "Standardní C++ knihovna může být teoreticky naprosto nezávislá na standardní C knihovně." AFAIK musi C++ alespon implementovat vsechny funkce C, treba taky malloc?

When people want prime order group, give them prime order group.
15.7.2009 00:31 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Všechny rozhodně ne, jen některé. Funkce malloc() mezi nimi sice je, ale neznamená to, že musí jít o stejnou implementaci jako v libc. Vztah mezi funkcí malloc() a operátorem new je takový, že malloc() nesmí k alokaci použít new
The functions calloc(), malloc(), and realloc() do not attempt to allocate storage by calling ::operator new().
ale na druhou stranu se výslovně uvádí, že není specifikováno, zda operátor new používá malloc() nebo ne
Whether the attempt involves a call to the Standard C library function malloc is unspecified.

Takže operátor new může být nadstavba nad funkcí malloc(), ale stejně tak na ní může být úplně nezávislý. Funkce malloc() ale nesmí být implementována pomocí operátoru new, IMHO kvůli tomu, aby bylo možné beztrestně overloadovat new vlastní verzí využívající malloc().

15.7.2009 00:36 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Fragmentace paměti s hash_setem
Příkladem něčeho, co je garantováno v ISO C, ale v ISO C++ to být nemusí, jsou např. celočíselné typy definované v <stdint.h>. V C++ programu se obecně nemůžete spolehnout na to, že je budete mít k dispozici (ani ty, jejichž dostupnost garantuje norma jazyka C).

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.