kou opened a new pull request #8612:
URL: https://github.com/apache/arrow/pull/8612
Summary:
* Deprecate SortToIndices()
* Add SortIndices() because we use "sort_indices" as kernel name in
#7240
* Add support for sort indices in descending order on Array
* Rename existing "sort_indices" kernel to "array_sort_indices" and
introduce "sort_indices" meta function to support RecordBatch and
Table
Benchmark:
Summary:
* No performance regression in existing sort on array
* Same performance as sort on array when the number of sort keys is 1
* 1.5x-100x slower than sort on array when the number of sort keys is 2
Before:
----------------------------------------------------------------------------------
Benchmark Time
CPU
----------------------------------------------------------------------------------
SortToIndicesInt64Count/32768/10000/min_time:1.000 15685 ns
15682 ns
SortToIndicesInt64Count/32768/100/min_time:1.000 15961 ns
15957 ns
SortToIndicesInt64Count/32768/10/min_time:1.000 16473 ns
16469 ns
SortToIndicesInt64Count/32768/2/min_time:1.000 27993 ns
27987 ns
SortToIndicesInt64Count/32768/1/min_time:1.000 5609 ns
5608 ns
SortToIndicesInt64Count/32768/0/min_time:1.000 13143 ns
13141 ns
SortToIndicesInt64Count/1048576/1/min_time:1.000 134695 ns
134670 ns
SortToIndicesInt64Count/8388608/1/min_time:1.000 1243992 ns
1243260 ns
SortToIndicesInt64Compare/32768/10000/min_time:1.000 193632 ns
193595 ns
SortToIndicesInt64Compare/32768/100/min_time:1.000 194876 ns
194837 ns
SortToIndicesInt64Compare/32768/10/min_time:1.000 182362 ns
182324 ns
SortToIndicesInt64Compare/32768/2/min_time:1.000 111607 ns
111584 ns
SortToIndicesInt64Compare/32768/1/min_time:1.000 5642 ns
5641 ns
SortToIndicesInt64Compare/32768/0/min_time:1.000 190302 ns
190268 ns
SortToIndicesInt64Compare/1048576/1/min_time:1.000 134743 ns
134718 ns
SortToIndicesInt64Compare/8388608/1/min_time:1.000 1261404 ns
1249362 ns
After:
-------------------------------------------------------------------------------------
Benchmark Time
CPU
-------------------------------------------------------------------------------------
ArraySortIndicesInt64Count/32768/10000/min_time:1.000 14769 ns
14766 ns
ArraySortIndicesInt64Count/32768/100/min_time:1.000 15207 ns
15204 ns
ArraySortIndicesInt64Count/32768/10/min_time:1.000 15892 ns
15889 ns
ArraySortIndicesInt64Count/32768/2/min_time:1.000 30107 ns
30100 ns
ArraySortIndicesInt64Count/32768/1/min_time:1.000 5509 ns
5508 ns
ArraySortIndicesInt64Count/32768/0/min_time:1.000 12699 ns
12696 ns
ArraySortIndicesInt64Count/1048576/1/min_time:1.000 132585 ns
132557 ns
ArraySortIndicesInt64Count/8388608/1/min_time:1.000 1236596 ns
1235842 ns
ArraySortIndicesInt64Compare/32768/10000/min_time:1.000 193259 ns
193217 ns
ArraySortIndicesInt64Compare/32768/100/min_time:1.000 190010 ns
189973 ns
ArraySortIndicesInt64Compare/32768/10/min_time:1.000 179923 ns
179879 ns
ArraySortIndicesInt64Compare/32768/2/min_time:1.000 111100 ns
111074 ns
ArraySortIndicesInt64Compare/32768/1/min_time:1.000 5660 ns
5659 ns
ArraySortIndicesInt64Compare/32768/0/min_time:1.000 186521 ns
186476 ns
ArraySortIndicesInt64Compare/1048576/1/min_time:1.000 132863 ns
132832 ns
ArraySortIndicesInt64Compare/8388608/1/min_time:1.000 1266383 ns
1265765 ns
TableSortIndicesInt64Count/32768/10000/min_time:1.000 21812 ns
21807 ns
TableSortIndicesInt64Count/32768/100/min_time:1.000 22494 ns
22490 ns
TableSortIndicesInt64Count/32768/10/min_time:1.000 17300 ns
17296 ns
TableSortIndicesInt64Count/32768/2/min_time:1.000 29927 ns
29921 ns
TableSortIndicesInt64Count/32768/1/min_time:1.000 5877 ns
5875 ns
TableSortIndicesInt64Count/32768/0/min_time:1.000 20394 ns
20390 ns
TableSortIndicesInt64Count/1048576/1/min_time:1.000 132904 ns
132871 ns
TableSortIndicesInt64Count/8388608/1/min_time:1.000 1342693 ns
1341943 ns
TableSortIndicesInt64Compare/32768/10000/min_time:1.000 203163 ns
203106 ns
TableSortIndicesInt64Compare/32768/100/min_time:1.000 199531 ns
199477 ns
TableSortIndicesInt64Compare/32768/10/min_time:1.000 185968 ns
185916 ns
TableSortIndicesInt64Compare/32768/2/min_time:1.000 113571 ns
113540 ns
TableSortIndicesInt64Compare/32768/1/min_time:1.000 6251 ns
6249 ns
TableSortIndicesInt64Compare/32768/0/min_time:1.000 183650 ns
183609 ns
TableSortIndicesInt64Compare/1048576/1/min_time:1.000 131701 ns
131674 ns
TableSortIndicesInt64Compare/8388608/1/min_time:1.000 1264413 ns
1263622 ns
TableSortIndicesInt64Int64/32768/10000/min_time:1.000 313368 ns
313310 ns
TableSortIndicesInt64Int64/32768/100/min_time:1.000 313425 ns
313361 ns
TableSortIndicesInt64Int64/32768/10/min_time:1.000 337051 ns
336987 ns
TableSortIndicesInt64Int64/32768/2/min_time:1.000 402063 ns
401973 ns
TableSortIndicesInt64Int64/32768/1/min_time:1.000 254660 ns
254612 ns
TableSortIndicesInt64Int64/32768/0/min_time:1.000 305887 ns
305815 ns
TableSortIndicesInt64Int64/1048576/1/min_time:1.000 11157920 ns
11155020 ns
TableSortIndicesInt64Int64/8388608/1/min_time:1.000 106529839 ns
106501576 ns
Follow-up tasks:
* Improve performance when the number of sort keys is 2 or greater
* Idea1: Use counting sort for small range data like on array
* Idea2: Use threading and merge sort
* Add support multi-column partition Nth indices on Table
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
