Re[2]: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
Hi Brent, see my comments inline: >Четверг, 1 августа 2019, 9:23 +03:00 от Laurent Bourgès >: > >Hi Brent, > >Le jeu. 1 août 2019 à 02:32, Brent Christian < brent.christ...@oracle.com > a >écrit : >>Thanks, Laurent. I can sponsor this fix, get a RFR thread going for >>JDK-8226297, keep webrevs updated as the review progresses, etc. Thank you for review! > >Excellent, I will let you and Vladimir work on this review. > >FYI I have implemented DPQS (int[] ) sorting 2 arrays (values + indices) in >the Marlin renderer. It could be generalized to any array type and having the >index array is very important in many algorithms... > >> >>However I've uncovered an issue with the fix that should be resolved >>before proceeding. >> >>Specifically, the new Arrays.COMMON_PARALLELISM static constant causes >>exceptions at startup under some circumstances: >> * running with LANG=C on Linux[1] >> * setting a property value with non-Ascii characters on Mac[2] >> >>java.util.Arrays is used a fair bit for String handling >>(java.lang.StringCoding, java.langStringLatin1, etc). The problem is >>that early in startup, depending on the locale/language setup and/or >>property settings, java.util.Arrays can be called during initialization >>of system properties. >> >>During Arrays., COMMON_PARALLELISM is setup with a call to >>ForkJoinPool.getCommonPoolParallelism(). ForkJoinPool sets up >>some VarHandles, VarHandles leads to >>MethodHandleStatics., which reads some system properties. But >>we're still initializing the system properties - 'props' is null, so NPE. > >Chicken-egg problem. Maybe this field could be wrapped in a getter doing lazy >resolution... >> >>I think Arrays.java needs to remove the COMMON_PARALLELISM constant, and >>go back to making calls to ForkJoinPool.getCommonPoolParallelism(). > >I do not know why Vladimir changed that recently. Any good reason ? >> >>I can do the update and post an updated webrev (unless further >>discussion is needed). Yes, please, remove COMMON_PARALLELISM constant and replace by call ForkJoinPool.getCommonPoolParallelism(). in parallelSort() methods. Please, go ahead and update webrev with corrected Arrays.java >> >PS: I can help on benchmarking as I developed a fair sort benchmark based on >JMH: >https://github.com/bourgesl/nearly-optimal-mergesort-code > >JMH test code: >https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/src/main/java/edu/sorting/bench >I would be interested by improving the perf test code and possibly integrate >it in OpenJDK JMH test suite... (later) > >Goodbye & good luck, >Laurent -- Vladimir Yaroslavskiy
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
Hi Brent, Le jeu. 1 août 2019 à 02:32, Brent Christian a écrit : > Thanks, Laurent. I can sponsor this fix, get a RFR thread going for > JDK-8226297, keep webrevs updated as the review progresses, etc. > Excellent, I will let you and Vladimir work on this review. FYI I have implemented DPQS (int[] ) sorting 2 arrays (values + indices) in the Marlin renderer. It could be generalized to any array type and having the index array is very important in many algorithms... > However I've uncovered an issue with the fix that should be resolved > before proceeding. > > Specifically, the new Arrays.COMMON_PARALLELISM static constant causes > exceptions at startup under some circumstances: > * running with LANG=C on Linux[1] > * setting a property value with non-Ascii characters on Mac[2] > > java.util.Arrays is used a fair bit for String handling > (java.lang.StringCoding, java.langStringLatin1, etc). The problem is > that early in startup, depending on the locale/language setup and/or > property settings, java.util.Arrays can be called during initialization > of system properties. > > During Arrays., COMMON_PARALLELISM is setup with a call to > ForkJoinPool.getCommonPoolParallelism(). ForkJoinPool sets up > some VarHandles, VarHandles leads to > MethodHandleStatics., which reads some system properties. But > we're still initializing the system properties - 'props' is null, so NPE. > Chicken-egg problem. Maybe this field could be wrapped in a getter doing lazy resolution... > I think Arrays.java needs to remove the COMMON_PARALLELISM constant, and > go back to making calls to ForkJoinPool.getCommonPoolParallelism(). > I do not know why Vladimir changed that recently. Any good reason ? > I can do the update and post an updated webrev (unless further > discussion is needed). > PS: I can help on benchmarking as I developped a fair sort benchmark based on JMH: https://github.com/bourgesl/nearly-optimal-mergesort-code JMH test code: https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/src/main/java/edu/sorting/bench I would be interested by improving the perf test code and possibly integrate it in OpenJDK JMH test suite... (later) > Goodbye & good luck, Laurent
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
Thanks, Laurent. I can sponsor this fix, get a RFR thread going for JDK-8226297, keep webrevs updated as the review progresses, etc. However I've uncovered an issue with the fix that should be resolved before proceeding. Specifically, the new Arrays.COMMON_PARALLELISM static constant causes exceptions at startup under some circumstances: * running with LANG=C on Linux[1] * setting a property value with non-Ascii characters on Mac[2] java.util.Arrays is used a fair bit for String handling (java.lang.StringCoding, java.langStringLatin1, etc). The problem is that early in startup, depending on the locale/language setup and/or property settings, java.util.Arrays can be called during initialization of system properties. During Arrays., COMMON_PARALLELISM is setup with a call to ForkJoinPool.getCommonPoolParallelism(). ForkJoinPool sets up some VarHandles, VarHandles leads to MethodHandleStatics., which reads some system properties. But we're still initializing the system properties - 'props' is null, so NPE. I think Arrays.java needs to remove the COMMON_PARALLELISM constant, and go back to making calls to ForkJoinPool.getCommonPoolParallelism(). I can do the update and post an updated webrev (unless further discussion is needed). Thanks, -Brent 1. FWIW, additional JNU_CHECK_EXCEPTION_RETURN calls were needed to produce this stack trace: Error occurred during initialization of VM java.lang.ExceptionInInitializerError at java.lang.invoke.VarHandle.(java.base/VarHandle.java:2052) at java.lang.invoke.VarHandles.makeFieldHandle(java.base/VarHandles.java:71) at java.lang.invoke.MethodHandles$Lookup.getFieldVarHandleCommon(java.base/MethodHandles.java:3147) at java.lang.invoke.MethodHandles$Lookup.getFieldVarHandle(java.base/MethodHandles.java:3107) at java.lang.invoke.MethodHandles$Lookup.findVarHandle(java.base/MethodHandles.java:2229) at java.util.concurrent.ForkJoinPool.(java.base/ForkJoinPool.java:3184) at java.util.Arrays.(java.base/Arrays.java:436) at java.lang.StringLatin1.newString(java.base/StringLatin1.java:767) at java.lang.StringBuilder.toString(java.base/StringBuilder.java:446) at sun.nio.cs.StandardCharsets.toLower(java.base/StandardCharsets.java:1284) at sun.nio.cs.StandardCharsets.lookup(java.base/StandardCharsets.java:1304) at sun.nio.cs.StandardCharsets.charsetForName(java.base/StandardCharsets.java:1338) at java.nio.charset.Charset.lookup2(java.base/Charset.java:471) at java.nio.charset.Charset.lookup(java.base/Charset.java:460) at java.nio.charset.Charset.isSupported(java.base/Charset.java:501) at jdk.internal.util.SystemProps$Raw.platformProperties(java.base/Native Method) at jdk.internal.util.SystemProps$Raw.(java.base/SystemProps.java:233) at jdk.internal.util.SystemProps.initProperties(java.base/SystemProps.java:54) at java.lang.System.initPhase1(java.base/System.java:2001) Caused by: java.lang.NullPointerException at java.lang.invoke.MethodHandleStatics.(java.base/MethodHandleStatics.java:62) at java.lang.invoke.VarHandle.(java.base/VarHandle.java:2052) at java.lang.invoke.VarHandles.makeFieldHandle(java.base/VarHandles.java:71) at java.lang.invoke.MethodHandles$Lookup.getFieldVarHandleCommon(java.base/MethodHandles.java:3147) at java.lang.invoke.MethodHandles$Lookup.getFieldVarHandle(java.base/MethodHandles.java:3107) at java.lang.invoke.MethodHandles$Lookup.findVarHandle(java.base/MethodHandles.java:2229) at java.util.concurrent.ForkJoinPool.(java.base/ForkJoinPool.java:3184) at java.util.Arrays.(java.base/Arrays.java:436) at java.lang.StringLatin1.newString(java.base/StringLatin1.java:767) at java.lang.StringBuilder.toString(java.base/StringBuilder.java:446) at sun.nio.cs.StandardCharsets.toLower(java.base/StandardCharsets.java:1284) at sun.nio.cs.StandardCharsets.lookup(java.base/StandardCharsets.java:1304) at sun.nio.cs.StandardCharsets.charsetForName(java.base/StandardCharsets.java:1338) at java.nio.charset.Charset.lookup2(java.base/Charset.java:471) at java.nio.charset.Charset.lookup(java.base/Charset.java:460) at java.nio.charset.Charset.isSupported(java.base/Charset.java:501) at jdk.internal.util.SystemProps$Raw.platformProperties(java.base/Native Method) at jdk.internal.util.SystemProps$Raw.(java.base/SystemProps.java:233) at jdk.internal.util.SystemProps.initProperties(java.base/SystemProps.java:54) at java.lang.System.initPhase1(java.base/System.java:2001) 2. I tried setting java.io.tmpdir to include a non-ascii character (e.g. ï ): Error occurred during initialization of VM java.lang.ExceptionInInitializerError at java.lang.invoke.VarHandle.(java.base/VarHandle.java:2052) at java.lang.invoke.VarHandles.makeFieldHandle(java.base/VarHandles.java:71) at
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
Hi all, I updated the DPQS patch thanks to latest release from Vladimir ([image: Pièces jointes]2019.07.25): http://cr.openjdk.java.net/~lbourges/dpqs/dpqs-8226297/dpqs-8226297.1/ " Updated version of Arrays and DualPivotQuicksort files, the summary of changes: 1. Corrected minimal threshold for parallelism argument (0 -> 1) 2. Added constant for common parallelism 3. Updated byte / char / short counting sort. " Incremental patch change: http://cr.openjdk.java.net/~lbourges/dpqs/dpqs-8226297/diff_dpqs_1_vs_0.log Cheers, Laurent Le mer. 17 juil. 2019 à 17:12, Laurent Bourgès a écrit : > 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 >
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
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 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 > 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
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
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 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 > > >
Re: The final optimized version of Dual-Pivot Quicksort (ver.19.1)
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
The final optimized version of Dual-Pivot Quicksort (ver.19.1)
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
