unordered_map performance-tuning



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


Anmelden zum Antworten