Re[4]: The new optimized version of Dual-Pivot Quicksort

Wed Nov 14 16:30:29 UTC 2018

```Hello, Tagir!

Thank you for interesting news! I will look at RadixSort and let you know my result.

It may happen that int will be sorted by numeric-specific sorting algorithm
(like we switched byte, char, short to counting sort).

Regards,

>Среда, 14 ноября 2018, 19:17 +03:00 от Tagir Valeev <amaembo at gmail.com>:
>
>
>I created a pull request containing my RadixSort implementation:
>https://github.com/bourgesl/nearly-optimal-mergesort-code/pull/1
>On my machine the results produced by Mergesorts.java are like this:
>
>Runs with individual timing (skips first 10 runs):
>adjusted reps: 110 + inner loop: 1
>avg-ms=102.6177(+/- 7 %), algo=PeekSort+iscutoff=24+onlyIncRuns=false,
>n=1000000     (55000110) (n=100, µ=102.6177, σ=7.4065714)
>avg-ms=95.62607(+/- 4 %),
>algo=TopDownMergesort+iscutoff=24+checkSorted=true, n=1000000
>(55000110) (n=100, µ=95.62607, σ=3.5302947)
>avg-ms=118.73089(+/- 4 %),
>algo=BottomUpMergesort+minRunLen=24+checkSorted=true, n=1000000
>(55000110) (n=100, µ=118.73089, σ=4.464908)
>avg-ms=108.36175(+/- 4 %), algo=MarlinSort, n=1000000     (55000110)
>(n=100, µ=108.36175, σ=4.5998554)
>avg-ms=99.68292(+/- 4 %), algo=MarlinMergeSort, n=1000000
>(55000110) (n=100, µ=99.68292, σ=3.9944465)
>avg-ms=75.43999(+/- 3 %), algo=DualPivotQuicksort2018, n=1000000
>(55000110) (n=100, µ=75.43999, σ=2.6127808)
>avg-ms=83.80406(+/- 6 %), algo=DualPivotQuicksort2018Ext, n=1000000
> (55000110) (n=100, µ=83.80406, σ=4.734225)
>avg-ms=18.886326(+/- 4 %), algo=RadixSort, n=1000000     (55000110)
>(n=100, µ=18.886326, σ=0.75667334)
>
>As you can see RadixSort is much faster than anything. Well, probably
>there are some input patterns where it may lose (though it's
>performance is much more predictable and much less depend on input
>data than in DPQS), but I strongly believe that concentrating efforts
>on testing corner cases performance and integrating RadixSort into JDK
>would yield much better performance than DPQS, at least for int[]
>arrays. Also the implementation is much simpler.
>
>With best regards,
>Tagir Valeev.
>On Mon, Nov 12, 2018 at 5:09 PM Laurent Bourgès
>< bourges.laurent at gmail.com > wrote:
>>
>> Hi,
>>
>> Do you know if someone has written a complete JMH benchmark suite dedicated
>> to Arrays.sort() ?
>> with varying array size (trivial) but also testing lots of data
>> distributions: (see Vladimir's tests) and possibly all variants (int, long,
>> double, Object[] )
>>
>> It could be part of the standard OpenJDK JMH test suite...
>>
>> For now, I forked the nearly-optimal-mergesort repository on github:
>>  https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/results
>>
>> Cheers,
>> Laurent
>>
>> Le sam. 10 nov. 2018 à 12:49, Laurent Bourgès < bourges.laurent at gmail.com > a
>> écrit :
>>
>> > Dear Vladimir & other Java sort experts,
>> >
>> > I made the port of the DPQS 2018.2 code last night to support a secondary
>> > array to be sorted and use preallocation (aux/run for merge sort):
>> >
>> >  https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/src/wildinter/net/mergesort/DualPivotQuicksort2018Ext.java
>> >
>> > I succeded in using this variant in Marlin renderer (dev) and it is
>> > promising. I figured out a rendering bug in 1 test wigh 65535 random
>> > segments, certainly due to array swaps in mergesort (my side)...
>> >
>> > I will look again at my changes to check if I miss some permutation (a //
>> > b) or made any mistake on their indices... tricky.
>> >
>> > PS: Please share your updated webrev when possible to rebase my changes.
>> >
>> > Regards,
>> > Laurent
>> >
>> > Le ven. 9 nov. 2018 à 10:08, Laurent Bourgès < bourges.laurent at gmail.com >
>> > a écrit :
>> >
>> >>
>> >> Thank you for your attention, you are the Sort Master.
>> >>
>> >>
>> >> Le ven. 9 nov. 2018 à 09:02, Vladimir Yaroslavskiy < vlv.spb.ru at mail.ru >
>> >> a écrit :
>> >>
>> >>> Hi Laurent,
>> >>>
>> >>> The new version is still under review, there were a lot of suggestions
>> >>> and ideas from Doug Lea.
>> >>> I needed time to apply and check them. I'm going to send final version
>> >>> in few days.
>> >>>
>> >>
>> >> Excellent news, so it will ship in jdk12...
>> >>
>> >>>
>> >>> As to new method sort(a[], low, high, indices): do you mean this method
>> >>> in Arrays class?
>> >>> Are you going to extend Arrays API?
>> >>>
>> >>
>> >> I benchmarked my MergeSort and adding extra array implies many more
>> >> moves: thresholds should be adjusted and my sort is sometimes better as it
>> >> makes half moves (a <-> buffer swaps), so this complementary sort should
>> >> have its own tuned implementation (tests & benchmarks).
>> >>
>> >> I coded my sort as such need did not match any Arrays.sort() methods.
>> >> Having it publicly in jdk.base would be great for any other data handling
>> >> algorithm (science, AI ?)
>> >>
>> >> If you agree it is useful, I could try proposing an Arrays/Collection API
>> >> extension like :
>> >> sort(<primitive or Value>[], low, high, int[]indices)
>> >>
>> >>
>> >>> About new parameters workbase[]: method sort(...) in DualPivotQuicksort
>> >>> class (version is under review)
>> >>> has extra parameter - parallel context (Sorter sorter) which has
>> >>> required workbase[].
>> >>> If we run sorting sequentially, sorter parameter is null (no any
>> >>> objects) and temporary buffer
>> >>> will be created inside in tryMerge method if we go ahead with merging.
>> >>>
>> >>
>> >> I will have a look. For Marlin, parallel sort is not possible as
>> >> rendering shapes can be parallelized in the application (geoserver map
>> >> rendering).
>> >>
>> >>
>> >>> I will send new sources in few days and add you in cc, so you can look
>> >>> at it
>> >>> and find if new methods are acceptable for you. Then we can discuss
>> >>> required changes (if any).
>> >>>
>> >>
>> >> github repo.
>> >>
>> >>
>> >>> Thank you,
>> >>>
>> >>
>> >> Thank you very much for your first thoughts,
>> >> Laurent
>> >>
>> >>
>> >>> Пятница, 9 ноября 2018, 10:44 +03:00 от Laurent Bourgès <
>> >>>  bourges.laurent at gmail.com >:
>> >>>
>> >>> Hi,
>> >>>
>> >>> I am currently testing many sort algorithms to improve the Marlin
>> >>> renderer (AA 2D shape rasterizer), I integrated since OpenJDK9 and am still
>> >>> improving for OpenJDK12 .
>> >>>
>> >>> I created my MergeSort (top down, check for sorted parts, array / buffer
>> >>> swap to minimize moves, isort on small sub arrays) that sort 2 int[]:
>> >>> crossing + edge indices.
>> >>>  It is critical as edge crossings are sorted at every scanline, data are
>> >>> almost sorted/reversed, not really random.
>> >>>
>> >>> 3 questions:
>> >>> - why is this patch dormant ? I checked in openjdk12 repo and your
>> >>> changes were not integrated.
>> >>> - I need a sort() method that works with 2 arrays: data + indices
>> >>> (pointer like). Such sorted indices are useful to use for lookups c[idx[k]]
>> >>> or to perform other array permutations...
>> >>> Would you agree adding such new sort(a[], low, high, indices)
>> >>> - Marlin uses a ThreadLocal context to avoid any allocation. JDK sort()
>> >>> impl do not accept parameters to give any buffer[] and avoid allocations.
>> >>> Would you agree adding such optional parameters (like workbase[]) ?
>> >>>
>> >>> I will experiment adapting the DualPivotQuickSort in Marlin renderer and
>> >>> perform array sort race & rendering benchmarks.
>> >>>
>> >>> Cheers,
>> >>> Laurent
>> >>>
>> >>> Le ven. 19 janv. 2018 à 14:38, Vladimir Yaroslavskiy < vlv.spb.ru at mail.ru
>> >>> < https://e.mail.ru/compose/?mailto=mailto%3avlv.spb.ru@mail.ru >> a
>> >>> écrit :
>> >>>
>> >>> Hi team,
>> >>>
>> >>> In Sept 2009 Josh Bloch, Jon Bentley and I introduced new sorting
>> >>> algorithm, Dual-Pivot Quicksort, for primitives in JDK 7 and later
>> >>> I suggested several improvements of Dual-Pivot Quicksort, which
>> >>> were integrated into JDK 8.
>> >>>
>> >>> Now I have more optimized and faster version of Dual-Pivot Quicksort.
>> >>> I have been working on it for the last 5 years. Please, find the
>> >>> summary of changes below and sources / diff at webrev [1].
>> >>>
>> >>> All tests and benchmarking were run on the most recent build of JDK 10,
>> >>> jdk-10-ea+39. The new version shows the better performance on different
>> >>> inputs and guarantees n*log(n) on any data.
>> >>>
>> >>> The new implementation of Dual-Pivot Quicksort is 'all-in-one' version:
>> >>> it contains one code for both parallel and sequential sorting algorithms.
>> >>>
>> >>> Suggested version is 10-20% faster on random data, 1.5-4 times faster
>> >>> on nearly structured arrays, 1.5-2 times faster on period inputs.
>> >>>
>> >>> Parallel Dual-Pivot Quicksort is 1.5-3 times faster than current
>> >>> algorithm based on merge sort.
>> >>>
>> >>> Benchmarking on the test suite, suggested by Jon Bentley, shows the
>> >>> boost of performance in 1.4 times. This test suite contains several
>> >>> types of inputs, such as random data, nearly structured arrays, data
>> >>> with period and so on. Also there are several modifications of inputs
>> >>> and parameters which are used in data building. We run sorting on all
>> >>> combinations to compare two algorithms.
>> >>>
>> >>> Please let me know if you have any questions / comments.
>> >>>
>> >>> Summary of changes:
>> >>>
>> >>> DualPivotQuicksort class
>> >>> ------------------------
>> >>> * Pivots are chosen with another step, the 1-st and 5-th candidates
>> >>>    are taken as pivots instead of 2-nd and 4-th.
>> >>> * Splitting into parts is related to the golden ratio
>> >>> * Pivot candidates are sorted by combination of 5-element
>> >>>    network sorting + insertion sort
>> >>> * New backwards partitioning is simpler and more efficient
>> >>> * Quicksort tuning parameters were updated
>> >>> * Merging sort is invoked on each iteration from Quicksort
>> >>> * Additional steps for float/double were fully rewritten
>> >>> * Heap sort is invoked on the leftmost part
>> >>> * Heap sort is used as a guard against quadratic time
>> >>> * Parallel sorting is based on Dual-Pivot Quicksort
>> >>>    instead of merge sort
>> >>>
>> >>> SortingAlgorithms class
>> >>> -----------------------
>> >>> * Merging sort and pair insertion sort were moved from
>> >>>    DualPivotQuicksort class
>> >>> * Pair insertion sort was simplified and optimized
>> >>> * New nano insertion sort was introduced for tiny arrays
>> >>> * Merging sort was fully rewritten
>> >>> * Optimized merging partitioning is used
>> >>> * Merging parameters were updated
>> >>> * Merging of runs was fully rewritten
>> >>> * Fast version of heap sort was introduced
>> >>> * Parallel merging sort was also provided
>> >>>
>> >>> Sorting / ParallelSorting classes
>> >>> ---------------------------------
>> >>> * New test cases were added
>> >>> * Sources of these classes were unified
>> >>>
>> >>> Arrays class
>> >>> ------------
>> >>> * Calls of Dual-Pivot Quicksort were updated
>> >>> * Parallel sorting of primitives was switched to parallel
>> >>>    Dual-Pivot Quicksort
>> >>> * Javadoc was modified
>> >>>
>> >>> ArraysParallelSortHelpers class
>> >>> -------------------------------
>> >>> * Old implementation of parallel sorting for primitives was removed
>> >>> * Javadoc was updated
>> >>>
>> >>> Thank you,
>> >>>
>> >>> --------------------------------------------------------------------
>> >>> [1]  http://cr.openjdk.java.net/~alanb/DualPivotSortUpdate/webrev.01/
>> >>> --------------------------------------------------------------------
>> >>>
>> >>>
>> >>>
>> >>> --