{"action":"opened","number":199,"pull_request":{"url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199","id":158801526,"html_url":"https://github.com/RoaringBitmap/RoaringBitmap/pull/199","diff_url":"https://github.com/RoaringBitmap/RoaringBitmap/pull/199.diff","patch_url":"https://github.com/RoaringBitmap/RoaringBitmap/pull/199.patch","issue_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/199","number":199,"state":"open","locked":false,"title":"Speed up incremental writes","user":{"login":"richardstartin","id":16439049,"avatar_url":"https://avatars3.githubusercontent.com/u/16439049?v=4","gravatar_id":"","url":"https://api.github.com/users/richardstartin","html_url":"https://github.com/richardstartin","followers_url":"https://api.github.com/users/richardstartin/followers","following_url":"https://api.github.com/users/richardstartin/following{/other_user}","gists_url":"https://api.github.com/users/richardstartin/gists{/gist_id}","starred_url":"https://api.github.com/users/richardstartin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/richardstartin/subscriptions","organizations_url":"https://api.github.com/users/richardstartin/orgs","repos_url":"https://api.github.com/users/richardstartin/repos","events_url":"https://api.github.com/users/richardstartin/events{/privacy}","received_events_url":"https://api.github.com/users/richardstartin/received_events","type":"User","site_admin":false},"body":"This pull request makes it possible to write sequentially and incrementally to a RoaringBitmap. \r\n\r\n**Usage**\r\n\r\n`OrderedWriter` wraps a `RoaringBitmap` and requires the caller to flush it to ensure all added data is saved to the bitmap.\r\n\r\n```\r\n   OrderedWriter writer = new OrderedWriter(rb);\r\n    // add data incrementally, must be in ascending unsigned order\r\n    for (int i : values) {\r\n      writer.add(i);\r\n    }\r\n    // flush all buffered data down to the underlying bitmap\r\n    writer.flush();\r\n```\r\n\r\n**Testing**\r\n\r\nThe basic behaviour of `OrderWriter` is tested in `TestOrderedWriter`.\r\n\r\nThat a RoaringBitmap built by an `OrderedWriter` is equivalent to one built by `RoaringBitmap.bitmapOf` is tested for random bitmaps of various size is tested in `OrderedWriterRandomisedTest`\r\n\r\n**Benchmarks**\r\n\r\n`WriteSequential` compares `RoaringBitmap.bitmapOf` (i.e. what you could do if you had the entire array in one go), sequential calls to `RoaringBitmap.add` and `OrderedWriter`. Data is generated for a range of sizes and a range of \"runniness\" (i.e. how likely it is that the data can be run length encoded.) The results are good: `OrderedWriter` is faster than `RoaringBitmap.bitmapOf` for small data sets. For larger datasets the performance is of similar performance, and a great deal better than sequential calls to `RoaringBitmap.add`.\r\n\r\n```\r\nBenchmark                                    (randomness)    (size)  Mode  Cnt       Score       Error  Units\r\nWriteSequential.buildRoaringBitmap                    0.1     10000  avgt    5      53.628 ▒     2.544  us/op\r\nWriteSequential.buildRoaringBitmap                    0.1    100000  avgt    5     354.691 ▒     9.786  us/op\r\nWriteSequential.buildRoaringBitmap                    0.1   1000000  avgt    5    3530.126 ▒   157.438  us/op\r\nWriteSequential.buildRoaringBitmap                    0.1  10000000  avgt    5   31400.821 ▒   529.543  us/op\r\nWriteSequential.buildRoaringBitmap                    0.5     10000  avgt    5      52.083 ▒     2.663  us/op\r\nWriteSequential.buildRoaringBitmap                    0.5    100000  avgt    5     353.520 ▒     7.453  us/op\r\nWriteSequential.buildRoaringBitmap                    0.5   1000000  avgt    5    3492.611 ▒   111.276  us/op\r\nWriteSequential.buildRoaringBitmap                    0.5  10000000  avgt    5   37178.051 ▒  9069.530  us/op\r\nWriteSequential.buildRoaringBitmap                    0.9     10000  avgt    5      59.458 ▒     8.530  us/op\r\nWriteSequential.buildRoaringBitmap                    0.9    100000  avgt    5     360.718 ▒    52.790  us/op\r\nWriteSequential.buildRoaringBitmap                    0.9   1000000  avgt    5    3766.560 ▒  1198.259  us/op\r\nWriteSequential.buildRoaringBitmap                    0.9  10000000  avgt    5   33221.955 ▒  2151.770  us/op\r\nWriteSequential.incrementalNativeAdd                  0.1     10000  avgt    5      95.012 ▒     8.962  us/op\r\nWriteSequential.incrementalNativeAdd                  0.1    100000  avgt    5     780.217 ▒   106.684  us/op\r\nWriteSequential.incrementalNativeAdd                  0.1   1000000  avgt    5    9265.335 ▒   846.230  us/op\r\nWriteSequential.incrementalNativeAdd                  0.1  10000000  avgt    5  101037.210 ▒  6457.910  us/op\r\nWriteSequential.incrementalNativeAdd                  0.5     10000  avgt    5     111.847 ▒    14.197  us/op\r\nWriteSequential.incrementalNativeAdd                  0.5    100000  avgt    5     887.937 ▒    69.129  us/op\r\nWriteSequential.incrementalNativeAdd                  0.5   1000000  avgt    5    7620.004 ▒   500.564  us/op\r\nWriteSequential.incrementalNativeAdd                  0.5  10000000  avgt    5  101455.646 ▒ 14751.135  us/op\r\nWriteSequential.incrementalNativeAdd                  0.9     10000  avgt    5      93.574 ▒     8.004  us/op\r\nWriteSequential.incrementalNativeAdd                  0.9    100000  avgt    5     882.819 ▒    46.454  us/op\r\nWriteSequential.incrementalNativeAdd                  0.9   1000000  avgt    5    7507.996 ▒   426.764  us/op\r\nWriteSequential.incrementalNativeAdd                  0.9  10000000  avgt    5   98675.524 ▒  1715.163  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.1     10000  avgt    5      26.338 ▒     1.190  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.1    100000  avgt    5     367.215 ▒    26.818  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.1   1000000  avgt    5    3832.171 ▒   347.830  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.1  10000000  avgt    5   43193.867 ▒ 20770.625  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.5     10000  avgt    5      32.928 ▒    10.230  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.5    100000  avgt    5     394.717 ▒    93.505  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.5   1000000  avgt    5    3728.619 ▒   177.213  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.5  10000000  avgt    5   36694.794 ▒  1931.691  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.9     10000  avgt    5      26.152 ▒     1.391  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.9    100000  avgt    5     366.515 ▒    14.643  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.9   1000000  avgt    5    3696.070 ▒   107.797  us/op\r\nWriteSequential.incrementalUseOrderedWriter           0.9  10000000  avgt    5   36587.744 ▒  1793.303  us/op\r\n\r\n```","created_at":"2017-12-17T20:15:10Z","updated_at":"2017-12-17T20:15:10Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"assignees":[],"requested_reviewers":[],"milestone":null,"commits_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199/commits","review_comments_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199/comments","review_comment_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/comments{/number}","comments_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/199/comments","statuses_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/statuses/f88ea0a49d563c6c636cebe7cc37db5fa7cb9718","head":{"label":"richardstartin:speed-up-incremental-writes","ref":"speed-up-incremental-writes","sha":"f88ea0a49d563c6c636cebe7cc37db5fa7cb9718","user":{"login":"richardstartin","id":16439049,"avatar_url":"https://avatars3.githubusercontent.com/u/16439049?v=4","gravatar_id":"","url":"https://api.github.com/users/richardstartin","html_url":"https://github.com/richardstartin","followers_url":"https://api.github.com/users/richardstartin/followers","following_url":"https://api.github.com/users/richardstartin/following{/other_user}","gists_url":"https://api.github.com/users/richardstartin/gists{/gist_id}","starred_url":"https://api.github.com/users/richardstartin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/richardstartin/subscriptions","organizations_url":"https://api.github.com/users/richardstartin/orgs","repos_url":"https://api.github.com/users/richardstartin/repos","events_url":"https://api.github.com/users/richardstartin/events{/privacy}","received_events_url":"https://api.github.com/users/richardstartin/received_events","type":"User","site_admin":false},"repo":{"id":113700977,"name":"RoaringBitmap","full_name":"richardstartin/RoaringBitmap","owner":{"login":"richardstartin","id":16439049,"avatar_url":"https://avatars3.githubusercontent.com/u/16439049?v=4","gravatar_id":"","url":"https://api.github.com/users/richardstartin","html_url":"https://github.com/richardstartin","followers_url":"https://api.github.com/users/richardstartin/followers","following_url":"https://api.github.com/users/richardstartin/following{/other_user}","gists_url":"https://api.github.com/users/richardstartin/gists{/gist_id}","starred_url":"https://api.github.com/users/richardstartin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/richardstartin/subscriptions","organizations_url":"https://api.github.com/users/richardstartin/orgs","repos_url":"https://api.github.com/users/richardstartin/repos","events_url":"https://api.github.com/users/richardstartin/events{/privacy}","received_events_url":"https://api.github.com/users/richardstartin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/richardstartin/RoaringBitmap","description":"A better compressed bitset in Java","fork":true,"url":"https://api.github.com/repos/richardstartin/RoaringBitmap","forks_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/forks","keys_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/keys{/key_id}","collaborators_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/teams","hooks_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/hooks","issue_events_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/issues/events{/number}","events_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/events","assignees_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/assignees{/user}","branches_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/branches{/branch}","tags_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/tags","blobs_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/git/refs{/sha}","trees_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/git/trees{/sha}","statuses_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/statuses/{sha}","languages_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/languages","stargazers_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/stargazers","contributors_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/contributors","subscribers_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/subscribers","subscription_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/subscription","commits_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/commits{/sha}","git_commits_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/git/commits{/sha}","comments_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/comments{/number}","issue_comment_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/issues/comments{/number}","contents_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/contents/{+path}","compare_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/compare/{base}...{head}","merges_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/merges","archive_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/downloads","issues_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/issues{/number}","pulls_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/pulls{/number}","milestones_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/milestones{/number}","notifications_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/labels{/name}","releases_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/releases{/id}","deployments_url":"https://api.github.com/repos/richardstartin/RoaringBitmap/deployments","created_at":"2017-12-09T21:01:45Z","updated_at":"2017-12-09T21:01:48Z","pushed_at":"2017-12-17T20:05:12Z","git_url":"git://github.com/richardstartin/RoaringBitmap.git","ssh_url":"git@github.com:richardstartin/RoaringBitmap.git","clone_url":"https://github.com/richardstartin/RoaringBitmap.git","svn_url":"https://github.com/richardstartin/RoaringBitmap","homepage":"http://roaringbitmap.org/","size":83561,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":null,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"RoaringBitmap:master","ref":"master","sha":"b9a2107ab35aff822caec1dcd01f9a334e8deefd","user":{"login":"RoaringBitmap","id":16548876,"avatar_url":"https://avatars2.githubusercontent.com/u/16548876?v=4","gravatar_id":"","url":"https://api.github.com/users/RoaringBitmap","html_url":"https://github.com/RoaringBitmap","followers_url":"https://api.github.com/users/RoaringBitmap/followers","following_url":"https://api.github.com/users/RoaringBitmap/following{/other_user}","gists_url":"https://api.github.com/users/RoaringBitmap/gists{/gist_id}","starred_url":"https://api.github.com/users/RoaringBitmap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoaringBitmap/subscriptions","organizations_url":"https://api.github.com/users/RoaringBitmap/orgs","repos_url":"https://api.github.com/users/RoaringBitmap/repos","events_url":"https://api.github.com/users/RoaringBitmap/events{/privacy}","received_events_url":"https://api.github.com/users/RoaringBitmap/received_events","type":"Organization","site_admin":false},"repo":{"id":10746583,"name":"RoaringBitmap","full_name":"RoaringBitmap/RoaringBitmap","owner":{"login":"RoaringBitmap","id":16548876,"avatar_url":"https://avatars2.githubusercontent.com/u/16548876?v=4","gravatar_id":"","url":"https://api.github.com/users/RoaringBitmap","html_url":"https://github.com/RoaringBitmap","followers_url":"https://api.github.com/users/RoaringBitmap/followers","following_url":"https://api.github.com/users/RoaringBitmap/following{/other_user}","gists_url":"https://api.github.com/users/RoaringBitmap/gists{/gist_id}","starred_url":"https://api.github.com/users/RoaringBitmap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoaringBitmap/subscriptions","organizations_url":"https://api.github.com/users/RoaringBitmap/orgs","repos_url":"https://api.github.com/users/RoaringBitmap/repos","events_url":"https://api.github.com/users/RoaringBitmap/events{/privacy}","received_events_url":"https://api.github.com/users/RoaringBitmap/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/RoaringBitmap/RoaringBitmap","description":"A better compressed bitset in Java","fork":false,"url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap","forks_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/forks","keys_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/keys{/key_id}","collaborators_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/teams","hooks_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/hooks","issue_events_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/events{/number}","events_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/events","assignees_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/assignees{/user}","branches_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/branches{/branch}","tags_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/tags","blobs_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/git/refs{/sha}","trees_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/git/trees{/sha}","statuses_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/statuses/{sha}","languages_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/languages","stargazers_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/stargazers","contributors_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/contributors","subscribers_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/subscribers","subscription_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/subscription","commits_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/commits{/sha}","git_commits_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/git/commits{/sha}","comments_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/comments{/number}","issue_comment_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/comments{/number}","contents_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/contents/{+path}","compare_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/compare/{base}...{head}","merges_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/merges","archive_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/downloads","issues_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues{/number}","pulls_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls{/number}","milestones_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/milestones{/number}","notifications_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/labels{/name}","releases_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/releases{/id}","deployments_url":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/deployments","created_at":"2013-06-17T20:29:23Z","updated_at":"2017-12-16T18:47:58Z","pushed_at":"2017-12-16T19:59:55Z","git_url":"git://github.com/RoaringBitmap/RoaringBitmap.git","ssh_url":"git@github.com:RoaringBitmap/RoaringBitmap.git","clone_url":"https://github.com/RoaringBitmap/RoaringBitmap.git","svn_url":"https://github.com/RoaringBitmap/RoaringBitmap","homepage":"http://roaringbitmap.org/","size":83557,"stargazers_count":724,"watchers_count":724,"language":"Java","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":135,"mirror_url":null,"archived":false,"open_issues_count":32,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":135,"open_issues":32,"watchers":724,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199"},"html":{"href":"https://github.com/RoaringBitmap/RoaringBitmap/pull/199"},"issue":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/199"},"comments":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/issues/199/comments"},"review_comments":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199/comments"},"review_comment":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/pulls/199/commits"},"statuses":{"href":"https://api.github.com/repos/RoaringBitmap/RoaringBitmap/statuses/f88ea0a49d563c6c636cebe7cc37db5fa7cb9718"}},"author_association":"CONTRIBUTOR","merged":false,"mergeable":null,"rebaseable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"maintainer_can_modify":true,"commits":2,"additions":299,"deletions":0,"changed_files":4}}
{"actor":{"display_login":"richardstartin"}}