flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-3722) The divisions in the InMemorySorters' swap/compare methods hurt performance
Date Thu, 20 Oct 2016 12:50:58 GMT

    [ https://issues.apache.org/jira/browse/FLINK-3722?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15591734#comment-15591734

ASF GitHub Bot commented on FLINK-3722:

Github user ggevay commented on a diff in the pull request:

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

View raw message