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

Hi Vladimir, One short comment, see below: Le jeu. 15 nov. 2018 à 15:39, Vladimir Yaroslavskiy a écrit : > Hello, Tagir! > > I compared Radix sort with Dual-Pivot Quicksort and see > that Radix sort is faster than DPQ (on 2M elements) on random data in > twice times, > but it works slower on

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

Hi all Sorting experts, I want to let you know I am building a Sorting benchmark suite myself based on contributions of Sebastian Wild (forked github repo) & Vladimir on github (MIT license): https://github.com/bourgesl/nearly-optimal-mergesort-code I hope to exploit JMH in a short future to

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

Hello, Tagir! I compared Radix sort with Dual-Pivot Quicksort and see that Radix sort is faster than DPQ (on 2M elements) on random data in twice times, but it works slower on repeated elements (in 3-7 times). For highly structured arrays merging sort is invoked in both cases. Other data types -

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

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, Vladimir >Среда, 14 ноября 2018, 19:17 +03:00 от Tagir

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

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 +

Re: The new optimized version of Dual-Pivot Quicksort

Thanks, Tagir. The benchmark was indeed incorrect. There was also another mistake: dualPivot() and radix() sorted different arrays. I believe I fixed it now: https://gist.github.com/orionll/595d10ff37ffe0d8c3824e734055cf00 Benchmark (seed)(size) Mode Cnt Score Error

Re: The new optimized version of Dual-Pivot Quicksort

Hello, Zheka! Seems that your benchmark is wrong: after the first iteration (which is part of warmup) you're always sorting an array which is already sorted, so in fact you are testing how algorithms behave on already sorted arrays. With best regards, Tagir Valeev. On Mon, Nov 12, 2018 at 10:08

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

Dear Vladimir, No information about JMH benchmarking. > I like it as Alexey made the best framework to benchmark short operations, like sorting small arrays. For example, 1000 ints ~ 0.05ms on my i7 laptop at fixed freq = 2ghz. I use Bentley's test suite to compare algorithms. > Is it

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

Hi Laurent, No information about JMH benchmarking. I use Bentley's test suite to compare algorithms. >Понедельник, 12 ноября 2018, 13:06 +03:00 от Laurent Bourgès >: > >Hi, > >Do you know if someone has written a complete JMH benchmark suite dedicated to >Arrays.sort() ? >with varying array

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

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

Re: The new optimized version of Dual-Pivot Quicksort

Hi Tagir! I wrote a simple benchmark comparing Arrays.sort() and your implementation: https://gist.github.com/orionll/595d10ff37ffe0d8c3824e734055cf00 Here are the results on my computer (JDK 11): REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on why

Re: The new optimized version of Dual-Pivot Quicksort

Hello! By the way why not using radix sort, at least for int[] arrays? The implementation is much simpler, it uses constant-size additional buffer (1024 ints) and performance should be better than DPQS, at least for large arrays. Here's sample implementation written by me several years ago

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

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

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

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

Re: The new optimized version of Dual-Pivot Quicksort

Hi, One more thing: if you have any advice on my code, datasets, or algorithmic approach, please give me your feedback/comments. Here is the Marlin MergeSort: http://hg.openjdk.java.net/jdk/jdk/file/190b77982361/src/java.desktop/share/classes/sun/java2d/marlin/MergeSort.java Laurent Le ven. 9

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

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. As to new method sort(a[], low, high, indices): do you mean this method in Arrays class? Are you

Re: The new optimized version of Dual-Pivot Quicksort

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)

Re: The new optimized version of Dual-Pivot Quicksort

Hi Vladimir, Thanks. Quick update for those on the list: Doug and Vladimir are doing some more detailed performance analysis. Paul. > On Jan 19, 2018, at 5:38 AM, Vladimir Yaroslavskiy wrote: > > Hi team, > > In Sept 2009 Josh Bloch, Jon Bentley and I introduced new

The new optimized version of Dual-Pivot Quicksort

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