[FLINK-4868] Insertion sort could avoid the swaps

• Type: Sub-task
• Status: Reopened
• Priority: Not a Priority
• Resolution: Unresolved
• Component/s: Runtime / Task
• Labels: performance
• Assignee: Unassigned
• Reporter: Gábor Gévay
• Created: 20/Oct/16 16:09
• Updated: 29/Jul/21 07:35

Description

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.

Issue Links

• links to: GitHub Pull Request #4868