[ https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17329821#comment-17329821 ]
Flink Jira Bot commented on FLINK-4868: --------------------------------------- This issue has been labeled "stale-minor" for 7 days. It is closed now. If you are still affected by this or would like to raise the priority of this ticket please re-open, removing the label "auto-closed" and raise the ticket priority accordingly. > 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: performance, stale-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}}.) > 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)