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

[Tagir Valeev]

Hello, Laurent, Vladimir!

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=100 (55000110) (n=100, µ=102.6177, σ=7.4065714)
avg-ms=95.62607(+/- 4 %),
algo=TopDownMergesort+iscutoff=24+checkSorted=true, n=100
(55000110) (n=100, µ=95.62607, σ=3.5302947)
avg-ms=118.73089(+/- 4 %),
algo=BottomUpMergesort+minRunLen=24+checkSorted=true, n=100
(55000110) (n=100, µ=118.73089, σ=4.464908)
avg-ms=108.36175(+/- 4 %), algo=MarlinSort, n=100 (55000110)
(n=100, µ=108.36175, σ=4.5998554)
avg-ms=99.68292(+/- 4 %), algo=MarlinMergeSort, n=100
(55000110) (n=100, µ=99.68292, σ=3.9944465)
avg-ms=75.43999(+/- 3 %), algo=DualPivotQuicksort2018, n=100
(55000110) (n=100, µ=75.43999, σ=2.6127808)
avg-ms=83.80406(+/- 6 %), algo=DualPivotQuicksort2018Ext, n=100
 (55000110) (n=100, µ=83.80406, σ=4.734225)
avg-ms=18.886326(+/- 4 %), algo=RadixSort, n=100 (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
 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  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 
> > a écrit :
> >
> >> Hi Vladimir,
> >>
> >> Thank you for your attention, you are the Sort Master.
> >>
> >>
> >> Le ven. 9 nov. 2018 à 09:02, Vladimir Yaroslavskiy 
> >> 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([], 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 

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

[Laurent Bourgès]

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  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 
> a écrit :
>
>> Hi Vladimir,
>>
>> Thank you for your attention, you are the Sort Master.
>>
>>
>> Le ven. 9 nov. 2018 à 09:02, Vladimir Yaroslavskiy 
>> 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([], 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).
>>>
>>
>> Perfect, I started adapting your code and will share soon the link to my
>> github repo.
>>
>>
>>> Thank you,
>>> Vladimir
>>>
>>
>> Thank you very much for your first thoughts,
>> Laurent
>>
>>
>>> Пятница, 9 ноября 2018, 10:44 +03:00 от Laurent Bourgès <
>>> bourges.laur...@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 >> 

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

[Laurent Bourgès]

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  a
écrit :

> Hi Vladimir,
>
> Thank you for your attention, you are the Sort Master.
>
>
> Le ven. 9 nov. 2018 à 09:02, Vladimir Yaroslavskiy  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([], 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).
>>
>
> Perfect, I started adapting your code and will share soon the link to my
> github repo.
>
>
>> Thank you,
>> Vladimir
>>
>
> Thank you very much for your first thoughts,
> Laurent
>
>
>> Пятница, 9 ноября 2018, 10:44 +03:00 от Laurent Bourgès <
>> bourges.laur...@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 > > 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.
>>
>> 

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

[Laurent Bourgès]

Hi Vladimir,

Thank you for your attention, you are the Sort Master.


Le ven. 9 nov. 2018 à 09:02, Vladimir Yaroslavskiy  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([], 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).
>

Perfect, I started adapting your code and will share soon the link to my
github repo.


> Thank you,
> Vladimir
>

Thank you very much for your first thoughts,
Laurent


> Пятница, 9 ноября 2018, 10:44 +03:00 от Laurent Bourgès <
> bourges.laur...@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  > 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
> 
> *