[Webkit-unassigned] [Bug 118616] New: Consider changing hashing algorithm

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=118616

           Summary: Consider changing hashing algorithm
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: Unspecified
        OS/Version: Unspecified
            Status: NEW
          Keywords: BlinkMergeCandidate
          Severity: Normal
          Priority: P2
         Component: Web Template Framework
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: rniwa at webkit.org
                CC: darin at apple.com, ben at meyerhome.net,
                    barraclough at apple.com


Perhaps we might want to consider merging https://chromium.googlesource.com/chromium/blink/+/e82c2bf6f26388a1ce423b953478a564932ac857
or come up with an alternative:

Improve WTF::HashTable performance by changing probing method

Our current HashTable implementation uses a linear probing system where
the delta is a hash of the given hash, which for integers requires
numerous shift and add operations to compute. This patch takes some
inspiration from CPython's dict implementation[1] to improve average
performance.

The new probing system is based off CPython's implementation -- we use a
linear congruential generator (x <- x*5+1), but for the first few probes
we also mix in the original hash (we shift this right by 5 each probe,
so we should use all the bits of the hash if the hash table is at least
32 objects big).

[1] http://svn.python.org/projects/python/trunk/Objects/dictobject.c

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.