flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gabor Gevay (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-4868) Insertion sort could avoid the swaps
Date Thu, 20 Oct 2016 16:09:59 GMT
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

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

View raw message