The new optimized version of Dual-Pivot Quicksort

Laurent Bourgès bourges.laurent at
Fri Nov 9 07:44:40 UTC 2018


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.


Le ven. 19 janv. 2018 à 14:38, Vladimir Yaroslavskiy < at> 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]
> --------------------------------------------------------------------

More information about the core-libs-dev mailing list