Gabor Gevay created FLINK-4868:
----------------------------------
Summary: 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
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}}.)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
