{"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/comments/25553975","id":25553975,"diff_hunk":"@@ -248,70 +251,73 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> Bucket<K, V, M> {\n     /// this module.\n     pub fn peek(self) -> BucketState<K, V, M> {\n         match unsafe { *self.raw.hash } {\n-            EMPTY_BUCKET =>\n-                Empty(EmptyBucket {\n-                    raw: self.raw,\n-                    idx: self.idx,\n-                    table: self.table\n-                }),\n-            _ =>\n-                Full(FullBucket {\n-                    raw: self.raw,\n-                    idx: self.idx,\n-                    table: self.table\n-                })\n+            None => Empty(self.unsafe_cast()),\n+            _ => Full(self.unsafe_cast()),\n         }\n     }\n \n     /// Modifies the bucket pointer in place to make it point to the next slot.\n     pub fn next(&mut self) {\n-        // Branchless bucket iteration step.\n-        // As we reach the end of the table...\n-        // We take the current idx:          0111111b\n-        // Xor it by its increment:        ^ 1000000b\n-        //                               ------------\n-        //                                   1111111b\n-        // Then AND with the capacity:     & 1000000b\n-        //                               ------------\n-        // to get the backwards offset:      1000000b\n-        // ... and it's zero at all other times.\n-        let maybe_wraparound_dist = (self.idx ^ (self.idx + 1)) & self.table.capacity();\n-        // Finally, we obtain the offset 1 or the offset -cap + 1.\n-        let dist = 1 - (maybe_wraparound_dist as isize);\n-\n         self.idx += 1;\n \n+        let dist = if self.idx & (self.capacity - 1) == 0 {\n+            1i - self.capacity as int\n+        } else {\n+            1\n+        };","path":"src/libstd/collections/hash/table.rs","position":363,"original_position":363,"commit_id":"b7317cd6fe161bdbe47faf99a9f167294035b6b0","original_commit_id":"b7317cd6fe161bdbe47faf99a9f167294035b6b0","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"body":"being branchless isn't worth it?","created_at":"2015-02-28T03:53:27Z","updated_at":"2015-02-28T03:53:27Z","html_url":"https://github.com/rust-lang/rust/pull/21973#discussion_r25553975","pull_request_url":"https://api.github.com/repos/rust-lang/rust/pulls/21973","_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments/25553975"},"html":{"href":"https://github.com/rust-lang/rust/pull/21973#discussion_r25553975"},"pull_request":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/21973"}}},"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/21973","id":28748226,"html_url":"https://github.com/rust-lang/rust/pull/21973","diff_url":"https://github.com/rust-lang/rust/pull/21973.diff","patch_url":"https://github.com/rust-lang/rust/pull/21973.patch","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/21973","number":21973,"state":"open","locked":false,"title":"In-place growth for HashMap. Cleanup.","user":{"login":"pczarn","id":3356767,"avatar_url":"https://avatars.githubusercontent.com/u/3356767?v=3","gravatar_id":"","url":"https://api.github.com/users/pczarn","html_url":"https://github.com/pczarn","followers_url":"https://api.github.com/users/pczarn/followers","following_url":"https://api.github.com/users/pczarn/following{/other_user}","gists_url":"https://api.github.com/users/pczarn/gists{/gist_id}","starred_url":"https://api.github.com/users/pczarn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pczarn/subscriptions","organizations_url":"https://api.github.com/users/pczarn/orgs","repos_url":"https://api.github.com/users/pczarn/repos","events_url":"https://api.github.com/users/pczarn/events{/privacy}","received_events_url":"https://api.github.com/users/pczarn/received_events","type":"User","site_admin":false},"body":"Changes HashMap's memory layout from `[hhhh...KKKK...VVVV...]` to `[KVKVKVKV...hhhh...]`. This makes in-place growth easy to implement (and efficient).\r\n\r\nThe removal of `find_with_or_insert_with` has made more cleanup possible.\r\n\r\n20 benchmark runs, averaged:\r\n```\r\n                           before         after\r\nbench::find_existing       40573.50 ns    41227.65 ns\r\nbench::find_nonexisting    41815.45 ns    42362.60 ns\r\nbench::get_remove_insert     197.85 ns      198.60 ns\r\nbench::grow_by_insertion     171.05 ns      154.05 ns\r\nbench::hashmap_as_queue      112.85 ns      112.65 ns\r\nbench::new_drop               79.40 ns       79.20 ns\r\nbench::new_insert_drop       179.40 ns      149.05 ns\r\n```\r\nthanks to @Gankro for the Entry interface, and to @thestinger for improving jemalloc's in-place realloc!\r\ncc @cgaebel\r\nr? @Gankro ","created_at":"2015-02-05T18:24:03Z","updated_at":"2015-02-28T03:53:27Z","closed_at":null,"merged_at":null,"merge_commit_sha":"be0a2ed965b587bc62f973ea3c3d97b74ab9816e","assignee":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/rust-lang/rust/pulls/21973/commits","review_comments_url":"https://api.github.com/repos/rust-lang/rust/pulls/21973/comments","review_comment_url":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/21973/comments","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/b7317cd6fe161bdbe47faf99a9f167294035b6b0","head":{"label":"pczarn:hash_map-mem-layout","ref":"hash_map-mem-layout","sha":"b7317cd6fe161bdbe47faf99a9f167294035b6b0","user":{"login":"pczarn","id":3356767,"avatar_url":"https://avatars.githubusercontent.com/u/3356767?v=3","gravatar_id":"","url":"https://api.github.com/users/pczarn","html_url":"https://github.com/pczarn","followers_url":"https://api.github.com/users/pczarn/followers","following_url":"https://api.github.com/users/pczarn/following{/other_user}","gists_url":"https://api.github.com/users/pczarn/gists{/gist_id}","starred_url":"https://api.github.com/users/pczarn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pczarn/subscriptions","organizations_url":"https://api.github.com/users/pczarn/orgs","repos_url":"https://api.github.com/users/pczarn/repos","events_url":"https://api.github.com/users/pczarn/events{/privacy}","received_events_url":"https://api.github.com/users/pczarn/received_events","type":"User","site_admin":false},"repo":{"id":17574759,"name":"rust","full_name":"pczarn/rust","owner":{"login":"pczarn","id":3356767,"avatar_url":"https://avatars.githubusercontent.com/u/3356767?v=3","gravatar_id":"","url":"https://api.github.com/users/pczarn","html_url":"https://github.com/pczarn","followers_url":"https://api.github.com/users/pczarn/followers","following_url":"https://api.github.com/users/pczarn/following{/other_user}","gists_url":"https://api.github.com/users/pczarn/gists{/gist_id}","starred_url":"https://api.github.com/users/pczarn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pczarn/subscriptions","organizations_url":"https://api.github.com/users/pczarn/orgs","repos_url":"https://api.github.com/users/pczarn/repos","events_url":"https://api.github.com/users/pczarn/events{/privacy}","received_events_url":"https://api.github.com/users/pczarn/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/pczarn/rust","description":"a safe, concurrent, practical language","fork":true,"url":"https://api.github.com/repos/pczarn/rust","forks_url":"https://api.github.com/repos/pczarn/rust/forks","keys_url":"https://api.github.com/repos/pczarn/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pczarn/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pczarn/rust/teams","hooks_url":"https://api.github.com/repos/pczarn/rust/hooks","issue_events_url":"https://api.github.com/repos/pczarn/rust/issues/events{/number}","events_url":"https://api.github.com/repos/pczarn/rust/events","assignees_url":"https://api.github.com/repos/pczarn/rust/assignees{/user}","branches_url":"https://api.github.com/repos/pczarn/rust/branches{/branch}","tags_url":"https://api.github.com/repos/pczarn/rust/tags","blobs_url":"https://api.github.com/repos/pczarn/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pczarn/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pczarn/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/pczarn/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pczarn/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/pczarn/rust/languages","stargazers_url":"https://api.github.com/repos/pczarn/rust/stargazers","contributors_url":"https://api.github.com/repos/pczarn/rust/contributors","subscribers_url":"https://api.github.com/repos/pczarn/rust/subscribers","subscription_url":"https://api.github.com/repos/pczarn/rust/subscription","commits_url":"https://api.github.com/repos/pczarn/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/pczarn/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/pczarn/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/pczarn/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/pczarn/rust/contents/{+path}","compare_url":"https://api.github.com/repos/pczarn/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pczarn/rust/merges","archive_url":"https://api.github.com/repos/pczarn/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pczarn/rust/downloads","issues_url":"https://api.github.com/repos/pczarn/rust/issues{/number}","pulls_url":"https://api.github.com/repos/pczarn/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/pczarn/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/pczarn/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pczarn/rust/labels{/name}","releases_url":"https://api.github.com/repos/pczarn/rust/releases{/id}","created_at":"2014-03-09T22:00:17Z","updated_at":"2014-07-25T23:29:16Z","pushed_at":"2015-02-27T17:23:28Z","git_url":"git://github.com/pczarn/rust.git","ssh_url":"git@github.com:pczarn/rust.git","clone_url":"https://github.com/pczarn/rust.git","svn_url":"https://github.com/pczarn/rust","homepage":"http://www.rust-lang.org","size":243190,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"rust-lang:master","ref":"master","sha":"bd0d8e47e53f25bbd50418a0f117973c366c1b08","user":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":724712,"name":"rust","full_name":"rust-lang/rust","owner":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/rust-lang/rust","description":"a safe, concurrent, practical language","fork":false,"url":"https://api.github.com/repos/rust-lang/rust","forks_url":"https://api.github.com/repos/rust-lang/rust/forks","keys_url":"https://api.github.com/repos/rust-lang/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-lang/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-lang/rust/teams","hooks_url":"https://api.github.com/repos/rust-lang/rust/hooks","issue_events_url":"https://api.github.com/repos/rust-lang/rust/issues/events{/number}","events_url":"https://api.github.com/repos/rust-lang/rust/events","assignees_url":"https://api.github.com/repos/rust-lang/rust/assignees{/user}","branches_url":"https://api.github.com/repos/rust-lang/rust/branches{/branch}","tags_url":"https://api.github.com/repos/rust-lang/rust/tags","blobs_url":"https://api.github.com/repos/rust-lang/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-lang/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-lang/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-lang/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-lang/rust/languages","stargazers_url":"https://api.github.com/repos/rust-lang/rust/stargazers","contributors_url":"https://api.github.com/repos/rust-lang/rust/contributors","subscribers_url":"https://api.github.com/repos/rust-lang/rust/subscribers","subscription_url":"https://api.github.com/repos/rust-lang/rust/subscription","commits_url":"https://api.github.com/repos/rust-lang/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-lang/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-lang/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-lang/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/rust-lang/rust/contents/{+path}","compare_url":"https://api.github.com/repos/rust-lang/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-lang/rust/merges","archive_url":"https://api.github.com/repos/rust-lang/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-lang/rust/downloads","issues_url":"https://api.github.com/repos/rust-lang/rust/issues{/number}","pulls_url":"https://api.github.com/repos/rust-lang/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-lang/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-lang/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-lang/rust/labels{/name}","releases_url":"https://api.github.com/repos/rust-lang/rust/releases{/id}","created_at":"2010-06-16T20:39:03Z","updated_at":"2015-02-28T02:21:53Z","pushed_at":"2015-02-28T03:37:21Z","git_url":"git://github.com/rust-lang/rust.git","ssh_url":"git@github.com:rust-lang/rust.git","clone_url":"https://github.com/rust-lang/rust.git","svn_url":"https://github.com/rust-lang/rust","homepage":"http://www.rust-lang.org","size":491374,"stargazers_count":9554,"watchers_count":9554,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1842,"mirror_url":null,"open_issues_count":1973,"forks":1842,"open_issues":1973,"watchers":9554,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/21973"},"html":{"href":"https://github.com/rust-lang/rust/pull/21973"},"issue":{"href":"https://api.github.com/repos/rust-lang/rust/issues/21973"},"comments":{"href":"https://api.github.com/repos/rust-lang/rust/issues/21973/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/21973/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/21973/commits"},"statuses":{"href":"https://api.github.com/repos/rust-lang/rust/statuses/b7317cd6fe161bdbe47faf99a9f167294035b6b0"}}}}