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

Brent Christian brent.christian at oracle.com
Thu Aug 1 00:33:04 UTC 2019


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.<clinit>, COMMON_PARALLELISM is setup with a call to 
ForkJoinPool.getCommonPoolParallelism().  ForkJoinPool<clinit> sets up 
some VarHandles, VarHandles<clinit> leads to 
MethodHandleStatics.<clinit>, 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.<clinit>(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.<clinit>(java.base/ForkJoinPool.java:3184)
	at java.util.Arrays.<clinit>(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.<init>(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.<clinit>(java.base/MethodHandleStatics.java:62)
	at java.lang.invoke.VarHandle.<clinit>(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.<clinit>(java.base/ForkJoinPool.java:3184)
	at java.util.Arrays.<clinit>(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.<init>(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.<clinit>(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:3140)
	at 
java.lang.invoke.MethodHandles$Lookup.getFieldVarHandle(java.base/MethodHandles.java:3100)
	at 
java.lang.invoke.MethodHandles$Lookup.findVarHandle(java.base/MethodHandles.java:2222)
	at 
java.util.concurrent.ForkJoinPool.<clinit>(java.base/ForkJoinPool.java:3184)
	at java.util.Arrays.<clinit>(java.base/Arrays.java:389)
	at java.lang.StringCoding.decodeUTF8_0(java.base/StringCoding.java:747)
	at java.lang.StringCoding.decodeUTF8(java.base/StringCoding.java:712)
	at java.lang.StringCoding.decode(java.base/StringCoding.java:231)
	at java.lang.String.<init>(java.base/String.java:483)
	at java.lang.String.<init>(java.base/String.java:553)
	at jdk.internal.util.SystemProps$Raw.vmProperties(java.base/Native Method)
	at 
jdk.internal.util.SystemProps$Raw.cmdProperties(java.base/SystemProps.java:253)
	at 
jdk.internal.util.SystemProps.initProperties(java.base/SystemProps.java:55)
	at java.lang.System.initPhase1(java.base/System.java:2001)
Caused by: java.lang.NullPointerException
	at 
java.lang.invoke.MethodHandleStatics.<clinit>(java.base/MethodHandleStatics.java:62)
	at java.lang.invoke.VarHandle.<clinit>(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:3140)
	at 
java.lang.invoke.MethodHandles$Lookup.getFieldVarHandle(java.base/MethodHandles.java:3100)
	at 
java.lang.invoke.MethodHandles$Lookup.findVarHandle(java.base/MethodHandles.java:2222)
	at 
java.util.concurrent.ForkJoinPool.<clinit>(java.base/ForkJoinPool.java:3184)
	at java.util.Arrays.<clinit>(java.base/Arrays.java:389)
	at java.lang.StringCoding.decodeUTF8_0(java.base/StringCoding.java:747)
	at java.lang.StringCoding.decodeUTF8(java.base/StringCoding.java:712)
	at java.lang.StringCoding.decode(java.base/StringCoding.java:231)
	at java.lang.String.<init>(java.base/String.java:483)
	at java.lang.String.<init>(java.base/String.java:553)
	at jdk.internal.util.SystemProps$Raw.vmProperties(java.base/Native Method)
	at 
jdk.internal.util.SystemProps$Raw.cmdProperties(java.base/SystemProps.java:253)
	at 
jdk.internal.util.SystemProps.initProperties(java.base/SystemProps.java:55)
	at java.lang.System.initPhase1(java.base/System.java:2001)


On 7/26/19 1:14 AM, Laurent Bourgès wrote:
> Hi all,
> 
> I updated the DPQS patch thanks to latest release from Vladimir (Pièces 
> jointes2019.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 
> <bourges.laurent at gmail.com <mailto:bourges.laurent at gmail.com>> 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
> 


More information about the core-libs-dev mailing list