{"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":5,"created_at":"2015-11-12T11:38:33Z","updated_at":"2015-11-13T08:15:33Z","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/156359312","html_url":"https://github.com/apache/spark/pull/9661#issuecomment-156359312","issue_url":"https://api.github.com/repos/apache/spark/issues/9661","id":156359312,"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},"created_at":"2015-11-13T08:15:33Z","updated_at":"2015-11-13T08:15:33Z","body":"For my questions in my last comment\r\n### continuous\r\n```scala\r\nscala> import org.roaringbitmap._\r\nimport org.roaringbitmap._\r\n\r\nscala> val r = new RoaringBitmap()\r\nr: org.roaringbitmap.RoaringBitmap = {}\r\n\r\nscala> for (i <- 1 to 2000000)  r.add(i)\r\n\r\nscala> r.runOptimize\r\nres1: Boolean = true\r\n\r\nscala> r.contains(2000000)\r\nres2: Boolean = true\r\n```\r\nbits | original size | opitimized size\r\n---|---|----\r\n200K|33,056|328\r\n2M|255,472|1,768\r\n\r\n\r\n\r\n### uncontinuous\r\n```scala\r\nscala> import org.roaringbitmap._\r\nimport org.roaringbitmap._\r\n\r\nscala> val r = new RoaringBitmap()\r\nr: org.roaringbitmap.RoaringBitmap = {}\r\n\r\nscala> for (i <- 1 to 2000000) if(i%10==0) r.add(i)\r\n\r\nscala> r.runOptimize\r\nres1: Boolean = false\r\n\r\nscala> r.trim\r\n\r\nscala> r.contains(2000000)\r\nres2: Boolean = true\r\n```\r\nbits | original size | opitimized size|trimed size\r\n---|---|----|----\r\n200K|255,472|255,472|254,072\r\n2M|2,516,688|2,516,688|2,516,272\r\n\r\n### conclusion\r\nIn ```uncontinuous```, ```runOptimize``` failed and the size after ```r.trim``` neither became smaller as  in ```continuous```\r\n\r\nI guess my ```separating sparse case``` idea is still necessary for roaringbitmap to add lesser bits incase of ```runOptimize``` failure\r\n "}}