Uploaded image for project: 'Qt'
  1. Qt
  2. QTBUG-29009

integer qHash functions are far from ideal

    XMLWordPrintable

Details

    • Suggestion
    • Resolution: Done
    • P3: Somewhat important
    • 6.0
    • 4.8.1
    • None
    • Win7

    • 735fd68dacdf25e51691d2e804d5e9db643e7833 (qt/qtbase/dev)

    Description

      When trying to implement a 3D space hashing object in Qt (4.8.1) I noticed performance issues when using QHash with 64bit integer keys. The keys were a simply mash up of the x,y,z coordinates of an object (x<<32 + y<<16 + z) where (x,y,z) < 65536. The best I could achieve was ~800,000 hash insertion per second (2.2GHz i7 laptop, OpenGL rendering was being performed as well). A QMap implementation was actually faster despite O(nlogn) vs. QHash's amortized O(1)!

      I used a custom hash (MurmurHash3) for my objects (using the same source keys) and have over doubled performance. This leads me to believe that Qt's qHash algorithm for 64bit integers is terrible, resulting in far from optimal hash performance.

      Attachments

        No reviews matched the request. Check your Options in the drop-down menu of this sections header.

        Activity

          People

            laknoll Lars Knoll
            drew.mikola@gmail.com Drew Mikola
            Maurice Kalinowski Maurice Kalinowski
            Alex Blasche Alex Blasche
            Votes:
            2 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved:

              Gerrit Reviews

                There are no open Gerrit changes