{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/13680","repository_url":"https://api.github.com/repos/apache/spark","labels_url":"https://api.github.com/repos/apache/spark/issues/13680/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/13680/comments","events_url":"https://api.github.com/repos/apache/spark/issues/13680/events","html_url":"https://github.com/apache/spark/pull/13680","id":160346862,"number":13680,"title":"[SPARK-15962][SQL] Introduce implementation with a dense format for UnsafeArrayData","user":{"login":"kiszk","id":1315079,"avatar_url":"https://avatars.githubusercontent.com/u/1315079?v=3","gravatar_id":"","url":"https://api.github.com/users/kiszk","html_url":"https://github.com/kiszk","followers_url":"https://api.github.com/users/kiszk/followers","following_url":"https://api.github.com/users/kiszk/following{/other_user}","gists_url":"https://api.github.com/users/kiszk/gists{/gist_id}","starred_url":"https://api.github.com/users/kiszk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kiszk/subscriptions","organizations_url":"https://api.github.com/users/kiszk/orgs","repos_url":"https://api.github.com/users/kiszk/repos","events_url":"https://api.github.com/users/kiszk/events{/privacy}","received_events_url":"https://api.github.com/users/kiszk/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":53,"created_at":"2016-06-15T06:22:50Z","updated_at":"2016-07-06T10:12:49Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/13680","html_url":"https://github.com/apache/spark/pull/13680","diff_url":"https://github.com/apache/spark/pull/13680.diff","patch_url":"https://github.com/apache/spark/pull/13680.patch"},"body":"## What changes were proposed in this pull request?\r\n\r\nThis PR introduces more compact representation for ```UnsafeArrayData```.\r\n\r\n```UnsafeArrayDataSparse``` accepts ```null``` value in each entry of an array by using indirect index. However, it increases memory footprint (e.g. 1.6x for an integer array) due to existence of [```offsets``` area](https://github.com/apache/spark/blob/43b149fb885a27f9467aab28e5195f6f03aadcf0/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/UnsafeArrayData.java#L35). This PR represents ```null``` value in each entry of an array by using bitvector without indirect index. The new format can reduce memory footprint and improve performance of accessing each element.\r\n\r\nExample of memory foot comparison:\r\n1024x1024 elements integer array\r\nSize of ```baseObject``` for ```UnsafeArrayData```: 4 + 1024x1024 + 1024x1024 = 2M bytes\r\nSize of ```baseObject``` for ```UnsafeArrayData```: 4 + 1024x1024/8 + 1024x1024 = 1.25M bytes\r\n\r\nHere are performance results of benchmark programs:\r\n\r\n1.3x and 1.3x performance improvements\r\n````\r\nJava HotSpot(TM) 64-Bit Server VM 1.8.0_92-b14 on Mac OS X 10.10.4\r\nIntel(R) Core(TM) i5-5257U CPU @ 2.70GHz\r\n\r\nWithout SPARK-15962\r\nRead UnsafeArrayData:                    Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                            373 /  377        450.0           2.2       1.0X\r\nDouble                                         380 /  390        441.8           2.3       1.0X\r\n\r\nWith SPARK-15962\r\nRead UnsafeArrayData:                    Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                            279 /  294        600.4           1.7       1.0X\r\nDouble                                         296 /  303        567.0           1.8       0.9X\r\n````\r\n\r\n3.1x and 2.3x performance improvements\r\n````\r\nOpenJDK 64-Bit Server VM 1.8.0_91-b14 on Linux 4.0.4-301.fc22.x86_64\r\nIntel Xeon E3-12xx v2 (Ivy Bridge)\r\n\r\nWithout SPARK-15962\r\nWrite UnsafeArrayData:                   Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                            246 /  253        681.2           1.5       1.0X\r\nDouble                                         323 /  327        519.5           1.9       0.8X\r\n\r\nWith SPARK-15962\r\nWrite UnsafeArrayData:                   Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                             79 /   86       2124.2           0.5       1.0X\r\nDouble                                         140 /  147       1201.0           0.8       0.6X\r\n````\r\n\r\n2.6x and 1.6x performance improvements\r\n````\r\nOpenJDK 64-Bit Server VM 1.8.0_91-b14 on Linux 4.0.4-301.fc22.x86_64\r\nIntel Xeon E3-12xx v2 (Ivy Bridge)\r\n\r\nWithout SPARK-15962\r\nGet primitive array from UnsafeArrayData: Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                            205 /  426        307.0           3.3       1.0X\r\nDouble                                         330 /  362        190.5           5.2       0.6X\r\n\r\nWith SPARK-15962\r\nGet primitive array from UnsafeArrayData: Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                             80 /  151        783.4           1.3       1.0X\r\nDouble                                         208 /  366        302.8           3.3       0.4X\r\n````\r\n\r\n3.5x and 1.7x performance improvements\r\n````\r\nOpenJDK 64-Bit Server VM 1.8.0_91-b14 on Linux 4.0.4-301.fc22.x86_64\r\nIntel Xeon E3-12xx v2 (Ivy Bridge)\r\n\r\nWithout SPARK-15962\r\nCreate UnsafeArrayData from primitive array: Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                            241 /  371        261.4           3.8       1.0X\r\nDouble                                         419 /  524        150.2           6.7       0.6X\r\n\r\nWith SPARK-15962\r\nCreate UnsafeArrayData from primitive array: Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nInt                                             68 /  144        920.4           1.1       1.0X\r\nDouble                                         240 /  302        261.7           3.8       0.3X\r\n````\r\n\r\n1.7x and 1.1x performance improvements in ```UDTSerializationBenchmark```\r\n````\r\nJava HotSpot(TM) 64-Bit Server VM 1.8.0_92-b14 on Mac OS X 10.10.4\r\nIntel(R) Core(TM) i5-5257U CPU @ 2.70GHz\r\n\r\nWithout SPARK-15962\r\nVectorUDT de/serialization:              Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nserialize                                      650 /  704          0.0      650331.9       1.0X\r\ndeserialize                                    317 /  349          0.0      317066.7       2.1X\r\n\r\nWith SPARK-15962\r\nVectorUDT de/serialization:              Best/Avg Time(ms)    Rate(M/s)   Per Row(ns)   Relative\r\n------------------------------------------------------------------------------------------------\r\nserialize                                      389 /  431          0.0      389020.7       1.0X\r\ndeserialize                                    276 /  311          0.0      276168.4       1.4X\r\n````\r\n\r\n## How was this patch tested?\r\n\r\nAdded unit tests into ```UnsafeArraySuite```\r\n"},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/230732791","html_url":"https://github.com/apache/spark/pull/13680#issuecomment-230732791","issue_url":"https://api.github.com/repos/apache/spark/issues/13680","id":230732791,"user":{"login":"SparkQA","id":8108735,"avatar_url":"https://avatars.githubusercontent.com/u/8108735?v=3","gravatar_id":"","url":"https://api.github.com/users/SparkQA","html_url":"https://github.com/SparkQA","followers_url":"https://api.github.com/users/SparkQA/followers","following_url":"https://api.github.com/users/SparkQA/following{/other_user}","gists_url":"https://api.github.com/users/SparkQA/gists{/gist_id}","starred_url":"https://api.github.com/users/SparkQA/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SparkQA/subscriptions","organizations_url":"https://api.github.com/users/SparkQA/orgs","repos_url":"https://api.github.com/users/SparkQA/repos","events_url":"https://api.github.com/users/SparkQA/events{/privacy}","received_events_url":"https://api.github.com/users/SparkQA/received_events","type":"User","site_admin":false},"created_at":"2016-07-06T10:12:49Z","updated_at":"2016-07-06T10:12:49Z","body":"**[Test build #61839 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/61839/consoleFull)** for PR 13680 at commit [`65fca21`](https://github.com/apache/spark/commit/65fca217d05ee97a72b10f7e1e80662db62feb3d)."}}
{"actor":{"display_login":"SparkQA"}}