[jira] [Updated] (FLINK-4868) Insertion sort could avoid the swaps
[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Konstantin Knauf updated FLINK-4868:
Labels: performance (was: auto-closed performance)
Priority: Not a Priority (was: Minor)
> 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: Not a Priority
> Labels: performance
>
> 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)
[jira] [Updated] (FLINK-4868) Insertion sort could avoid the swaps
[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Flink Jira Bot updated FLINK-4868:
--
Labels: auto-closed performance (was: performance stale-minor)
> 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: auto-closed, performance
>
> 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)
[jira] [Updated] (FLINK-4868) Insertion sort could avoid the swaps
[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Flink Jira Bot updated FLINK-4868:
--
Labels: performance stale-minor (was: performance)
> 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)
[jira] [Updated] (FLINK-4868) Insertion sort could avoid the swaps
[
https://issues.apache.org/jira/browse/FLINK-4868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Gabor Gevay updated FLINK-4868:
---
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.
was:
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}}.)
> 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
> Labels: performance
>
> 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
(v6.3.4#6332)
