hash_map je zákeřná

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

Komentáře

[Pilgrim]

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).

[Deleted [8409]]

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]

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).

[podlesh]

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]

Například tento odstavec by podloužil téměř dokonale

Tak tomuhle bych nerozumněl zas já.

[ivan]

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.

 

[Ladicek]

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.