[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15985629#comment-15985629 ] ASF GitHub Bot commented on FLINK-3722: --- Github user heytitle commented on the issue: https://github.com/apache/flink/pull/3511 @greghogan May I ask you how to remove `FLINK-3722` commits?. Only way I can think of is `git rebase -i`, but this will rewrite history of this PR. > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Sub-task > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > Fix For: 1.3.0 > > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15985213#comment-15985213 ] ASF GitHub Bot commented on FLINK-3722: --- Github user greghogan commented on the issue: https://github.com/apache/flink/pull/3511 @heytitle please remove the old FLINK-3722 commits and rebase to master. > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Sub-task > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > Fix For: 1.3.0 > > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15985203#comment-15985203 ] ASF GitHub Bot commented on FLINK-3722: --- Github user asfgit closed the pull request at: https://github.com/apache/flink/pull/2628 > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Sub-task > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15592186#comment-15592186 ] ASF GitHub Bot commented on FLINK-3722: --- Github user ggevay commented on the issue: https://github.com/apache/flink/pull/2628 > I transcribed Quicksort so as to remove considerations of Java performance and inlining. It was not clear to me that if we encapsulated the index, page number, and page offset into an object that Java would inline the various increment and decrement functions. Also, I don't think this looks too bad. I'm happy to reformat if that is preferred. OK, I would say that it is OK like this, but let's see what the others will say. > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Sub-task > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15591881#comment-15591881 ] ASF GitHub Bot commented on FLINK-3722: --- Github user greghogan commented on the issue: https://github.com/apache/flink/pull/2628 Thanks @ggevay for reviewing. I added a commit with additional comments. I transcribed `Quicksort` so as to remove considerations of Java performance and inlining. It was not clear to me that if we encapsulated the index, page number, and page offset into an object that Java would inline the various increment and decrement functions. Also, I don't think this looks too bad. I'm happy to reformat if that is preferred. I think this is the best time to investigate alternative methods. I'm not seeing how one would sort on top of `InMemorySorter` without deserializing records. > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Sub-task > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[
https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15591734#comment-15591734
]
ASF GitHub Bot commented on FLINK-3722:
---
Github user ggevay commented on a diff in the pull request:
https://github.com/apache/flink/pull/2628#discussion_r84248344
--- Diff:
flink-runtime/src/main/java/org/apache/flink/runtime/operators/sort/QuickSort.java
---
@@ -49,20 +49,40 @@ protected static int getMaxDepth(int x) {
* then switch to {@link HeapSort}.
*/
public void sort(final IndexedSortable s, int p, int r) {
- sortInternal(s, p, r, getMaxDepth(r - p));
+ int recordsPerSegment = s.recordsPerSegment();
+ int recordSize = s.recordSize();
+
+ int maxOffset = recordSize * (recordsPerSegment - 1);
+
+ int size = s.size();
+ int sizeN = size / recordsPerSegment;
+ int sizeO = (size % recordsPerSegment) * recordSize;
+
+ sortInternal(s, recordsPerSegment, recordSize, maxOffset, 0, 0,
0, size, sizeN, sizeO, getMaxDepth(r - p));
}
public void sort(IndexedSortable s) {
sort(s, 0, s.size());
}
- private static void sortInternal(final IndexedSortable s, int p, int r,
int depth) {
+ private static void sortInternal(final IndexedSortable s, int
recordsPerSegment, int recordSize, int maxOffset,
+ int p, int pN, int pO, int r, int rN, int rO, int
depth) {
--- End diff --
Could you please add a comment that explains all these parameters? (I
understand them only because I know the original code and also what you are
trying to achieve, but for someone who sees the code for the first time this
will be quite scary.)
> The divisions in the InMemorySorters' swap/compare methods hurt performance
> ---
>
> Key: FLINK-3722
> URL: https://issues.apache.org/jira/browse/FLINK-3722
> Project: Flink
> Issue Type: Sub-task
> Components: Local Runtime
>Reporter: Gabor Gevay
>Assignee: Greg Hogan
>Priority: Minor
> Labels: performance
>
> NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods
> use divisions (which take a lot of time \[1\]) to calculate the index of the
> MemorySegment and the offset inside the segment. [~greghogan] reported on the
> mailing list \[2\] measuring a ~12-14% performance effect in one case.
> A possibility to improve the situation is the following:
> The way that QuickSort mostly uses these compare and swap methods is that it
> maintains two indices, and uses them to call compare and swap. The key
> observation is that these indices are mostly stepped by one, and
> _incrementally_ calculating the quotient and modulo is actually easy when the
> index changes only by one: increment/decrement the modulo, and check whether
> the modulo has reached 0 or the divisor, and if it did, then wrap-around the
> modulo and increment/decrement the quotient.
> To implement this, InMemorySorter would have to expose an iterator that would
> have the divisor and the current modulo and quotient as state, and have
> increment/decrement methods. Compare and swap could then have overloads that
> take these iterators as arguments.
> \[1\] http://www.agner.org/optimize/instruction_tables.pdf
> \[2\]
> http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15574672#comment-15574672 ] ASF GitHub Bot commented on FLINK-3722: --- Github user StephanEwen commented on the issue: https://github.com/apache/flink/pull/2628 Thanks for these cool experiments. Looks like a nice improvement. I'll try to dig into your code in the next days... > The divisions in the InMemorySorters' swap/compare methods hurt performance > --- > > Key: FLINK-3722 > URL: https://issues.apache.org/jira/browse/FLINK-3722 > Project: Flink > Issue Type: Improvement > Components: Local Runtime >Reporter: Gabor Gevay >Assignee: Greg Hogan >Priority: Minor > Labels: performance > > NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods > use divisions (which take a lot of time \[1\]) to calculate the index of the > MemorySegment and the offset inside the segment. [~greghogan] reported on the > mailing list \[2\] measuring a ~12-14% performance effect in one case. > A possibility to improve the situation is the following: > The way that QuickSort mostly uses these compare and swap methods is that it > maintains two indices, and uses them to call compare and swap. The key > observation is that these indices are mostly stepped by one, and > _incrementally_ calculating the quotient and modulo is actually easy when the > index changes only by one: increment/decrement the modulo, and check whether > the modulo has reached 0 or the divisor, and if it did, then wrap-around the > modulo and increment/decrement the quotient. > To implement this, InMemorySorter would have to expose an iterator that would > have the divisor and the current modulo and quotient as state, and have > increment/decrement methods. Compare and swap could then have overloads that > take these iterators as arguments. > \[1\] http://www.agner.org/optimize/instruction_tables.pdf > \[2\] > http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15570510#comment-15570510 ] ASF GitHub Bot commented on FLINK-3722: --- GitHub user greghogan opened a pull request: https://github.com/apache/flink/pull/2628 [FLINK-3722] [runtime] Don't / and % when sorting Replace division and modulus with addition and subtraction. The timing chart below has three columns for two Gelly algorithms with increasing scale. The first is timings for the master branch. The second column replaces division and modulus with shift-and-bitmask by storing each element in a power-of-2 chunk of memory. The third column is for this PR which modifies the sort algorithm to track the buffer number and offset for each index. This code has the advantage that there is no wasted memory. In this comparison, for both int and long, we look to be already operating on power-of-2 size elements. I would expect this PR to perform relatively better with the FixedLengthRecordSorter instrumented from FLINK-4705 where shift-and-bitmask would be padding elements. This initial PR does not modify `HeapSort`. I wanted to first get acceptance for the current set of modifications. There are further optimizations which can be benchmarked in follow-on tickets. ``` HITS, scale=16, INT : runtime= 1.618 (8) 1.524 (8) ( -5.82%) 1.546 (8) ( -4.47%) HITS, scale=16, LONG : runtime= 1.579 (8) 1.552 (8) ( -1.76%) 1.541 (8) ( -2.43%) HITS, scale=16, STRING: runtime= 1.774 (8) 1.739 (8) ( -1.99%) 1.701 (8) ( -4.11%) HITS, scale=17, INT : runtime= 2.032 (8) 1.950 (8) ( -4.06%) 1.937 (8) ( -4.71%) HITS, scale=17, LONG : runtime= 1.986 (8) 1.923 (8) ( -3.15%) 1.926 (8) ( -3.01%) HITS, scale=17, STRING: runtime= 2.377 (8) 2.275 (8) ( -4.30%) 2.289 (8) ( -3.68%) HITS, scale=18, INT : runtime= 2.894 (8) 2.761 (8) ( -4.59%) 2.762 (8) ( -4.54%) HITS, scale=18, LONG : runtime= 2.863 (8) 2.754 (8) ( -3.81%) 2.735 (8) ( -4.48%) HITS, scale=18, STRING: runtime= 3.683 (8) 3.455 (8) ( -6.18%) 3.461 (8) ( -6.02%) HITS, scale=19, INT : runtime= 4.914 (8) 4.631 (8) ( -5.76%) 4.595 (8) ( -6.49%) HITS, scale=19, LONG : runtime= 4.792 (8) 4.578 (8) ( -4.45%) 4.538 (8) ( -5.28%) HITS, scale=19, STRING: runtime= 6.484 (8) 6.149 (8) ( -5.18%) 6.118 (8) ( -5.64%) HITS, scale=20, INT : runtime= 8.662 (8) 8.086 (8) ( -6.64%) 8.091 (8) ( -6.59%) HITS, scale=20, LONG : runtime= 8.407 (8) 7.993 (8) ( -4.93%) 7.918 (8) ( -5.82%) HITS, scale=20, STRING: runtime= 11.946 (8) 11.327 (8) ( -5.18%) 11.272 (8) ( -5.64%) HITS, scale=21, INT : runtime= 16.248 (8) 15.137 (8) ( -6.84%) 15.207 (8) ( -6.41%) HITS, scale=21, LONG : runtime= 15.907 (8) 14.750 (8) ( -7.28%) 14.724 (8) ( -7.44%) HITS, scale=21, STRING: runtime= 23.634 (8) 22.596 (8) ( -4.39%) 22.546 (8) ( -4.61%) HITS, scale=22, INT : runtime= 31.964 (8) 29.954 (8) ( -6.29%) 29.808 (8) ( -6.74%) HITS, scale=22, LONG : runtime= 31.244 (8) 29.241 (8) ( -6.41%) 28.829 (8) ( -7.73%) HITS, scale=22, STRING: runtime= 47.870 (6) 45.942 (6) ( -4.03%) 45.987 (8) ( -3.93%) HITS, scale=23, INT : runtime= 65.146 (4) 60.245 (4) ( -7.52%) 60.008 (4) ( -7.89%) HITS, scale=23, LONG : runtime= 64.770 (4) 59.828 (4) ( -7.63%) 59.334 (4) ( -8.39%) HITS, scale=23, STRING: runtime= 103.690 (2) 99.335 (2) ( -4.20%) 98.919 (3) ( -4.60%) HITS, scale=24, INT : runtime= 156.567 (2)138.923 (2) (-11.27%) 141.185 (2) ( -9.82%) HITS, scale=24, LONG : runtime= 141.904 (2)132.292 (2) ( -6.77%) 129.677 (2) ( -8.62%) HITS, scale=24, STRING: runtime= 221.081 (1)217.128 (1) ( -1.79%) 213.822 (1) ( -3.28%) HITS, scale=25, INT : runtime= 280.720 (1) HITS, scale=25, LONG : runtime= 321.418 (1)297.764 (1) ( -7.36%) 293.982 (1) ( -8.54%) JaccardIndex, scale=12, INT : runtime= 0.413 (8) 0.424 (8) ( 2.57%) 0.408 (8) ( -1.30%) JaccardIndex, scale=12, LONG : runtime= 0.440 (8) 0.414 (8) ( -5.85%) 0.424 (8) ( -3.64%) JaccardIndex, scale=12, STRING: runtime= 0.667 (8) 0.647 (8) ( -2.91%) 0.644 (8) ( -3.38%) JaccardIndex, scale=13, INT : runtime= 0.811 (8) 0.743 (8) ( -8.45%) 0.764 (8) ( -5.75%) JaccardIndex, scale=13, LONG : runtime= 0.885 (8) 0.822 (8) ( -7.12%) 0.805 (8) ( -9.01%) JaccardIndex, scale=13, STRING: runtime= 1.599 (8) 1.489 (8) ( -6.86%) 1.486 (8) ( -7.04%) JaccardIndex, scale=14, INT : runtime= 1.809 (8) 1.621 (8) (-10.43%)
[jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
[
https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15234931#comment-15234931
]
Stephan Ewen commented on FLINK-3722:
-
Good observation.
How about implementing the QuickSort directly on the {{InMemorySorter}} - then
the offsets can be computed by adding/subtracting the key/pointer length.
This could still fall back to a heap sort, if the quicksort degenerates.
> The divisions in the InMemorySorters' swap/compare methods hurt performance
> ---
>
> Key: FLINK-3722
> URL: https://issues.apache.org/jira/browse/FLINK-3722
> Project: Flink
> Issue Type: Improvement
> Components: Distributed Runtime
>Reporter: Gabor Gevay
>Priority: Minor
> Labels: performance
>
> NormalizedKeySorter's and FixedLengthRecordSorter's swap and compare methods
> use divisions (which take a lot of time \[1\]) to calculate the index of the
> MemorySegment and the offset inside the segment. [~greghogan] reported on the
> mailing list \[2\] measuring a ~12-14% performance effect in one case.
> A possibility to improve the situation is the following:
> The way that QuickSort mostly uses these compare and swap methods is that it
> maintains two indices, and uses them to call compare and swap. The key
> observation is that these indices are mostly stepped by one, and
> _incrementally_ calculating the quotient and modulo is actually easy when the
> index changes only by one: increment/decrement the modulo, and check whether
> the modulo has reached 0 or the divisor, and if it did, then wrap-around the
> modulo and increment/decrement the quotient.
> To implement this, InMemorySorter would have to expose an iterator that would
> have the divisor and the current modulo and quotient as state, and have
> increment/decrement methods. Compare and swap could then have overloads that
> take these iterators as arguments.
> \[1\] http://www.agner.org/optimize/instruction_tables.pdf
> \[2\]
> http://apache-flink-mailing-list-archive.1008284.n3.nabble.com/DISCUSS-Macro-benchmarking-for-performance-tuning-and-regression-detection-td11078.html
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
