{"action":"created","issue":{"url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/22","labels_url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/22/labels{/name}","comments_url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/22/comments","events_url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/22/events","html_url":"https://github.com/lemire/RoaringBitmap/pull/22","id":64982652,"number":22,"title":"Optimize AND","user":{"login":"gssiyankai","id":2707931,"avatar_url":"https://avatars.githubusercontent.com/u/2707931?v=3","gravatar_id":"","url":"https://api.github.com/users/gssiyankai","html_url":"https://github.com/gssiyankai","followers_url":"https://api.github.com/users/gssiyankai/followers","following_url":"https://api.github.com/users/gssiyankai/following{/other_user}","gists_url":"https://api.github.com/users/gssiyankai/gists{/gist_id}","starred_url":"https://api.github.com/users/gssiyankai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gssiyankai/subscriptions","organizations_url":"https://api.github.com/users/gssiyankai/orgs","repos_url":"https://api.github.com/users/gssiyankai/repos","events_url":"https://api.github.com/users/gssiyankai/events{/privacy}","received_events_url":"https://api.github.com/users/gssiyankai/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-03-28T20:12:32Z","updated_at":"2015-03-31T23:37:41Z","closed_at":"2015-03-31T19:10:04Z","pull_request":{"url":"https://api.github.com/repos/lemire/RoaringBitmap/pulls/22","html_url":"https://github.com/lemire/RoaringBitmap/pull/22","diff_url":"https://github.com/lemire/RoaringBitmap/pull/22.diff","patch_url":"https://github.com/lemire/RoaringBitmap/pull/22.patch"},"body":"This PR optimizes AND (in-place and not-in-place) on roaring bitmaps.\r\n\r\nSo far, the AND operation between a bitmap A and a bitmap B used to be linear with n where:\r\n  - n is the number of chunks with a key smaller than k\r\n  - k is the min of kA and kB\r\n  - kA is the max chunk key of A\r\n  - kB is the max chunk key of B\r\n\r\nNow, the AND operation is linear with N where:\r\n  - N is the number of chunks with keys that are in both A and B\r\n\r\nTo have an idea of the improvements, I've set up some JMH benchmarks. Here are my results before and after my changes:\r\n```\r\nBEFORE\r\nBenchmark                          Mode  Cnt   Score   Error  Units\r\nRoaringBitmapBenchmark.and         avgt   10  58.256 ± 0.783  us/op\r\nRoaringBitmapBenchmark.inplaceAnd  avgt   10   4.068 ± 0.411  ns/op\r\n\r\nAFTER\r\nBenchmark                          Mode  Cnt  Score   Error  Units\r\nRoaringBitmapBenchmark.and         avgt   10  1.614 ± 0.026  us/op\r\nRoaringBitmapBenchmark.inplaceAnd  avgt   10  3.869 ± 0.242  ns/op\r\n```\r\n\r\nTo launch the JMH benchmarks locally, have a look at the README.\r\n\r\nLet me know if this looks good to you and I will add the same optimization to the memory-mapped roaring bitmaps."},"comment":{"url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/comments/88285025","html_url":"https://github.com/lemire/RoaringBitmap/pull/22#issuecomment-88285025","issue_url":"https://api.github.com/repos/lemire/RoaringBitmap/issues/22","id":88285025,"user":{"login":"lemire","id":391987,"avatar_url":"https://avatars.githubusercontent.com/u/391987?v=3","gravatar_id":"","url":"https://api.github.com/users/lemire","html_url":"https://github.com/lemire","followers_url":"https://api.github.com/users/lemire/followers","following_url":"https://api.github.com/users/lemire/following{/other_user}","gists_url":"https://api.github.com/users/lemire/gists{/gist_id}","starred_url":"https://api.github.com/users/lemire/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lemire/subscriptions","organizations_url":"https://api.github.com/users/lemire/orgs","repos_url":"https://api.github.com/users/lemire/repos","events_url":"https://api.github.com/users/lemire/events{/privacy}","received_events_url":"https://api.github.com/users/lemire/received_events","type":"User","site_admin":false},"created_at":"2015-03-31T23:37:41Z","updated_at":"2015-03-31T23:37:41Z","body":"Please hold one while I review the code more carefully. "}}