RESOLVED WONTFIX118616
Consider changing hashing algorithm 
https://bugs.webkit.org/show_bug.cgi?id=118616
Summary Consider changing hashing algorithm
Ryosuke Niwa
Reported 2013-07-12 14:40:19 PDT
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
Attachments
Add attachment proposed patch, testcase, etc.
Ahmad Saleem
Comment 2 2022-10-05 00:29:43 PDT
Do we have anything to merge here since the patch was reverted and I don't know whether it landed later or anything related. Can we mark this as "RESOLVED WONTFIX"? Thanks!
Ryosuke Niwa
Comment 3 2022-10-05 00:32:11 PDT
This is won't fix. We don't do linear probing in HashTable. I guess that got diverged shortly after Blink fork? Regardless, this patch is quite irrelevant now.
Note You need to log in before you can comment on or make changes to this bug.