[jira] [Commented] (FLINK-4868) Insertion sort could avoid the swaps

["ASF GitHub Bot (JIRA)" <ji...@apache.org>]

    [ 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)