{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/9452","labels_url":"https://api.github.com/repos/apache/spark/issues/9452/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/9452/comments","events_url":"https://api.github.com/repos/apache/spark/issues/9452/events","html_url":"https://github.com/apache/spark/pull/9452","id":114937970,"number":9452,"title":"[SPARK-11493] remove bitset from BytesToBytesMap","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-11-03T23:54:50Z","updated_at":"2015-11-04T22:43:22Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/9452","html_url":"https://github.com/apache/spark/pull/9452","diff_url":"https://github.com/apache/spark/pull/9452.diff","patch_url":"https://github.com/apache/spark/pull/9452.patch"},"body":"Since we have 4 bytes as number of records in the beginning of a page, the address can not be zero, so we do not need the bitset.\r\n\r\nFor performance concerns, the bitset could help speed up false lookup if the slot is empty (because bitset is smaller than longArray, cache hit rate will be higher). In practice, the map is filled with 35% - 70% (use 50% as average), so only half of the false lookups can benefit of it, all others will pay the cost of load the bitset (still need to access the longArray anyway).\r\n\r\nFor aggregation, we always need to access the longArray (insert a new key after false lookup), also confirmed by a benchmark.\r\n\r\n For broadcast hash join, there could be a regression, but a simple benchmark showed that it may not (most of lookup are false):\r\n\r\n```\r\nsqlContext.range(1<<20).write.parquet(\"small\")\r\ndf = sqlContext.read.parquet('small')\r\nfor i in range(3):\r\n    t = time.time()\r\n    df2 = sqlContext.range(1<<26).selectExpr(\"id * 1111111111 % 987654321 as id2\")\r\n    df2.join(df, df.id == df2.id2).count()\r\n    print time.time() -t\r\n```\r\n\r\nHaving bitset (used time in seconds):\r\n```\r\n17.5404241085\r\n10.2758829594\r\n10.5786800385\r\n```\r\nAfter removing bitset (used time in seconds):\r\n```\r\n21.8939979076\r\n12.4132959843\r\n9.97224712372\r\n``` \r\n\r\ncc @rxin @nongli "},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/153893245","html_url":"https://github.com/apache/spark/pull/9452#issuecomment-153893245","issue_url":"https://api.github.com/repos/apache/spark/issues/9452","id":153893245,"user":{"login":"JoshRosen","id":50748,"avatar_url":"https://avatars.githubusercontent.com/u/50748?v=3","gravatar_id":"","url":"https://api.github.com/users/JoshRosen","html_url":"https://github.com/JoshRosen","followers_url":"https://api.github.com/users/JoshRosen/followers","following_url":"https://api.github.com/users/JoshRosen/following{/other_user}","gists_url":"https://api.github.com/users/JoshRosen/gists{/gist_id}","starred_url":"https://api.github.com/users/JoshRosen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoshRosen/subscriptions","organizations_url":"https://api.github.com/users/JoshRosen/orgs","repos_url":"https://api.github.com/users/JoshRosen/repos","events_url":"https://api.github.com/users/JoshRosen/events{/privacy}","received_events_url":"https://api.github.com/users/JoshRosen/received_events","type":"User","site_admin":false},"created_at":"2015-11-04T22:43:22Z","updated_at":"2015-11-04T22:43:22Z","body":"LGTM, so I'm going to merge this to master (1.6)."}}