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
