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.christ...@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 > > >
