Hi, I integrated locally the complete DPQS 19.2 patch from Vladimir Yaroslavskiy with up-to-date jdk14 (client) repository: build OK and jtreg passed OK (java/util/Arrays).
Here is the corresponding webrev for review: http://cr.openjdk.java.net/~lbourges/dpqs/dpqs-8226297/webrev/ Cheers, Laurent Le ven. 12 juil. 2019 à 09:34, Laurent Bourgès <bourges.laur...@gmail.com> a écrit : > 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 >> > >> > -- -- Laurent Bourgès
