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...@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, > Vladimir > > -------------------------------------------------------------------- > [1] http://cr.openjdk.java.net/~alanb/DualPivotSortUpdate/webrev.01/ > -------------------------------------------------------------------- >
