[
https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Greg Hogan closed FLINK-3722.
-----------------------------
Resolution: Implemented
Implemented in 336b95d4eedc23e5ce37d1739165157e127c65f8
> 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)
