{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/9661","labels_url":"https://api.github.com/repos/apache/spark/issues/9661/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/9661/comments","events_url":"https://api.github.com/repos/apache/spark/issues/9661/events","html_url":"https://github.com/apache/spark/pull/9661","id":116532755,"number":9661,"title":"[SPARK-11583] [Core]MapStatus Using RoaringBitmap More Properly","user":{"login":"yaooqinn","id":8326978,"avatar_url":"https://avatars.githubusercontent.com/u/8326978?v=3","gravatar_id":"","url":"https://api.github.com/users/yaooqinn","html_url":"https://github.com/yaooqinn","followers_url":"https://api.github.com/users/yaooqinn/followers","following_url":"https://api.github.com/users/yaooqinn/following{/other_user}","gists_url":"https://api.github.com/users/yaooqinn/gists{/gist_id}","starred_url":"https://api.github.com/users/yaooqinn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yaooqinn/subscriptions","organizations_url":"https://api.github.com/users/yaooqinn/orgs","repos_url":"https://api.github.com/users/yaooqinn/repos","events_url":"https://api.github.com/users/yaooqinn/events{/privacy}","received_events_url":"https://api.github.com/users/yaooqinn/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-11-12T11:38:33Z","updated_at":"2015-11-12T22:33:45Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/9661","html_url":"https://github.com/apache/spark/pull/9661","diff_url":"https://github.com/apache/spark/pull/9661.diff","patch_url":"https://github.com/apache/spark/pull/9661.patch"},"body":"1. test cases\r\n\r\n1.1 sparse case: for each task 10 blocks contains data, others dont\r\n      sc.makeRDD(1 to 40950, 4095).groupBy(x=>x).top(5)\r\n\r\n1.2 dense case: for each task most block contains data, few dont\r\n      1.2.1 full\r\n          sc.makeRDD(1 to 16769025, 4095).groupBy(x=>x).top(5)\r\n       1.2.2 very dense: about 95 empty blocks\r\nsc.makeRDD(1 to 16380000, 4095).groupBy(x=>x).top(5)\r\n\r\n\r\n1.3 test tool\r\njmap -dump:format=b,file=heap.bin <pid>\r\n1.4 test branches: branch-1.5, master\r\n\r\n\r\n2. memory usage\r\n\r\n2.1 RoaringBitmap--sparse\r\nClass Name                                                                        | Objects | Shallow Heap | Retained Heap\r\n\r\norg.apache.spark.scheduler.HighlyCompressedMapStatus| 4,095    |  131,040          | >= 34,135,920\r\n\r\nmy explaination: 4095 * short[4095-10] =4095 * 16 * 4085 / 8 ≈ 34,135,920\r\n\r\n2.2.1 RoaringBitmap--full\r\n\r\norg.apache.spark.scheduler.HighlyCompressedMapStatus| 4,095     | 131,040           | >= 360,360 \r\n\r\nmy explaination：RoaringBitmap(0)\r\n\r\n2.2.2 RoaringBitmap--very dense\r\n\r\norg.apache.spark.scheduler.HighlyCompressedMapStatus| 4,095      | 131,040           | >= 1,441,440\r\n\r\nmy explaination：4095 * short[95] = 4095 * 16 * 95 / 8 = 778, 050 (+ others = 1441440)\r\n\r\n2.3 BitSet--sparse\r\n\r\norg.apache.spark.scheduler.HighlyCompressedMapStatus| 4,095       | 131,040          | >= 2,391,480\r\n\r\nmy explaination：4095 * 4095 =16,769,025 + (others = 2,391,480)\r\n\r\n2.4 BitSet--full\r\n\r\norg.apache.spark.scheduler.HighlyCompressedMapStatus| 4,095       | 131,040         | >= 2,391,480\r\n\r\nmy explaination：same as the above\r\n\r\n3. conclusion\r\nmemory usage:( Retained Heap)\r\nRoaringBitmap--full < RoaringBitmap--very dense < BitSet---full = BitSet--sparse < RoaringBitmap--sparse\r\n\r\nIn this specific case, for  RoaringBitmap--sparse, use RoaringBitmap to mark non-empty blocks instead of empty ones. In this way, memory usage can stay low in all cases.\r\n\r\nThis is better than my former pr ---- https://github.com/apache/spark/pull/9559"},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/156258591","html_url":"https://github.com/apache/spark/pull/9661#issuecomment-156258591","issue_url":"https://api.github.com/repos/apache/spark/issues/9661","id":156258591,"user":{"login":"squito","id":71240,"avatar_url":"https://avatars.githubusercontent.com/u/71240?v=3","gravatar_id":"","url":"https://api.github.com/users/squito","html_url":"https://github.com/squito","followers_url":"https://api.github.com/users/squito/followers","following_url":"https://api.github.com/users/squito/following{/other_user}","gists_url":"https://api.github.com/users/squito/gists{/gist_id}","starred_url":"https://api.github.com/users/squito/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/squito/subscriptions","organizations_url":"https://api.github.com/users/squito/orgs","repos_url":"https://api.github.com/users/squito/repos","events_url":"https://api.github.com/users/squito/events{/privacy}","received_events_url":"https://api.github.com/users/squito/received_events","type":"User","site_admin":false},"created_at":"2015-11-12T22:33:45Z","updated_at":"2015-11-12T22:33:45Z","body":"@srowen There is still some analysis left to be done, but I think there is a growing case that roaring is actually the right way to go, with some minor tweaks.  So I'll do more reviewing here, assuming the analysis works out the way we expect, but this is still pending some final details from the discussion on the jira."}}