Hash 4 Integers



  • Hallo,
    ich suche derzeit nach der besten Möglichkeit, 4 64-bit integers (Pointer) auf einen einzelnen anderen Pointer zu mappen.
    Mein derzeitiges Vorgehen ist:

    using hash_type = std::array<uintptr_t, 4>;
    class type { };
    std::map<hash_type, type*> > map;
    hash_type hash(type* n0, type* n1, type* n2, type* n3)
    {
    	hash_type h = { reinterpret_cast<uintptr_t>(n0), reinterpret_cast<uintptr_t>(n1),
    					reinterpret_cast<uintptr_t>(n2), reinterpret_cast<uintptr_t>(n3) };
    	return h;
    }
    

    Mein Problem bei diesem Vorgehen ist allerdings, dass die Vergleiche der Arrays zu langsam sind, da die Map durchaus eine Größe >10000 erreicht und die Performance bei dem Projekt leider nicht außer Acht zu lassen ist.
    Deshalb ist meine Frage, ob euch eine bessere Möglichkeit einfällt (natürlich möglichst kollisionsfrei) die 4 Pointer auf nur einen zu mappen.
    Oder gibt es gar keine andere Option?

    Danke!



  • Boost bietet hierzu das:

    https://www.boost.org/doc/libs/1_55_0/doc/html/hash/combine.html

    Wie gut oder schnell das ist, weiß ich leider nicht.



  • Vor einiger Zeit hatte ich mit Pointer-Hashing herumgespielt, allerdings nur für 1 Pointer. Da hatte sich herausgestellt, dass es klug ist, nicht direkt den Pointerwert zu verwenden, sondern die "Nullen am Ende" wegzuschieben. Also reinterpret_cast<uintptr_t>(n0) / alignof(type) zu nehmen. Kannst du ja auch mal ausprobieren, vielleicht in Kombination mit hash_combine. War in diesem Forum, ich finde bei der Suche nach mir und alignof aber gerade nichts mit der Forumssuche.

    Ansonsten noch die Frage, ob std::map eine gute Idee ist. Wie wärs mit std::unorderd_map? Oder gar google::dense_hash_map? Oder noch andere Implementierungen.

    Mir fällt gerade auf in deinem Code auf, dass du ja überhaupt gar nicht hashst. Also wäre das vermutlich der nullte Schritt.



  • Das hash_combine aus boost sieht tatsächlich ganz interessant aus, ich schaue es mir an. Danke.

    @wob
    Ich habe leider immer nur eine Null hinten. Klar kann ich die Abschneiden, aber das löst leider nocht nicht ganz das Problem.
    Ein weiterer Ansatz von mir wäre sonst, dass ich einmal versuche, die Pointer in 16-bit Werte zu hashen und die einfach in einen 64-bit int packe. Müsste ich einmal ausprobieren.
    Mein Problem ist mit std::unordered_map, dass ich dafür ja eben eine Hash-Funktion brauche und die suche ich gerade. Dass meine Funktion hash() nichts hasht ist mir auch klar, das war eigentlich nur als Übergangslösung gedacht und hat sich länger gehalten als gedacht, jetzt muss aber ein Ersatz her.
    Die google::dense_hash_map kenne ich zugegebenermaßen nicht, muss ich mir einmal ansehen. Dabei werde ich aber vermutlich das gleiche Problem wie bei der std::unordered_map haben.

    Und ich habe es mir noch einmal genauer angeschaut: die Map wird üblicherweise ca. 80000 Elemente groß. Da sind 16-bit pro Pointer vermutlich zu wenig.



  • Für was brauchst du eine eigene hash funktion für deine objekte?
    Bei std::map/unordered_map ist der key (welcher gehashed wird) separat zum value (mit dem nichts gemacht wird).
    Eine hash funktion für eigene objekte sind nur für container ala std::set/unordered_set notwendig



  • @firefly Aber die 4 Pointer sind ja der Key. Und dafür gibt es keine standardmäßige Hashfunktion, welche bei einer std::unordered_map notwendig ist (nicht hingegen bei einer std::map).



  • Ich habe nun mit der hier erwähnten CRC16-Funktion aus dem Linux-Kernel die 4 Pointer zu einem 64-bit int umgewandelt.
    In einer normalen std::map erhalte ich damit als Key jedoch ca. 45% Kollisionen. In einer std::unordered_map, wie ich es jetzt gerade dann habe, wird das aber ja durch eine Liste für jeden Hashwert mit dem Array als Key abgefangen.
    Damit habe ich tatsächlich einen kleinen Performanceschub erzielt, auch wenn durchaus noch Steigerungspotential da ist. Vermutlich ließe sich durch einen besseren Hashalgorithmus noch einmal mehr herausholen. Hat dafür noch jemand eine Idee?



  • @unterfliege Was sprach denn gegen hash_combine und für das crc16? Bzw. wie waren da die Performaceunterschiede? Und wie sieht sein Zugriffsmuster aus? Also baust du die map auf und guckst oft rein oder löscht du auch oft was raus? Stehen die 4 Pointer ansonsten in irgendeiner Relation zueinander? Ich finde solche Themen immer spannend 🙂



  • Ich hatte hash_combine irgendwie wieder verdrängt, weil ich zwischenzeitlich noch ein anderes Problem hatte.
    Ich habe es nun einmal implementiert und es ist vermutlich tatsächlich schneller als crc16, wobei ich noch genauere Tests durchführen muss.
    Was mich sehr überrascht ist, dass ich 0% Kollisionen hatte bei 70000 Elementen. Also eine beträchtliche Steigerung im Vergleich zu CRC16. Einziger Nachteil daran ist natürlich die zusätzliche Dependency, da das Projekt ansonsten bis jetzt boost-frei war. Aber das ist vermutlich verkraftbar. Was ich noch überlege, ist, ob ich nicht das Array als Key entferne oder vllt. auch zwei Hashes in unterschiedlicher Reihenfolge nehme als Sicherheit, wenn ich in weiteren Tests weiterhin auch bei 100000 Elementen 0% Kollisionen habe. Könnte vllt. noch einmal einen kleinen Performanceschub geben, wobei es bereits so eine Verbesserung von min. 70% darstellt (wie gesagt: um das definitiv sagen zu können sind weitere Tests notwendig).



  • Du brauchst dafür boost nicht einzubinden. Schau dir den Code von hash_combine an, das sind 1-2 Zeilen.



  • Und noch ein kleiner Tip zu "schau dir den Code an": step einfach in Debugger rein. Erleichtert das Finden des Codes ungemein. Speziell bei so Sachen wie boost::hash_value (welches von boost::hash_combine aufgerufen wird) wo es nur ca. 1 Mio. Overloads gibt die dann mit diversen SFINAE Hilfsklassen enabled/disabled werden und...

    OK, gibt natürlich schlimmeres als boost::hash_value, aber übersichtlich ist es auf jeden Fall nicht.



  • Ja, ich habe mir den Code bereits angesehen und der sollte tatsächlich ziemlich einfach zu kopieren sein. Weiß da jemand wie das mit Copyright aussieht?
    Ich bin gerade aber sowieso an anderer Stelle am Überlegen, boost zu verwenden, wo es nicht so einfach herauskopierbar wäre. Muss ich mir beides noch einmal ansehen.
    Danke auf jeden Fall für eure Hilfe.



  • @unterfliege sagte in Hash 4 Integers:

    Was ich noch überlege, ist, ob ich nicht das Array als Key entferne oder vllt. auch zwei Hashes in unterschiedlicher Reihenfolge nehme als Sicherheit

    Du hast irgendwie komische Überlegungen. Du brauchst das Array gar nicht, warum hast du es denn da genutzt? Warum brauchst du irgendwas "als Sicherheit"?



  • @tggc Wenn der Hash gut genug wäre und auf mehrere 100000 Arrays keine Kollisionen liefert, wäre der Geschwindigkeitsvorteil eventuell die Gefahr einer Kollision wert.
    Aber natürlich brauche ich am Anfang schon die Pointer im Array, aber eben nur um die Hashwerte zu erzeugen.
    Die Idee wurde aber sowieso wieder verworfen.


  • Global Moderator

    @unterfliege sagte in Hash 4 Integers:

    @tggc Wenn der Hash gut genug wäre und auf mehrere 100000 Arrays keine Kollisionen liefert, wäre der Geschwindigkeitsvorteil eventuell die Gefahr einer Kollision wert.
    Aber natürlich brauche ich am Anfang schon die Pointer im Array, aber eben nur um die Hashwerte zu erzeugen.
    Die Idee wurde aber sowieso wieder verworfen.

    Du weißt schon, dass eine Kollision kein Beinbruch für eine Map ist? Funktioniert wunderbar und ist dann halt mal minimal langsamer. Es ist wahrscheinlich keine gute Idee, bei jedem Zugriff doppelt und dreifachen Rechenaufwand zu betreiben, um die Kollisionswahrscheinlichkeit von 1:100000 auf 1:1000000 zu senken. Den Aufwand einer besseren Hashfunktion möchtest du betreiben, wenn du so viele Werte hast, dass eine Kollision der Normalfall anstatt der Ausnahmefall wird.



  • @seppj Wenn ich den Hashwert als Key nehme, dann sind Kollisionen natürlich relevant. Dann habe ich schließlich nicht mehr die eigentlich wesentlichen Pointer zum Vergleich. Und wenn die Map keine weiteren Informationen außer dem Hashwert hat, dann kann sie auch nichts mehr machen, da sie bei Kollisionen keine Unterschiede erkennen kann.
    Diese Idee wurde aber ja schließlich sowieso schon verworfen. Da ist es wohl sinnvoller, sich nach einer besseren std::unordered_map umzusehen, wie die schon vorgeschlagene Googles dense_hash_map.



  • @unterfliege Hast du inzwischen denn std::unordered_map überhaupt mal ausprobiert? Die Idee "Hashwert als Key" ist seltsam, aber zum Glück schon verworfen.



  • @wob Ja, natürlich, damit arbeite ich natürlich schon die ganze Zeit, seitdem ich die Hash-Funktion verwende. Klappt mit dem boost-Code auch sehr gut.
    War ja auch nur eine Idee, da ich anfangs tatsächlich 0.0% Kollisionen hatte, war aber vermutlich nur Glück.
    Nun habe ich gerade eben auch noch einmal profilt und die map ist damit gerade nur noch die drittgrößte Bremse. Ich werde mich also noch an andere Optimierungen machen und anschließend noch einmal der Map zuwenden und z.B. die erwähnte dense_hash_map versuchen oder eine andere Implementation.