Bug 118616
| Summary: | Consider changing hashing algorithm | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | Ryosuke Niwa <rniwa> |
| Component: | Web Template Framework | Assignee: | Nobody <webkit-unassigned> |
| Status: | RESOLVED WONTFIX | ||
| Severity: | Normal | CC: | ahmad.saleem792, ap, barraclough, bfulgham, darin |
| Priority: | P2 | Keywords: | BlinkMergeCandidate |
| Version: | 528+ (Nightly build) | ||
| Hardware: | Unspecified | ||
| OS: | Unspecified | ||
Ryosuke Niwa
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. |
Ryosuke Niwa
Reverted in https://chromium.googlesource.com/chromium/blink/+/8bb886cfc733154d380a9f9019700c0703aff3d7.
Ahmad Saleem
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
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.