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 01:11 | Bezpečnostní upozornění

    Red Hat řeší bezpečnostní incident, při kterém došlo k neoprávněnému přístupu do GitLab instance používané jejich konzultačním týmem.

    Ladislav Hagara | Komentářů: 0
    včera 23:33 | Nová verze

    Immich byl vydán v první stabilní verzi 2.0.0 (YouTube). Jedná se o alternativu k výchozím aplikacím od Googlu a Applu pro správu fotografií a videí umožňující vlastní hosting serveru Immich. K vyzkoušení je demo. Immich je součástí balíčků open source aplikací FUTO. Zdrojové kódy jsou k dispozici na GitHubu pod licencí AGPL-3.0.

    Ladislav Hagara | Komentářů: 0
    včera 22:33 | IT novinky

    Český telekomunikační úřad vydal zprávy o vývoji cen a trhu elektronických komunikací se zaměřením na rok 2024. Jaká jsou hlavní zjištění? V roce 2024 bylo v ČR v rámci služeb přístupu k internetu v pevném místě přeneseno v průměru téměř 366 GB dat na jednu aktivní přípojku měsíčně – celkově jich tak uživateli bylo přeneseno přes 18 EB (Exabyte). Nejvyužívanějším způsobem přístupu k internetu v pevném místě zůstal v roce 2024 bezdrátový

    … více »
    Ladislav Hagara | Komentářů: 0
    včera 12:11 | Nová verze

    Raspberry Pi OS, oficiální operační systém pro Raspberry Pi, byl vydán v nové verzi 2025-10-01. Přehled novinek v příspěvku na blogu Raspberry Pi a poznámkách k vydání. Jedná o první verzi postavenou na Debianu 13 Trixie.

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

    Byla vydána nová verze 4.6 svobodného notačního programu MuseScore Studio (Wikipedie). Představení novinek v oznámení v diskusním fóru a také na YouTube.

    Ladislav Hagara | Komentářů: 0
    včera 02:22 | Komunita

    Společnost DuckDuckGo stojící za stejnojmenným vyhledávačem věnovala 1,1 milionu dolarů (stejně jako loni) na podporu digitálních práv, online soukromí a lepšího internetového ekosystému. Rozdělila je mezi 29 organizací a projektů. Za 15 let rozdala 8 050 000 dolarů.

    Ladislav Hagara | Komentářů: 4
    1.10. 20:11 | Nová verze

    Svobodný multiplatformní herní engine Bevy napsaný v Rustu byl vydán ve verzi 0.17. Díky 278 přispěvatelům.

    Ladislav Hagara | Komentářů: 0
    1.10. 16:11 | Nová verze

    Bylo vydáno openSUSE Leap 16 (cs). Ve výchozím nastavení přichází s vypnutou 32bitovou (ia32) podporou. Uživatelům však poskytuje možnost ji ručně povolit a užívat si tak hraní her ve Steamu, který stále závisí na 32bitových knihovnách. Změnily se požadavky na hardware. Leap 16 nyní vyžaduje jako minimální úroveň architektury procesoru x86-64-v2, což obecně znamená procesory zakoupené v roce 2008 nebo později. Uživatelé se starším hardwarem mohou migrovat na Slowroll nebo Tumbleweed.

    Ladislav Hagara | Komentářů: 3
    1.10. 16:00 | IT novinky

    Ministerstvo průmyslu a obchodu (MPO) ve spolupráci s Národní rozvojovou investiční (NRI) připravuje nový investiční nástroj zaměřený na podporu špičkových technologií – DeepTech fond. Jeho cílem je posílit inovační ekosystém české ekonomiky, rozvíjet projekty s vysokou přidanou hodnotou, podpořit vznik nových technologických lídrů a postupně zařadit Českou republiku mezi země s nejvyspělejší technologickou základnou.

    … více »
    Ladislav Hagara | Komentářů: 3
    1.10. 12:55 | Nová verze

    Radicle byl vydán ve verzi 1.5.0 s kódovým jménem Hibiscus. Jedná se o distribuovanou alternativu k softwarům pro spolupráci jako např. GitLab.

    Ladislav Hagara | Komentářů: 3
    Jaké řešení používáte k vývoji / práci?
     (40%)
     (47%)
     (14%)
     (16%)
     (18%)
     (14%)
     (18%)
     (14%)
     (14%)
    Celkem 159 hlasů
     Komentářů: 10, poslední dnes 01:37
    Rozcestník

    hash_map je zákeřná

    11.7.2009 03:59 | Přečteno: 1484× | programování

    První část blogu věnována performance. "Testbed" je multiplatformní C++ aplikace (linux/windows), kompilována gcc 4.1.2, resp. msvc 7.1. Nejprominentnější struktury jsou dvě: syntaktický strom (AST) a tabulky symbolů. (Kompilovaný jazyk je nějaká podivná kombinace - "kartézský součin" - Verilogu, VHDL a MASTu, syntakticky asi nejblíž Verilogu).

    "Zákeřnost" hash_map je třeba brát trocha s rezervou, běžné na její zákeřnost nejspíš nenarazíte, ale extrémní případy jsou pak kruté.

    Proč je hash_map zákeřná:

    1. není STL standard (až na TR1 jako unordered_map), proto jsou jak template argumenty tak implementace velmi odlišný (gcc vs msvc), tohle je zdánlivá drobnost, ale viz níže
    2. je implementována jako hashovaní se separovanými řetězci (separate chaining), kde pro každou hash hodnotu je v tabulce připojen seznam (bucket) který obsahuje klíče se stejnou hash hodnotou. Co by v principu nemuselo vadit, jenže buckety jsou alokovány přes std::allocator, který používá new/malloc a ten už může dělat skutečně neočekávaně divy při opakovaném (de)alokování spousty malých bloků (o tom příště)
    3. viz unordered_map implementation rationale - boost::unordered_map implementation rationale Týká se to taky hash_mapy, hlavně požadavků na lokální (bucket) iteratory. Není možno použít v implementaci třeba open adressing nebo coalesced hashing (kvůli bucket iteratorům je vlastně vyžadováno separate chaining).

    Případ hash_compare:

    Máme třídu Signatuře (reprezentující signaturu typu argumentů funkce), který datový členy vypadají asi takhle:

    class Signature {
    /* ... */
    private:
        std::vector<size_t> _argumentTypes;
        size_t _returnType;
        bool _varArg;
    };
    

    Instancí třídy Signatuře je mnoho (mnoho funkcí). Překlad standardní knihovny funkci trvalo na linuxu 3 sekundy, na windowse 5 minut.

    Po zjišťování "WTF is going on" jsem zjistil, že nejvíc času se tráví ve win na počítání hashe a porovnávání dvou signatur (operátor <). Zřejmě implementace hash_map v msvc třídí buckety podle operátoru <.

    V tomhle případě se sešli tři faktory, které přispěly k celkové pomalosti:

    1. msvc implementace hash_map volá počítání hashe a operátor < enormní počet krát, tím pádem když není hash predpočten (třeba v konstruktoru třídy), tak i několik porovnání int-ů trvá při počítání hashe dlouho (protože je volaná statisíce kr8t). AFAIK se msvc implementace hash_map snaží radit klíče v bucketech podle operátoru <.
    2. každý typ (argumentů funkce) je identifikován číslem, tyhle čísla jsou sekvenční (nový typ dostane identifikaci jako previous_type_id++)
    3. původně byla funkce Signature::hash() implementována jako sečtení všech datových členů, tím pádem vznikaly hashový kolize (protože id typu byla sekvenční lineární posloupnost)

    Řešení:

    1. použít boost::unordered_map místo hash_map (implementace je podobná jako linuxova/SGI hash_map).
    2. hash počítat již v konstruktoru třídy Signatuře a uložit do member atributů
    3. použít FNV hash (třeba z boostu) místo naivního sčítání member členů kvůli hash kolizím (který se pak uloží jako hash value do nějakého member členů _hashValue):
    // header .h
    
    class Signature {
    public:
        /* ... */
        size_t hash() const { return _hashValue; }
        size_t computeHash() const;
        /* ... */
    private:
        std::vector<size_t> _argumentTypes;
        size_t _returnType;
        bool _varArg;
        size_t _hashValue;
    };
    
    inline size_t hash_value(const Signature& s) {
        return s.hash(); // vrátí v konstruktoru predpočítanou hodnotu _hashValue
    }
    
    // .cpp
    
    Signature::Signature(...) {
        /* nastavení member atributů atd. */
        _hashValue = computeHash();
    }
    
    size_t Signature::computeHash() const {
        size_t seed = _returnType;
        size_t argHash = boost::hash_range(_argumentTypes.begin(), _argumentTypes.end());
        boost::hash_combine(seed, size_t(_varArg));
        boost::hash_combine(seed, argHash);
    
        return seed;
    }
    
    Pak se z 5 minut stalo na windows několik sekund. Rule of thumb: 1. Vůbec nepoužívejte hash_map. Když tak radši boost::unordered_map. Performance pak bude stejná na všech platormach. Není pak navíc potřeba definovat vícero operátorů (postačí definování hashe a operátorů rovnosti). 2. Pro malé mapy (do velikosti řádově 100-1000 klíčů) použijte std::map, je to rychlejší (měřeno profilerem). 3. Nikdy nepoužijte spoustu instanci hash_map pro obrovské množství malých map. Tohle pravidlo hodně souvisí s alokátorma - vedlejší efekty jsou pomalost a memory fragmentation (příště).        

    Hodnocení: 89 %

            špatnédobré        

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

    Komentáře

    Vložit další komentář

    11.7.2009 15:18 Pilgrim
    Rozbalit Rozbalit vše Re: hash_map je zákeřná

    Neminim rypat, ale opravdu jsem jediny komu tohle pripada jako trochu "nedodelany" zapisek? Nebo je to umysl a budes na nem jeste pracovat? Pokud je to "První část blogu věnována performance", tak mi trochu nedochazi (ale mozna je to umysl) k jakymu blogu je to prvni cast, a co je to "performance" (prosty preklad z anglictiny mi trochu nesedi do kontextu - nema to byt nazev nejakeho projektu?). Na "prvni cast" mi  prijde ze se to az moc odkazuje na nejakou "nultou cast" (jestli je to diplomka / bakalarka, tak asi Uvod).

    Navic mi obcas trochu nedochazi logicke souvislosti mezi odstavci (kde je v tride Signature nejaka hash_map? Co s tim ma doba prekladu co delat?).

    Pokud to ma byt pokus o predstaveni novych veci z TR1 a na co si pri praci s nimi davat pozor, tak je to dobry napad (samotneho by me to zajimalo). Pokud se ale odkazujes na nejake predchozi veci (a predpokladas uroven znalosti "neceho" - STL? Boostu? ), mozna by nebylo spatne udelat k tomu nejaky uvod (napr. co je vlastne smyslem tohohle vseho a pro koho to je).

    11.7.2009 15:54 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: hash_map je zákeřná
    Já se musím autora v tomto případě zastat, pochopil jsem, co chtěl říct (nebo spíš na co narazil) a podle mě žádné další třídy představovat nemusí. Podle mě jasně popsal, v čem se liší implementace MSVC, a proč použil boost.
    limit_false avatar 11.7.2009 18:16 limit_false | skóre: 23 | blog: limit_false
    Rozbalit Rozbalit vše Re: hash_map je zákeřná

    Sorry jestli to nebylo jasne:

    Signature je klic v hash tabulce, sama zadnou tabulku neobsahuje.

    Smyslem je ukazat mozne (a neocekavane) problemy pri pouzivani ruznych struktur v C++ (hash_map v tomhle pripade). Urcite nejsem jediny, kdo na to narazil/narazi (a bude to muset resit) a prvni krat je to velke prekvapeni. Specialne hash_map mela neco do cineni s kazdym druhym performance bugem, ktery jsem resil ("performance" lze prelozit jako "vykon", ale neni to uplne ekvivalent). Podle dokumentace clovek napr. ocekava O(1) slozitost vkladani/vyhledavani (za predpokladu ze kolizi neni mnoho), ale skutecna implementace muze delat celkem ruzne veci.

    Znalost STL je predpokladana (alespon vedet o existenci kontejneru jako map, hash_map). Uvod moc udelat nejde, protoze to by byl uvod do prekladacu (proto jsou nastineny jenom podstatne struktury). Je asi potreba hodne predstavivosti ;-)

    I kdyz se omlouvam za tu nejasnost u slova "preklad" - je mineny preklad nejakych zdrojaku tou aplikaci, podobne "standardni knihovna" je standardni knihovna funkci te aplikace.

    Hlavne jsem vcera stravil vic nez hodinu jenom pokusem text postnout - CMS mi vzdy po kazdem nahledu zmenilo entity gt/lt (pouzite pri tech parametrech sablon) na vetsitka/mensitka a vzdy jsem to musel rucne opravit pred dalsim nahledem/dokoncenim (po asi 20 nahledech jsem mel fakt dost, proto je tam nekolik preklepu, nevim jestli jde editovat prispevek i po postnuti).

    When people want prime order group, give them prime order group.
    11.7.2009 23:47 podlesh | skóre: 38 | Freiburg im Breisgau
    Rozbalit Rozbalit vše Re: hash_map je zákeřná
    Uvod moc udelat nejde, protoze to by byl uvod do prekladacu (proto jsou nastineny jenom podstatne struktury). Je asi potreba hodne predstavivosti
    Úvod určitě udělat jde, mělo by z něj vyplynout co je vlastně smyslem článku. Například tento odstavec by podloužil téměř dokonale:
    Smyslem je ukazat mozne (a neocekavane) problemy pri pouzivani ruznych struktur v C++ (hash_map v tomhle pripade). Urcite nejsem jediny, kdo na to narazil/narazi (a bude to muset resit) a prvni krat je to velke prekvapeni. Specialne hash_map mela neco do cineni s kazdym druhym performance bugem, ktery jsem resil ("performance" lze prelozit jako "vykon", ale neni to uplne ekvivalent). Podle dokumentace clovek napr. ocekava O(1) slozitost vkladani/vyhledavani (za predpokladu ze kolizi neni mnoho), ale skutecna implementace muze delat celkem ruzne veci.
    default avatar 12.7.2009 09:19 default | skóre: 22 | Madrid
    Rozbalit Rozbalit vše Re: hash_map je zákeřná
    Například tento odstavec by podloužil téměř dokonale

    Tak tomuhle bych nerozumněl zas já. :-D

    12.7.2009 20:46 ivan
    Rozbalit Rozbalit vše Re: hash_map je zákeřná

    JJ, taky jsem se s tim setkal. Port aplikace na Solaris byl priserne pomalej. Po chvili googlovani jsme zjistili, ze na solarisu jsou dve STL knihovny. Standartni - plne kompatibilni, a "rozsirena", ktera pry plne neodpovida standartu. Ta prvni pouziva pro mapu vektor(nebo seznam) a ta "nestandartni" pouziva hash tabulku. Stacilo doinstalovat nejaky balik a prekompilovat aplikaci a vse jelo jak vino. Souhlasim s tim, ze to dost zakerna vec, ze zdrojaku vubec nemate sanci odvodit aplikace bude pomala.

     

    12.7.2009 20:44 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: hash_map je zákeřná
    Ten zápisek není špatný, jen takový překotný, syrový. O překladačích řekl bych něco málo tuším :-), takže s výrazy jako AST nebo signatura funkce nemám problémy, ale stejně jsem si to musel přečíst dvakrát, abych to pobral. Což zase může být tím, že nejsem C++ praktik :-) Ale určitě jsem zvědavý na další zápisky.
    Ještě na tom nejsem tak špatně, abych četl Viewegha.

    Založit nové vláknoNahoru

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