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

[Laurent Bourgès]

Hi,
I asked alan to update the webrev, but I can publish it myself...

Will do it asap,
Stay tuned,
Laurent

Le mar. 9 juil. 2019 à 22:19, Brent Christian <brent.christian at oracle.com>
a écrit :

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