{"action":"created","issue":{"url":"https://api.github.com/repos/dlang/druntime/issues/2247","repository_url":"https://api.github.com/repos/dlang/druntime","labels_url":"https://api.github.com/repos/dlang/druntime/issues/2247/labels{/name}","comments_url":"https://api.github.com/repos/dlang/druntime/issues/2247/comments","events_url":"https://api.github.com/repos/dlang/druntime/issues/2247/events","html_url":"https://github.com/dlang/druntime/pull/2247","id":339586516,"node_id":"MDExOlB1bGxSZXF1ZXN0MjAwMjAzODU1","number":2247,"title":"Fix Issue 19072 - Object.toHash and typeid(void*).getHash(&ptr) should be more varied in their low bits","user":{"login":"n8sh","id":21227491,"node_id":"MDQ6VXNlcjIxMjI3NDkx","avatar_url":"https://avatars2.githubusercontent.com/u/21227491?v=4","gravatar_id":"","url":"https://api.github.com/users/n8sh","html_url":"https://github.com/n8sh","followers_url":"https://api.github.com/users/n8sh/followers","following_url":"https://api.github.com/users/n8sh/following{/other_user}","gists_url":"https://api.github.com/users/n8sh/gists{/gist_id}","starred_url":"https://api.github.com/users/n8sh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/n8sh/subscriptions","organizations_url":"https://api.github.com/users/n8sh/orgs","repos_url":"https://api.github.com/users/n8sh/repos","events_url":"https://api.github.com/users/n8sh/events{/privacy}","received_events_url":"https://api.github.com/users/n8sh/received_events","type":"User","site_admin":false},"labels":[{"id":638910588,"node_id":"MDU6TGFiZWw2Mzg5MTA1ODg=","url":"https://api.github.com/repos/dlang/druntime/labels/Enhancement","name":"Enhancement","color":"0052cc","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2018-07-09T19:59:05Z","updated_at":"2018-07-10T15:24:40Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/dlang/druntime/pulls/2247","html_url":"https://github.com/dlang/druntime/pull/2247","diff_url":"https://github.com/dlang/druntime/pull/2247.diff","patch_url":"https://github.com/dlang/druntime/pull/2247.patch"},"body":"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.\r\n\r\nFixing 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."},"comment":{"url":"https://api.github.com/repos/dlang/druntime/issues/comments/403863307","html_url":"https://github.com/dlang/druntime/pull/2247#issuecomment-403863307","issue_url":"https://api.github.com/repos/dlang/druntime/issues/2247","id":403863307,"node_id":"MDEyOklzc3VlQ29tbWVudDQwMzg2MzMwNw==","user":{"login":"n8sh","id":21227491,"node_id":"MDQ6VXNlcjIxMjI3NDkx","avatar_url":"https://avatars2.githubusercontent.com/u/21227491?v=4","gravatar_id":"","url":"https://api.github.com/users/n8sh","html_url":"https://github.com/n8sh","followers_url":"https://api.github.com/users/n8sh/followers","following_url":"https://api.github.com/users/n8sh/following{/other_user}","gists_url":"https://api.github.com/users/n8sh/gists{/gist_id}","starred_url":"https://api.github.com/users/n8sh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/n8sh/subscriptions","organizations_url":"https://api.github.com/users/n8sh/orgs","repos_url":"https://api.github.com/users/n8sh/repos","events_url":"https://api.github.com/users/n8sh/events{/privacy}","received_events_url":"https://api.github.com/users/n8sh/received_events","type":"User","site_admin":false},"created_at":"2018-07-10T15:24:40Z","updated_at":"2018-07-10T15:24:40Z","author_association":"MEMBER","body":"BTW the original version of this PR used different shift sizes for different known malloc alignments. I removed this because it seemed to me like overengineering, and taking a step back it wasn't clear if in practice -- aside from the toy problem of placing into a tiny hash table keys that all have minimum `classInstanceSize` and are allocated in sequence -- there would be a benefit compared to a constant xor-shift of 4.\r\n\r\n<details>\r\n<summary>Discarded version</summary>\r\n\r\n```d\r\nsize_t toHash() @trusted nothrow\r\n{\r\n    const addr = cast(size_t) cast(void*) this;\r\n    // The bottom log2((void*).alignof) bits of the address will\r\n    // always be 0. Moreover it is likely that each Object is\r\n    // allocated with a separate call to malloc.\r\n    enum log2PtrAlign = (size_t.sizeof >= 8 || (void*).alignof >= 8) ? 3 : 2;\r\n    version(ARM) { enum isARM32 = true; } else { enum isARM32 = false; }\r\n    version(MIPS32) { enum isMIPS32 = true; } else { enum isMIPS32 = false; }\r\n\r\n    // 16 byte aligned malloc:\r\n    version (OSX)\r\n        return addr ^ (addr >>> 4);\r\n    else version (CRuntime_Musl)\r\n        return addr ^ (addr >>> 4);\r\n    else version (OpenBSD)\r\n        return addr ^ (addr >>> 4);\r\n    else version (DragonFlyBSD)\r\n        return addr ^ (addr >>> 4);\r\n    // (size_t.sizeof * 2) aligned malloc:\r\n    else version (Windows)\r\n        return addr ^ (addr >>> (log2PtrAlign + 1));\r\n    else version (CRuntime_Glibc)\r\n        return addr ^ (addr >>> (log2PtrAlign + 1));\r\n    // (size_t.sizeof) aligned malloc:\r\n    else version (CRuntime_UClibc)\r\n        return addr ^ (addr >>> log2PtrAlign);\r\n    // NetBSD & FreeBSD:\r\n    else version (NetBSD)\r\n        return addr ^ (addr >>> (4 - uint(isARM32)));\r\n    else version (FreeBSD)\r\n        return addr ^ (addr >>> (4 - uint(isARM32 || isMIPS32)));\r\n    // Otherwise we only know that the log2(size_t.sizeof) low bits\r\n    // are always zero. We shift 1 more than this because shifting\r\n    // by too little will cause every hash to be even, while shifting\r\n    // by \"too much\" is not particularly bad.\r\n    else\r\n        return addr ^ (addr >>> (log2PtrAlign + 1));\r\n}\r\n```\r\n</details>"}}
{"actor":{"display_login":"n8sh"}}