Bug 19072 – Object.toHash and typeid(void*).getHash(&ptr) should be more varied in their low bits

Status
RESOLVED
Resolution
FIXED
Severity
enhancement
Priority
P1
Component
druntime
Product
D
Version
D2
Platform
All
OS
All
Creation time
2018-07-09T19:52:26Z
Last change time
2018-07-22T17:57:21Z
Assigned to
No Owner
Creator
Nathan S.

Comments

Comment #0 by n8sh.secondary — 2018-07-09T19:52:26Z
The low bits of `Object.toHash` are insufficiently varied. Depending on the platform the bottom 4, 3, or 2 bits of the result will always be zero. This is bad because the low bits of a hash code are typically the most significant for hashtable implementations. D's builtin AA deals with this and other potential defects by rehashing the hash codes it receives. Some 3rd party hashtable implementations do the same, but others assume that keys with a defined `toHash` have reasonable hashcodes that can be used without need for further mixing. Fixing this would not be hard. The same can be done for raw pointers; although it will not always be necessary for them the cost is low and it will frequently be a benefit.
Comment #1 by github-bugzilla — 2018-07-22T17:57:20Z
Commits pushed to master at https://github.com/dlang/druntime https://github.com/dlang/druntime/commit/710adf3f5d7d15f6024266a584de8ab1feb84fb3 Fix Issue 19072 - Object.toHash and typeid(void*).getHash(&ptr) should be more varied in their low bits The low bits of Object.toHash are insufficiently varied. Depending on the platform the bottom 4, 3, or 2 bits of the result will always be zero. This is bad because the low bits of a hash code are typically the most significant for hashtable implementations. D's builtin AA deals with this and other potential defects by rehashing the hash codes it receives. Some 3rd party hashtable implementations do the same, but others assume that keys with a defined toHash have reasonable hashcodes that can be used without need for further mixing. Fixing this is not hard and not computationally expensive. This PR also does a similar thing for raw pointers. Although it will not always be necessary for them the cost is low and it will frequently be a benefit. https://github.com/dlang/druntime/commit/b70774bc00a8e837eef05bbd2680ddc2fb2d62ea Merge pull request #2247 from n8sh/object-hash-19072 Fix Issue 19072 - Object.toHash and typeid(void*).getHash(&ptr) should be more varied in their low bits merged-on-behalf-of: Petar Kirov <[email protected]>