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 AM Zheka Kozlov <orionllm...@gmail.com> wrote: > > 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 the numbers are the way they are. Use profilers (see -prof, -lprof), > design factorial > experiments, perform baseline and negative tests that provide experimental > control, make sure > the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from > the domain experts. > Do not assume the numbers tell you what you want them to tell. > > Benchmark (size) Mode Cnt Score Error Units > Sort.dualPivot 10 avgt 4 0,012 ? 0,002 us/op > Sort.dualPivot 1000 avgt 4 0,282 ? 0,014 us/op > Sort.dualPivot 100000 avgt 4 31,625 ? 10,063 us/op > Sort.dualPivot 10000000 avgt 4 10077,948 ? 601,204 us/op > Sort.radix 10 avgt 4 1,310 ? 0,151 us/op > Sort.radix 1000 avgt 4 1,297 ? 0,063 us/op > Sort.radix 100000 avgt 4 33,009 ? 2,303 us/op > Sort.radix 10000000 avgt 4 10150,036 ? 1095,015 us/op > > I don't want to make any conclusions. These are just numbers. Probably your > implementation can be optimized so it beats the platform sort at least on > large arrays. > > вс, 11 нояб. 2018 г. в 11:48, Tagir Valeev <amae...@gmail.com>: >> >> 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 (reusing merge sort part from JDK) which degrades to >> merge sort if array is nearly sorted. >> http://cr.openjdk.java.net/~tvaleev/patches/radix/RadixSort.java >> >> With best regards, >> Tagir Valeev. >> >> On Fri, Jan 19, 2018 at 8:38 PM Vladimir Yaroslavskiy >> <vlv.spb...@mail.ru> wrote: >> > >> > 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, >> > Vladimir >> > >> > -------------------------------------------------------------------- >> > [1] http://cr.openjdk.java.net/~alanb/DualPivotSortUpdate/webrev.01/ >> > --------------------------------------------------------------------
