unordered_map performance-tuning



  • Hi Leute

    ich untersuche gerade die Performance der unordered_map im Vergleich zu einer hausinternen HashList.

    Leider geht die Map in dem Vergleich ziemlich unter ( Faktor 3 ). Daraus schließe ich, dass ich die Map noch nicht korrekt parametrisiert habe und das dort Verbesserungsbedarf besteht.

    Der Datenbestand besteht aus 1,8 Mio Datensätzen. Die Keys sind Strings mit jeweils 12 Zeichen.

    Initialisierung meiner Map:

    std::unordered_map<std::string, WPData*> mymap;
    for ( unsigned i = 0; i < Data.size(); ++i )
       mymap[ Data[ i ]->Key ] = Data[ i ];
    

    Suche mittels Key:

    WPData *wp = isinmap[ Data[ rand() % Data.size() ]->Key ];
    

    Anmerkung: Data ist ein Vektor, der die eigentlichen Objekte hält.

    Was kann ich noch besser machen? Kann ich Einfluss auf die interne Struktur des Baums nehmen, so dass meine Suchvorgänge noch schneller sind?



  • It0101 schrieb:

    ich untersuche gerade die Performance der unordered_map im Vergleich zu einer hausinternen HashList.

    Leider geht die Map in dem Vergleich ziemlich unter ( Faktor 3 ).

    Also die unordered_map ist 3mal langsamer als eure HashList? Was steckt dann da für eine Datenstruktur genau hinter?

    It0101 schrieb:

    Was kann ich noch besser machen? Kann ich Einfluss auf die interne Struktur des Baums nehmen, so dass meine Suchvorgänge noch schneller sind?

    unordered_map ist mit hoher Wahrscheinlichkeit konzeptionell als "Array von Listen" implementiert, wobei die Liste dann anhand des Hashwertes ausgewählt wird.

    Du könntest ja mal gucken, ob es an der Hashfunktion liegt und eure eigene Hashfunktion bei unordered_map verwenden. Vielleicht ist eure String-hashende Funktion einfach flotter als die der StandardLib-Implementierung.



  • Leider geht die Map in dem Vergleich ziemlich unter ( Faktor 3 ). Daraus schließe ich, dass ich die Map noch nicht korrekt parametrisiert habe und das dort Verbesserungsbedarf besteht.

    Das ist "normal", da unordered_set keinerlei weitere Einstellungsmoeglichkeiten bietet.



  • Das hört sich hier so an, als ob die unordered_XXX Container schlecht sind (schlecht == langsam hier)?! Oo



  • Zudem kann man mit load_factor und max_load_factor auch die Häufigkeit eines rehashes beeinflussen. Vielleicht kannst du damit etwas verändern.
    Was ist denn das langsame? Zugriff oder neueinfügen.

    Wahrscheinlich bringt die Veränderung der Hashfunktion am meisten, denn im gegensatz zur nativen Implementierung weißt du, dass ein String 12 Zeichen haben muss und möglicherweise gibt es noch andere Bestimmungen (nur ASCII, nur Großbuchstaben, keine whitespaces), die man für einen Geschwindigkeitsvorteil nutzen kann.



  • Im Prinzip ist unseres intern auch ein Array von Listen, allerdings ist das Array ca. 100000 Einträge breit, so dass bei 1,8mio durchschnittlich eben die Listen 18 Einträge lang sind...



  • Marthog schrieb:

    Zudem kann man mit load_factor und max_load_factor auch die Häufigkeit eines rehashes beeinflussen. Vielleicht kannst du damit etwas verändern.
    Was ist denn das langsame? Zugriff oder neueinfügen.

    Wahrscheinlich bringt die Veränderung der Hashfunktion am meisten, denn im gegensatz zur nativen Implementierung weißt du, dass ein String 12 Zeichen haben muss und möglicherweise gibt es noch andere Bestimmungen (nur ASCII, nur Großbuchstaben, keine whitespaces), die man für einen Geschwindigkeitsvorteil nutzen kann.

    Die Nativelösung kann auch beliebige HashKeys verarbeiten, ist allerdings kompliziert im Handling... Ich probiere erstmal das rehashing zu beeinflussen, denn meine Datenmenge ist statisch.

    Zudem will ich erstmal rausfinden, wie ausgeglichen die Map ist. Wenn im schlimmsten Fall alle Items in einer Liste liegen, ist der Performanceeinbruch erklärbar.



  • knivil schrieb:

    Das ist "normal", da unordered_set keinerlei weitere Einstellungsmoeglichkeiten bietet.

    Was ist das für ein Getrolle?

    @It0101: Wenn du in deiner map 100000 Einträge hast, dann gibt diese Zahl dem Konstruktor mit.

    std::unordered_map<std::string, WPData*> mymap(100000);
    

    Sonst schau dir mal die Hashfunktion und Vergleichsfunktion der eigenen map an, da geht sicher noch viel.



  • Achso, der Unterschied ist, dass euer Array bereits vorher gesetzte Größen hat.
    Benutze mal reserve, um der hashmap mitzuteilen, dass du Platz für 1.8 mio Elemente brauchst. Das erspart viele rehashes.



  • Ich messe ja in meiner Auswertung nur die "find" Aufrufe. Meine Datenmenge ist statisch, d.h. mir ist eigentlich (fast) egal wie lange er für das Aufbauen benötigt.



  • Probier mal soetwas:

    struct MyStringHash
    {
        // Aus Boost.    
        void HashCombine(std::size_t& first, std::size_t second)
        {
            first ^= second + 0x9e3779b9 + (first<<6) + (first>>2);
        }
    
        std::size_t operator()(std::string const& str) const
        {
            assert(str.length() == 12);
    
            struct AsInts
            {
                std::uint64_t first8;
                std::uint32_t last4;
            };
            static_assert(sizeof(AsInts) == 12, "");
            assert(str.data() % alignof(AsInts) == 0);
    
            AsInts const* ints = reinterpret_cast<AsInts const*>(str.data());
            std::size_t p1 = std::hash<std::uint64_t>()(ints.first8);
            std::size_t p2 = std::hash<std::uint32_t>()(ints.last4);
            HashCombine(p1, p2);
            return p1;
        }
    };
    


  • antitroll schrieb:

    knivil schrieb:

    Das ist "normal", da unordered_set keinerlei weitere Einstellungsmoeglichkeiten bietet.

    Was ist das für ein Getrolle

    Na dann erklaer mal, wie ich dem Container mitteile, dass meine Hashfunktion perfekt ist. Beispiel, ObjektId oder eben Zeiger. Bei unordered_set haengt es eigentlich nur an der Hashfunktion.

    Meine Erfahrung ist, dass ich mit anderen Hashtable-Implementierungen wesentlich besser gefahren bin, da die anderen eben besser auf das Problem, d.h. Elementtyp/Hashfunktion angepasst waren. Wie? Keine Ahnung, hab die beste halt ausgesucht. Auch sollte getestet werden, wieviel Perfomancevorsprung gegenueber std::set im Anwendunsfall besteht. Der ist meist verschmerzbar.

    Probier mal soetwas

    Fuer kurze Strings gibt es viele gute Hashfunktionen, z.B.:

    /* hash: compute hash value of string */
    unsigned int hash(char *str)
    {
       unsigned int h;
       unsigned char *p;
    
       h = 0;
       for (p = (unsigned char*)str; *p != '\0'; p++)
          h = MULTIPLIER * h + *p;
       return h; // or, h % ARRAY_SIZE;
    }
    
    Empirically, the values 31 and 37 have proven to be good choices for the
    multiplier in a hash function for ASCII strings.
    

    Weiterhin hat SSE 4.2 eine CRC-Instruction.

    AsInts const* ints = reinterpret_cast<AsInts const*>(str.data());
    

    Da schellen alle Alarmglocken bei mir. Erste Frage: Ist str.data() korrekt aligned? Zweite Frage: Was bei 32 oder 64 Bit Architekturen? Ich lasse mich gern belehren.



  • knivil schrieb:

    antitroll schrieb:

    knivil schrieb:

    Das ist "normal", da unordered_set keinerlei weitere Einstellungsmoeglichkeiten bietet.

    Was ist das für ein Getrolle

    Na dann erklaer mal, wie ich dem Container mitteile, dass meine Hashfunktion perfekt ist. Beispiel, ObjektId oder eben Zeiger. Bei unordered_set haengt es eigentlich nur an der Hashfunktion.

    Spielt es eine Rolle? Für Pointer ist die Map sowieso optimiert, weil das ein häufiges Einsatzszenario ist.
    std::unordered_set vom GCC ist tatsächlich auf integral_constants optimiert, das kannst du mit einer Eigenimplementierung nicht schlagen.

    bool __cache_hash_code =
    	     __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
    			   integral_constant<bool, !__is_final(_Hash)>,
    			   __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
    

    Für eine ID, die hochgezählt wird, eignet sich std::vector oft besser, da braucht es keine Hashmaps.

    knivil schrieb:

    Meine Erfahrung ist, dass ich mit anderen Hashtable-Implementierungen wesentlich besser gefahren bin, da die anderen eben besser auf das Problem, d.h. Elementtyp/Hashfunktion angepasst waren. Wie? Keine Ahnung, hab die beste halt ausgesucht. Auch sollte getestet werden, wieviel Perfomancevorsprung gegenueber std::set im Anwendunsfall besteht. Der ist meist verschmerzbar.

    Es kann sein, dass du diese Erfahrungen mit einer alten Version der Standard-Bibliothek gemacht hast? Die Klassen sind relativ neu und es gab ein paar Performance-Bugs in älteren GCCs. Vielleicht ist das auch das Problem des OPs.



  • knivil schrieb:

    AsInts const* ints = reinterpret_cast<AsInts const*>(str.data());
    

    Da schellen alle Alarmglocken bei mir. Erste Frage: Ist str.data() korrekt aligned? Zweite Frage: Was bei 32 oder 64 Bit Architekturen? Ich lasse mich gern belehren.

    In der Regel schon. Zumindestens mit std::allocator<> auf jeder mir bekannten Plattform/Implementierung.
    Aber dazu ist ja eine Zeile darüber das assert. 😉



  • Es kann sein, dass du diese Erfahrungen mit einer alten Version der Standard-Bibliothek gemacht hast?

    Sicher, da ich nicht andauernd Benchmarks mit jeder neuen Standardlibrary mache.



  • Ethon schrieb:

    In der Regel schon. Zumindestens mit std::allocator<> auf jeder mir bekannten Plattform/Implementierung.
    Aber dazu ist ja eine Zeile darüber das assert. 😉

    Es ist zwar garantiert, dass std::allocator<> so alloziert, dass es für alle Datentypen passt, aber es ist nicht klar, was std::string damit macht. Vielleicht verwendet er die Small-String-Optimierung oder speichert im ersten char des char-Arrays die Länge (wenn Länge <255, sonst Wert 255 und die nächsten 4 chars beinhalten die Länge).

    Das beste würde es vermutlich sein, eine eigene 12-Zeichen-String-Klasse zu schreiben. Die kann das garantieren und die hat dann auch nicht 3 Pointer Overhead mit 2 Subtraktion + 1 Vergleich Overhead beim Vergleich.



  • Aber dazu ist ja eine Zeile darüber das assert.

    Naja, dann kann man sich aber auch die Struktur sparen und gleich auf uin64_t* bzw. uint32_t* casten.



  • @It0101
    WAS ist langsamer, Insert oder Lookup oder Insert + Lookup?

    Und dann natürlich: ist der Vergleich überhaupt fair? Verwendet die selbstgebackene Hash-Map auch std::string als Key?
    Und handelt es sich auch wirklich um eine Hash-Map, oder eher ein Intrusive-Hash-Set?



  • hustbaer schrieb:

    @It0101
    Und dann natürlich: ist der Vergleich überhaupt fair? Verwendet die selbstgebackene Hash-Map auch std::string als Key?

    Ja. Sie verwendet die gleichen std::string-Keys wie die unordered_map die ich als Vergleich ausgesucht habe. Es werden auch beide mit der identischen Datenmenge getestet.

    Anmerkung: ich habe den Perfomancevergleich mit dem aktuellen CodeBlocks unter Windows gebaut. Daher kommt dort ein einigermaßen aktueller GCC-Compiler fuer Windows zum Einsatz. C++0x/11 Features wie chrono, auto und co. sind jedenfalls schon mit dabei.

    Ich denke, das Verfahren steht und fällt wirklich mit der Hashfunktion... D.h. für mich dass ich mal einige aussuchen und testen werde. Jedenfalls danke ich euch schonmal für euer Engagement.


  • Mod

    It0101 schrieb:

    Ich denke, das Verfahren steht und fällt wirklich mit der Hashfunktion... D.h. für mich dass ich mal einige aussuchen und testen werde. Jedenfalls danke ich euch schonmal für euer Engagement.

    Nimmst du denn nicht für beide die gleiche Hashfunktion? Sonst ist das reichlich unfair (für beide).


Log in to reply