[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Flink Jira Bot updated FLINK-4868:
----------------------------------
Labels: auto-closed performance (was: performance stale-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: Minor
> Labels: auto-closed, 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)
