[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16212755#comment-16212755
]
ASF GitHub Bot commented on FLINK-4868:
---------------------------------------
Github user vim-wj closed the pull request at:
https://github.com/apache/flink/pull/4868
> Insertion sort could avoid the swaps
> ------------------------------------
>
> Key: FLINK-4868
> URL: https://issues.apache.org/jira/browse/FLINK-4868
> Project: Flink
> Issue Type: Sub-task
> Components: Local Runtime
> Reporter: Gabor Gevay
> Priority: Minor
> Labels: performance
>
> This is about the fallback to insertion sort at the beginning of
> {{QuickSort.sortInternal}}. It is quite a hot code as it runs every time when
> we are at the bottom of the quick sort recursion tree.
> The inner loop does a series of swaps on adjacent elements for moving a block
> of several elements one slot to the right and inserting the ith element at
> the hole. However, it would be faster to first copy the ith element to a temp
> location, and then move the block of elements to the right without swaps, and
> then copy the original ith element to the hole.
> Moving the block of elements without swaps could be achieved by calling
> {{UNSAFE.copyMemory}} only once for every element (as opposed to the three
> calls in {{MemorySegment.swap}} currently being done).
> (Note that I'm not sure whether {{UNSAFE.copyMemory}} is like memmove or like
> memcpy, so I'm not sure if we can do the entire block of elements with maybe
> even one {{UNSAFE.copyMemory}}.)
> Note that the threshold for switching to the insertion sort could probably be
> increased after this.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
