The final optimized version of Dual-Pivot Quicksort (ver.19.1)

[Brent Christian]

Hi,

Is the webrev incomplete?  It only contains the changes for 
DualPivotQuicksort.java, and not for Arrays.java, etc.

Thanks,
-Brent

On 6/18/19 2:37 PM, Vladimir Yaroslavskiy wrote:
> Hi team,
> 
> Please review the final optimized version of Dual-Pivot Quicksort (ver.19.1),
> see http://cr.openjdk.java.net/~alanb/8226297/0/webrev
> (link to Jira task https://bugs.openjdk.java.net/browse/JDK-8226297)
> 
> The new version was published here more than one year ago (on Jan 19, 2018).
> Since that time Dual-Pivot Quicksort has been significantly improved
> and this work was done in collaboration with Doug Lea and Laurent Bourges.
> 
> You can find summary of all changes below.
> 
> DualPivotQuicksort.java
> ----------------------------------------------------------------------
> * The 1-st and 5-th candidates are taken as pivots
>    instead of 2-nd and 4-th
> * Pivots are chosen with another step
> * Pivot candidates are sorted by combination of
>    5-element network sorting and insertion sort
> * New backwards partitioning was introduced
> * Partitioning is related to the golden ratio
> * Quicksort tuning parameters were updated
> * Thresholds for byte / char / short sorting were updated
> * Additional steps for float / double were fully rewritten
> * Parallel sorting is based on combination of merge sort
>    and Dual-Pivot Quicksort
> * Pair insertion sort was optimized and became a part
>    of mixed insertion sort
> * Mixed insertion sort was introduced: combination
>    of simple insertion sort, pin insertion sort and
>    pair insertion sort
> * Simple insertion sort is invoked on tiny array
> * Pin insertion sort is started on small array
> * Pair insertion sort is continued on remain part
> * Merging of runs is invoked on each iteration of Quicksort
> * Merging of runs was fully rewritten
> * Optimal partitioning of merging is used
> * Not more than one copy of part to buffer during merging
> * Merging parameters were updated
> * Initial capacity of runs is based on size
> * Max number of runs is constant
> * Optimized version of heap sort was introduced
> * Heap sort is used as a guard against quadratic time
>    (int / long / float / double)
> * Parallel merging of runs was also provided
> * Parallel sorting, heap sort and merging of runs
>    are not used in byte / char / short sorting
> * Counting sort for byte / char / short were optimized
> * Counting sort is used as a guard against quadratic time
>    (byte / char / short)
> * Code style and javadoc improvements
> 
> Sorting.java
> ----------------------------------------------------------------------
> * New test cases were added
> * Test cases are invoked for both: sequential and
>    parallel sorting
> * Check for Object sorting was added
> * New tests were added against heap sort
> * Added test case against bug in parallel merge
>    sort on float / double data
> 
> ParallelSorting.java
> ----------------------------------------------------------------------
> * This class was removed, because Sorting class
>    covers all cases
> 
> SortingHelper.java
> ----------------------------------------------------------------------
> * The helper class provides access package-private
>    methods of DualPivotQuicksort class during testing
> 
> Arrays.java
> ----------------------------------------------------------------------
> * Calls of Dual-Pivot Quicksort were updated
> * Parallel sorting of primitives was switched to parallel
>    Dual-Pivot Quicksort
> * Javadoc was updated, double spaces were removed
> * Format changes
> 
> ArraysParallelSortHelpers.java
> ----------------------------------------------------------------------
> * Implementation of parallel sorting
>    for primitives was removed
> * Javadoc was updated
> 
> Thank you,
> Vladimir
>