flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gabor Gevay (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
Date Sat, 09 Apr 2016 10:40:25 GMT
Gabor Gevay created FLINK-3722:

             Summary: 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

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

View raw message