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%) 1.649 (8) ( -8.87%)
JaccardIndex, scale=14, LONG : runtime= 2.003 (8) 1.834 (8) (
-8.43%) 1.800 (8) (-10.13%)
JaccardIndex, scale=14, STRING: runtime= 3.855 (8) 3.666 (8) (
-4.91%) 3.667 (8) ( -4.86%)
JaccardIndex, scale=15, INT : runtime= 4.693 (8) 4.158 (8)
(-11.40%) 4.148 (8) (-11.62%)
JaccardIndex, scale=15, LONG : runtime= 5.205 (8) 4.936 (8) (
-5.17%) 4.712 (8) ( -9.48%)
JaccardIndex, scale=15, STRING: runtime= 10.882 (8) 10.429 (8) (
-4.16%) 10.529 (8) ( -3.24%)
JaccardIndex, scale=16, INT : runtime= 13.504 (8) 11.852 (8)
(-12.24%) 12.124 (8) (-10.22%)
JaccardIndex, scale=16, LONG : runtime= 14.933 (8) 13.482 (8) (
-9.72%) 13.279 (8) (-11.08%)
JaccardIndex, scale=16, STRING: runtime= 31.802 (8) 30.549 (8) (
-3.94%) 30.910 (8) ( -2.80%)
JaccardIndex, scale=17, INT : runtime= 36.742 (8) 32.542 (8)
(-11.43%) 33.193 (8) ( -9.66%)
JaccardIndex, scale=17, LONG : runtime= 40.648 (6) 37.355 (6) (
-8.10%) 36.786 (8) ( -9.50%)
JaccardIndex, scale=17, STRING: runtime= 89.418 (4) 84.632 (4) (
-5.35%) 86.596 (4) ( -3.16%)
JaccardIndex, scale=18, INT : runtime= 102.126 (4) 91.521 (4)
(-10.38%) 90.900 (4) (-10.99%)
JaccardIndex, scale=18, LONG : runtime= 121.389 (3) 113.324 (3) (
-6.64%) 112.323 (4) ( -7.47%)
JaccardIndex, scale=18, STRING: runtime= 251.373 (2) 240.014 (2) (
-4.52%) 243.849 (2) ( -2.99%)
JaccardIndex, scale=19, INT : runtime= 286.927 (1) 254.767 (1)
(-11.21%) 260.911 (2) ( -9.07%)
JaccardIndex, scale=19, LONG : runtime= 331.742 (1) 303.246 (1) (
-8.59%) 301.764 (2) ( -9.04%)
```
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/greghogan/flink
3722_the_divisions_in_the_inmemorysorters_swapcompare_methods_hurt_performance
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/flink/pull/2628.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #2628
----
commit 3283ef6e994ff831f1bb04d075a32995de8596c4
Author: Greg Hogan <[email protected]>
Date: 2016-10-05T20:13:02Z
[FLINK-3722] [runtime] Don't / and % when sorting
Replace division and modulus with addition and subtraction.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
