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)