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

["Konstantin Knauf (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Konstantin Knauf updated FLINK-4868:
------------------------------------
      Labels: performance  (was: auto-closed performance)
    Priority: Not a Priority  (was: Minor)

> 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: Runtime / Task
>            Reporter: Gábor Gévay
>            Priority: Not a Priority
>              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
(v8.3.4#803005)