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

[Laurent Bourgès]

Hi Brent,

Le jeu. 1 août 2019 à 02:32, Brent Christian <brent.christian at 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.
>

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

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