{"action":"created","comment":{"url":"https://api.github.com/repos/mimblewimble/grin/pulls/comments/217747228","pull_request_review_id":155540682,"id":217747228,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIxNzc0NzIyOA==","diff_hunk":"@@ -1224,27 +1224,45 @@ fn input_pos_to_rewind(\n \t\t\thead_header.height,\n \t\t\tblock_header.height\n \t\t);\n-\t\treturn Ok(bitmap);\n+\t\treturn Ok(Bitmap::create());\n \t}\n \n-\t//\n-\t// TODO - rework this loop to use Bitmap::fast_or() on a vec of bitmaps.\n-\t//\n-\tloop {\n-\t\tif current == block_header.hash() {\n-\t\t\tbreak;\n+\tlet bitmap_fast_or = |b_res, block_input_bitmaps: &mut Vec<Bitmap>| -> Option<Bitmap> {\n+\t\tif let Some(b) = b_res {\n+\t\t\tblock_input_bitmaps.push(b);\n+\t\t\tif block_input_bitmaps.len() < 256 {","path":"chain/src/txhashset.rs","position":27,"original_position":27,"commit_id":"996883e7191c588505fe4fa4b4b61cc2848753b1","original_commit_id":"996883e7191c588505fe4fa4b4b61cc2848753b1","user":{"login":"antiochp","id":30642645,"node_id":"MDQ6VXNlcjMwNjQyNjQ1","avatar_url":"https://avatars2.githubusercontent.com/u/30642645?v=4","gravatar_id":"","url":"https://api.github.com/users/antiochp","html_url":"https://github.com/antiochp","followers_url":"https://api.github.com/users/antiochp/followers","following_url":"https://api.github.com/users/antiochp/following{/other_user}","gists_url":"https://api.github.com/users/antiochp/gists{/gist_id}","starred_url":"https://api.github.com/users/antiochp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/antiochp/subscriptions","organizations_url":"https://api.github.com/users/antiochp/orgs","repos_url":"https://api.github.com/users/antiochp/repos","events_url":"https://api.github.com/users/antiochp/events{/privacy}","received_events_url":"https://api.github.com/users/antiochp/received_events","type":"User","site_admin":false},"body":"I think I was misreading the code here. Thought we were only doing `fast_or()` if we had > 256 bitmaps.\r\nBut I _think_ what you're doing is batching them up and running `fast_or()` on every batch of 256 bitmaps so we don't need to maintain a huge vec of bitmaps.\r\n\r\n:+1: if that's the case.\r\nBut maybe add a comment explaining that?\r\n\r\n","created_at":"2018-09-14T15:13:57Z","updated_at":"2018-09-14T15:13:57Z","html_url":"https://github.com/mimblewimble/grin/pull/1528#discussion_r217747228","pull_request_url":"https://api.github.com/repos/mimblewimble/grin/pulls/1528","author_association":"MEMBER","_links":{"self":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/comments/217747228"},"html":{"href":"https://github.com/mimblewimble/grin/pull/1528#discussion_r217747228"},"pull_request":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/1528"}},"in_reply_to_id":217733174},"pull_request":{"url":"https://api.github.com/repos/mimblewimble/grin/pulls/1528","id":215585172,"node_id":"MDExOlB1bGxSZXF1ZXN0MjE1NTg1MTcy","html_url":"https://github.com/mimblewimble/grin/pull/1528","diff_url":"https://github.com/mimblewimble/grin/pull/1528.diff","patch_url":"https://github.com/mimblewimble/grin/pull/1528.patch","issue_url":"https://api.github.com/repos/mimblewimble/grin/issues/1528","number":1528,"state":"open","locked":false,"title":"optimization for txhashset rewind","user":{"login":"garyyu","id":1852227,"node_id":"MDQ6VXNlcjE4NTIyMjc=","avatar_url":"https://avatars3.githubusercontent.com/u/1852227?v=4","gravatar_id":"","url":"https://api.github.com/users/garyyu","html_url":"https://github.com/garyyu","followers_url":"https://api.github.com/users/garyyu/followers","following_url":"https://api.github.com/users/garyyu/following{/other_user}","gists_url":"https://api.github.com/users/garyyu/gists{/gist_id}","starred_url":"https://api.github.com/users/garyyu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/garyyu/subscriptions","organizations_url":"https://api.github.com/users/garyyu/orgs","repos_url":"https://api.github.com/users/garyyu/repos","events_url":"https://api.github.com/users/garyyu/events{/privacy}","received_events_url":"https://api.github.com/users/garyyu/received_events","type":"User","site_admin":false},"body":"Optimization for `rewind()` function in `chain/src/txhashset.rs`. It's about as 700% faster as the old version, for this function call, in case the rewind block is very far from the Tip.\r\n\r\nCompare between old version and new version:\r\n\r\n- Test with block height 40,000:\r\n```\r\n# curl -0 -XGET  http://127.0.0.1:13413/v1/blocks/40000\r\n\r\nOld Version:\r\nSep 14 20:09:05.106 DEBG txhashset: merkle_proof: output: Commitment(09d84a9c6b5939fbd12739421e6c99d26fc313f269046353d8eecf7879cbef1d56), block: 007453cb\r\nSep 14 20:09:06.070 DEBG merkle_proof  99312, last_pos 99312\r\n                    <<<< 964ms spent\r\n\r\nNew Version:\r\nSep 14 20:31:54.413 DEBG txhashset: merkle_proof: output: Commitment(09d84a9c6b5939fbd12739421e6c99d26fc313f269046353d8eecf7879cbef1d56), block: 007453cb\r\nSep 14 20:31:54.548 DEBG merkle_proof  99312, last_pos 99312\r\n                    <<<< 135ms spent\r\n```\r\n- Test with block height 50,000:\r\n```\r\n# curl -0 -XGET  http://127.0.0.1:13413/v1/blocks/50000\r\n\r\nOld Version:\r\nSep 14 20:05:18.304 DEBG txhashset: merkle_proof: output: Commitment(09994dd2a6dd7cd7fbf9104e10c304cd8eaf16f74ae5d405e2b26c7e0e3b85c816), block: 02e79e8f\r\nSep 14 20:05:19.084 DEBG merkle_proof  119420, last_pos 119421\r\n                    <<<<  780ms spent\r\n\r\nNew Version:\r\nSep 14 20:30:14.842 DEBG txhashset: merkle_proof: output: Commitment(09994dd2a6dd7cd7fbf9104e10c304cd8eaf16f74ae5d405e2b26c7e0e3b85c816), block: 02e79e8f\r\nSep 14 20:30:14.948 DEBG merkle_proof  119420, last_pos 119421\r\n                    <<<< 106ms spent\r\n```\r\n- Test with block height 80,000:\r\n```\r\n# curl -0 -XGET  http://127.0.0.1:13413/v1/blocks/80000\r\n\r\nOld Version:\r\nSep 14 20:04:21.345 DEBG txhashset: merkle_proof: output: Commitment(093941106eb2c3392e0f839dbd2d19926f71ae81d2368492f8b6b4b5854bb9bd79), block: 1316d80e\r\nSep 14 20:04:21.612 DEBG merkle_proof  185971, last_pos 185977\r\n                    <<<< 267ms spent\r\n\r\nNew Version:\r\nSep 14 20:28:56.290 DEBG txhashset: merkle_proof: output: Commitment(093941106eb2c3392e0f839dbd2d19926f71ae81d2368492f8b6b4b5854bb9bd79), block: 1316d80e\r\nSep 14 20:28:56.325 DEBG merkle_proof  185971, last_pos 185977\r\n                    <<<< 35ms spent\r\n```\r\n\r\n**another** optimization is for `Bitmap`, use `Bitmap::fast_or()` to replace `or_inplace()`. This was a `TODO` item in the old code. I also add a bench test for it:\r\n```\r\n$ cd store\r\n$ cargo test --release bench_fast_or -- --nocapture\r\n\r\nrunning 1 test\r\n  or_inplace():     5.098ms. bitmap cardinality: 225785\r\n     fast_or():     0.778ms. bitmap cardinality: 226018\r\nfast_or_heap():     9.203ms. bitmap cardinality: 225628\r\n```\r\n\r\nA main optimization is using `get_hash_by_height()` instead of `get_block_header()`.\r\n\r\nBTW, this PR came from the analysis result of issue: https://github.com/mimblewimble/grin/issues/1477\r\n\r\n\r\n","created_at":"2018-09-14T12:55:12Z","updated_at":"2018-09-14T15:13:57Z","closed_at":null,"merged_at":null,"merge_commit_sha":"d3458c42c83fa1c50d1e4dfbf3e280f6ff9d0d28","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/mimblewimble/grin/pulls/1528/commits","review_comments_url":"https://api.github.com/repos/mimblewimble/grin/pulls/1528/comments","review_comment_url":"https://api.github.com/repos/mimblewimble/grin/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mimblewimble/grin/issues/1528/comments","statuses_url":"https://api.github.com/repos/mimblewimble/grin/statuses/996883e7191c588505fe4fa4b4b61cc2848753b1","head":{"label":"garyyu:txhashset-rewind","ref":"txhashset-rewind","sha":"996883e7191c588505fe4fa4b4b61cc2848753b1","user":{"login":"garyyu","id":1852227,"node_id":"MDQ6VXNlcjE4NTIyMjc=","avatar_url":"https://avatars3.githubusercontent.com/u/1852227?v=4","gravatar_id":"","url":"https://api.github.com/users/garyyu","html_url":"https://github.com/garyyu","followers_url":"https://api.github.com/users/garyyu/followers","following_url":"https://api.github.com/users/garyyu/following{/other_user}","gists_url":"https://api.github.com/users/garyyu/gists{/gist_id}","starred_url":"https://api.github.com/users/garyyu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/garyyu/subscriptions","organizations_url":"https://api.github.com/users/garyyu/orgs","repos_url":"https://api.github.com/users/garyyu/repos","events_url":"https://api.github.com/users/garyyu/events{/privacy}","received_events_url":"https://api.github.com/users/garyyu/received_events","type":"User","site_admin":false},"repo":{"id":131562603,"node_id":"MDEwOlJlcG9zaXRvcnkxMzE1NjI2MDM=","name":"grin","full_name":"garyyu/grin","owner":{"login":"garyyu","id":1852227,"node_id":"MDQ6VXNlcjE4NTIyMjc=","avatar_url":"https://avatars3.githubusercontent.com/u/1852227?v=4","gravatar_id":"","url":"https://api.github.com/users/garyyu","html_url":"https://github.com/garyyu","followers_url":"https://api.github.com/users/garyyu/followers","following_url":"https://api.github.com/users/garyyu/following{/other_user}","gists_url":"https://api.github.com/users/garyyu/gists{/gist_id}","starred_url":"https://api.github.com/users/garyyu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/garyyu/subscriptions","organizations_url":"https://api.github.com/users/garyyu/orgs","repos_url":"https://api.github.com/users/garyyu/repos","events_url":"https://api.github.com/users/garyyu/events{/privacy}","received_events_url":"https://api.github.com/users/garyyu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/garyyu/grin","description":"Minimal implementation of the MimbleWimble protocol.","fork":true,"url":"https://api.github.com/repos/garyyu/grin","forks_url":"https://api.github.com/repos/garyyu/grin/forks","keys_url":"https://api.github.com/repos/garyyu/grin/keys{/key_id}","collaborators_url":"https://api.github.com/repos/garyyu/grin/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/garyyu/grin/teams","hooks_url":"https://api.github.com/repos/garyyu/grin/hooks","issue_events_url":"https://api.github.com/repos/garyyu/grin/issues/events{/number}","events_url":"https://api.github.com/repos/garyyu/grin/events","assignees_url":"https://api.github.com/repos/garyyu/grin/assignees{/user}","branches_url":"https://api.github.com/repos/garyyu/grin/branches{/branch}","tags_url":"https://api.github.com/repos/garyyu/grin/tags","blobs_url":"https://api.github.com/repos/garyyu/grin/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/garyyu/grin/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/garyyu/grin/git/refs{/sha}","trees_url":"https://api.github.com/repos/garyyu/grin/git/trees{/sha}","statuses_url":"https://api.github.com/repos/garyyu/grin/statuses/{sha}","languages_url":"https://api.github.com/repos/garyyu/grin/languages","stargazers_url":"https://api.github.com/repos/garyyu/grin/stargazers","contributors_url":"https://api.github.com/repos/garyyu/grin/contributors","subscribers_url":"https://api.github.com/repos/garyyu/grin/subscribers","subscription_url":"https://api.github.com/repos/garyyu/grin/subscription","commits_url":"https://api.github.com/repos/garyyu/grin/commits{/sha}","git_commits_url":"https://api.github.com/repos/garyyu/grin/git/commits{/sha}","comments_url":"https://api.github.com/repos/garyyu/grin/comments{/number}","issue_comment_url":"https://api.github.com/repos/garyyu/grin/issues/comments{/number}","contents_url":"https://api.github.com/repos/garyyu/grin/contents/{+path}","compare_url":"https://api.github.com/repos/garyyu/grin/compare/{base}...{head}","merges_url":"https://api.github.com/repos/garyyu/grin/merges","archive_url":"https://api.github.com/repos/garyyu/grin/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/garyyu/grin/downloads","issues_url":"https://api.github.com/repos/garyyu/grin/issues{/number}","pulls_url":"https://api.github.com/repos/garyyu/grin/pulls{/number}","milestones_url":"https://api.github.com/repos/garyyu/grin/milestones{/number}","notifications_url":"https://api.github.com/repos/garyyu/grin/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/garyyu/grin/labels{/name}","releases_url":"https://api.github.com/repos/garyyu/grin/releases{/id}","deployments_url":"https://api.github.com/repos/garyyu/grin/deployments","created_at":"2018-04-30T06:22:04Z","updated_at":"2018-09-07T07:21:22Z","pushed_at":"2018-09-14T10:39:22Z","git_url":"git://github.com/garyyu/grin.git","ssh_url":"git@github.com:garyyu/grin.git","clone_url":"https://github.com/garyyu/grin.git","svn_url":"https://github.com/garyyu/grin","homepage":"http://grin-tech.org/","size":10925,"stargazers_count":1,"watchers_count":1,"language":"Rust","has_issues":false,"has_projects":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":0,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"mimblewimble:master","ref":"master","sha":"3c1d8c3f8b12ae9e8c3bf51f9c1effcda1aa0d5f","user":{"login":"mimblewimble","id":23646132,"node_id":"MDEyOk9yZ2FuaXphdGlvbjIzNjQ2MTMy","avatar_url":"https://avatars0.githubusercontent.com/u/23646132?v=4","gravatar_id":"","url":"https://api.github.com/users/mimblewimble","html_url":"https://github.com/mimblewimble","followers_url":"https://api.github.com/users/mimblewimble/followers","following_url":"https://api.github.com/users/mimblewimble/following{/other_user}","gists_url":"https://api.github.com/users/mimblewimble/gists{/gist_id}","starred_url":"https://api.github.com/users/mimblewimble/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mimblewimble/subscriptions","organizations_url":"https://api.github.com/users/mimblewimble/orgs","repos_url":"https://api.github.com/users/mimblewimble/repos","events_url":"https://api.github.com/users/mimblewimble/events{/privacy}","received_events_url":"https://api.github.com/users/mimblewimble/received_events","type":"Organization","site_admin":false},"repo":{"id":71514072,"node_id":"MDEwOlJlcG9zaXRvcnk3MTUxNDA3Mg==","name":"grin","full_name":"mimblewimble/grin","owner":{"login":"mimblewimble","id":23646132,"node_id":"MDEyOk9yZ2FuaXphdGlvbjIzNjQ2MTMy","avatar_url":"https://avatars0.githubusercontent.com/u/23646132?v=4","gravatar_id":"","url":"https://api.github.com/users/mimblewimble","html_url":"https://github.com/mimblewimble","followers_url":"https://api.github.com/users/mimblewimble/followers","following_url":"https://api.github.com/users/mimblewimble/following{/other_user}","gists_url":"https://api.github.com/users/mimblewimble/gists{/gist_id}","starred_url":"https://api.github.com/users/mimblewimble/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mimblewimble/subscriptions","organizations_url":"https://api.github.com/users/mimblewimble/orgs","repos_url":"https://api.github.com/users/mimblewimble/repos","events_url":"https://api.github.com/users/mimblewimble/events{/privacy}","received_events_url":"https://api.github.com/users/mimblewimble/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mimblewimble/grin","description":"Minimal implementation of the MimbleWimble protocol.","fork":false,"url":"https://api.github.com/repos/mimblewimble/grin","forks_url":"https://api.github.com/repos/mimblewimble/grin/forks","keys_url":"https://api.github.com/repos/mimblewimble/grin/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mimblewimble/grin/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mimblewimble/grin/teams","hooks_url":"https://api.github.com/repos/mimblewimble/grin/hooks","issue_events_url":"https://api.github.com/repos/mimblewimble/grin/issues/events{/number}","events_url":"https://api.github.com/repos/mimblewimble/grin/events","assignees_url":"https://api.github.com/repos/mimblewimble/grin/assignees{/user}","branches_url":"https://api.github.com/repos/mimblewimble/grin/branches{/branch}","tags_url":"https://api.github.com/repos/mimblewimble/grin/tags","blobs_url":"https://api.github.com/repos/mimblewimble/grin/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mimblewimble/grin/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mimblewimble/grin/git/refs{/sha}","trees_url":"https://api.github.com/repos/mimblewimble/grin/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mimblewimble/grin/statuses/{sha}","languages_url":"https://api.github.com/repos/mimblewimble/grin/languages","stargazers_url":"https://api.github.com/repos/mimblewimble/grin/stargazers","contributors_url":"https://api.github.com/repos/mimblewimble/grin/contributors","subscribers_url":"https://api.github.com/repos/mimblewimble/grin/subscribers","subscription_url":"https://api.github.com/repos/mimblewimble/grin/subscription","commits_url":"https://api.github.com/repos/mimblewimble/grin/commits{/sha}","git_commits_url":"https://api.github.com/repos/mimblewimble/grin/git/commits{/sha}","comments_url":"https://api.github.com/repos/mimblewimble/grin/comments{/number}","issue_comment_url":"https://api.github.com/repos/mimblewimble/grin/issues/comments{/number}","contents_url":"https://api.github.com/repos/mimblewimble/grin/contents/{+path}","compare_url":"https://api.github.com/repos/mimblewimble/grin/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mimblewimble/grin/merges","archive_url":"https://api.github.com/repos/mimblewimble/grin/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mimblewimble/grin/downloads","issues_url":"https://api.github.com/repos/mimblewimble/grin/issues{/number}","pulls_url":"https://api.github.com/repos/mimblewimble/grin/pulls{/number}","milestones_url":"https://api.github.com/repos/mimblewimble/grin/milestones{/number}","notifications_url":"https://api.github.com/repos/mimblewimble/grin/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mimblewimble/grin/labels{/name}","releases_url":"https://api.github.com/repos/mimblewimble/grin/releases{/id}","deployments_url":"https://api.github.com/repos/mimblewimble/grin/deployments","created_at":"2016-10-21T00:02:23Z","updated_at":"2018-09-14T14:25:55Z","pushed_at":"2018-09-14T14:25:52Z","git_url":"git://github.com/mimblewimble/grin.git","ssh_url":"git@github.com:mimblewimble/grin.git","clone_url":"https://github.com/mimblewimble/grin.git","svn_url":"https://github.com/mimblewimble/grin","homepage":"http://grin-tech.org/","size":10782,"stargazers_count":1369,"watchers_count":1369,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":252,"mirror_url":null,"archived":false,"open_issues_count":79,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":252,"open_issues":79,"watchers":1369,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/1528"},"html":{"href":"https://github.com/mimblewimble/grin/pull/1528"},"issue":{"href":"https://api.github.com/repos/mimblewimble/grin/issues/1528"},"comments":{"href":"https://api.github.com/repos/mimblewimble/grin/issues/1528/comments"},"review_comments":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/1528/comments"},"review_comment":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mimblewimble/grin/pulls/1528/commits"},"statuses":{"href":"https://api.github.com/repos/mimblewimble/grin/statuses/996883e7191c588505fe4fa4b4b61cc2848753b1"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"antiochp"}}