[
https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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)
