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 16:33 | Zajímavý software

    Sniffnet je multiplatformní aplikace pro sledování internetového provozu. Ke stažení pro Windows, macOS i Linux. Jedná se o open source software. Zdrojové kódy v programovacím jazyce Rust jsou k dispozici na GitHubu. Vývoj je finančně podporován NLnet Foundation.

    Ladislav Hagara | Komentářů: 0
    dnes 12:33 | Nová verze

    Byl vydán Debian Installer Trixie RC 2, tj. druhá RC verze instalátoru Debianu 13 s kódovým názvem Trixie.

    Ladislav Hagara | Komentářů: 0
    dnes 03:33 | Komunita

    Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za červen (YouTube).

    Ladislav Hagara | Komentářů: 0
    dnes 02:33 | Nová verze

    Libreboot (Wikipedie) – svobodný firmware nahrazující proprietární BIOSy, distribuce Corebootu s pravidly pro proprietární bloby – byl vydán ve verzi 25.06 "Luminous Lemon". Přidána byla podpora desek Acer Q45T-AM a Dell Precision T1700 SFF a MT. Současně byl ve verzi 25.06 "Onerous Olive" vydán také Canoeboot, tj. fork Librebootu s ještě přísnějšími pravidly.

    Ladislav Hagara | Komentářů: 0
    dnes 01:33 | Komunita

    Licence GNU GPLv3 o víkendu oslavila 18 let. Oficiálně vyšla 29. června 2007. Při té příležitosti Richard E. Fontana a Bradley M. Kuhn restartovali, oživili a znovu spustili projekt Copyleft-Next s cílem prodiskutovat a navrhnout novou licenci.

    Ladislav Hagara | Komentářů: 0
    včera 16:55 | Nová verze

    Svobodný nemocniční informační systém GNU Health Hospital Information System (HIS) (Wikipedie) byl vydán ve verzi 5.0 (Mastodon).

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

    Open source mapová a navigační aplikace OsmAnd (OpenStreetMap Automated Navigation Directions, Wikipedie, GitHub) oslavila 15 let.

    Ladislav Hagara | Komentářů: 0
    včera 11:55 | Zajímavý software

    Vývojář Spytihněv, autor počítačové hry Hrot (Wikipedie, ProtonDB), pracuje na nové hře Brno Transit. Jedná se o příběhový psychologický horor o strojvedoucím v zácviku, uvězněném v nejzatuchlejším metru východně od všeho, na čem záleží. Vydání je plánováno na čtvrté čtvrtletí letošního roku.

    Ladislav Hagara | Komentářů: 38
    1.7. 18:22 | IT novinky

    V uplynulých dnech byla v depu Českých drah v Brně-Maloměřicích úspěšně dokončena zástavba speciální antény satelitního internetu Starlink od společnosti SpaceX do jednotky InterPanter 660 004 Českých drah. Zástavbu provedla Škoda Group. Cestující se s InterPanterem, vybaveným vysokorychlostním satelitním internetem, setkají například na linkách Svitava Brno – Česká Třebová – Praha nebo Moravan Brno – Břeclav – Přerov – Olomouc.

    Ladislav Hagara | Komentářů: 21
    1.7. 13:11 | Nová verze

    Byla vydána nová verze 8.7.0 správce sbírky fotografií digiKam (Wikipedie). Přehled novinek i s náhledy v oficiálním oznámení (NEWS). Nejnovější digiKam je ke stažení také jako balíček ve formátu AppImage. Stačí jej stáhnout, nastavit právo ke spuštění a spustit.

    Ladislav Hagara | Komentářů: 0
    Jaký je váš oblíbený skriptovací jazyk?
     (59%)
     (28%)
     (7%)
     (2%)
     (0%)
     (1%)
     (3%)
    Celkem 344 hlasů
     Komentářů: 16, poslední 8.6. 21:05
    Rozcestník

    hash_map je zákeřná

    11.7.2009 03:59 | Přečteno: 1478× | 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.