RFR: 8226297: Dual-pivot quicksort improvements

[Brent Christian]

Hi, Vladimir

Thanks for the explanation of the changes to LONG_RUN_LENGTHS and 
SHORT_RUN_LENGTHS.

I've incorporated the other suggested changes:
http://cr.openjdk.java.net/~bchristi/8226297/webrev10/

-Brent

On 10/24/19 4:30 AM, Vladimir Yaroslavskiy wrote:
> Hi Brent,
> 
> See my comments inline
> 
>     Oct 24б 2019, 7:42 +03:00 от Brent Christian
>     <brent.christian at oracle.com>:
> 
>     Hi,
> 
>     I've created a webrev of the latest test changes that Vladimir sent me:
> 
>     http://cr.openjdk.java.net/~bchristi/8226297/webrev09-testUpdate/
> 
>     (I also created an incremental webrev[1] along the way, in case that's
>     helpful to anyone).
> 
>     I have just a few comments:
> 
>     test/jdk/java/util/Arrays/Sorting.java
> 
>     * I found some instances of "FloatPointing", which I've already changed
>     to "FloatingPoint". :)
> 
>     --
> 
> 
> Thank you for correction.
> 
> 
>            // Array lengths used in a long run (default)
>            private static final int[] LONG_RUN_LENGTHS = {
>     - 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
>     + 1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
> 
>            // Array lengths used in a short run
>            private static final int[] SHORT_RUN_LENGTHS = {
>     - 1, 2, 3, 21, 55, 1000, 10000 };
>     + 1, 8, 55, 100, 10_000 };
> 
>     Vladimir, can you tell me why some of the length values have been
>     removed?
> 
>     --
> 
> 
> Different sorting algorithms are invoked depending on input size. Insertion
> sort is run on small arrays, but, for example, sizes 5 and 8 are similar for
> insertion sort. Therefore, the list contains few small sizes only. Larger
> sizes are used for Quicksort, merging sort, parallel sort.
> 
> There was requirement to have fast runs (short and long) as much as 
> possible.
> Testing with 1M elements took almost all time, but didn't invoke new 
> functionality.
> I removed 1M and time of long run was down from 10 min to 2.5 min, short run
> takes about 5-7 sec instead of 15-20 sec.
> 
> As a result, I achieved reasonable testing time with coverage of all cases,
> excluding checks like, throw new IllegalArgumentException("Unknown type 
> of array...
> 
> 
>     1570 private static enum TypeConverter {
>     ...
>     1637 abstract void convert(Object src, Object dst);
> 
>     The 'src' argument to convert is always cast to an int[]. Can it be
>     made an int[] in the method signature, instead of Object ? I can make
>     the change if that sounds good.
> 
> 
> Good catch! Please, switch to void convert(int[] a, Object dst)
> and remove int[] a = (int[]) src; from all implementation methods.
> 
> And could you also please delete unnecessary code?
> 
> Lines 1509-1510:
> 
> if (src instanceof int[]) {
>       copy((int[]) dst, (int[]) src);
> in method private void copy(Object dst, Object src)
> 
> and then whole method at lines 1520-1522:
> private void copy(int[] dst, int[] src)
> 
> Method copy is invoked on float/double arrays only,
> not necessary to compare with int[].
> 
> Thanks,
> Vladimir
> 
> 
>     Other than those, this is pretty much ready to go.
> 
>     Thanks,
>     -Brent
> 
>     1. http://cr.openjdk.java.net/~bchristi/8226297/webrev09-incremental/
> 
>     On 10/8/19 5:41 PM, Brent Christian wrote:
>      > Hi, Vladimir
>      >
>      > On 10/8/19 3:18 PM, Vladimir Yaroslavskiy wrote:
>      >>
>      >> The following renaming changes are important
>      >> and should be kept. My explanation is here
>      > > ...
>      >
>      > Thanks for the explanation - much appreciated.
>      >
>      >> * Other changes, like failed -> fail, i++ -> ++i,
>      >> and TypeConverter, FloatBuilder, DoubleBuilder, SortedBuilder
>      >> to be non-static can be reverted.
>      >>
>      >> I can revert them, if you agree.
>      >
>      > That would be great, thanks.
>      >
>      >>     * I like that the various DualPivotQuickSort methods are tested
>      >>     directly (via SortingHelper). I'd prefer that we also
>     continue testing
>      >>     direct calls to Arrays.sort(), as that's what users will
>     call. What
>      >>     would be the best way to add that back in? (Maybe a
>     SortingHelper
>      >>     variant that calls Arrays.sort()?).
>      >>
>      >> I will add direct calls to Arrays.sort() and
>     Arrays.parallelSort() also.
>      >
>      > Great, thank you.
>      >
>      >>     * Having the test operation depend on setting various values
>     to the
>      >>     static 'sortingHelper' field seems brittle to me. This could
>     be a good
>      >>     opportunity to convert from static to instance methods, make
>      >>     'sortingHelper' and 'name' member variables, and create separate
>      >>     Sorting
>      >>     objects for each SortingHelper. Such a refactoring is not
>     strictly
>      >>     necessary, but I think it would be nice to have.
>      >>
>      >> Good idea, I will implement it and send you update version very
>     soon.
>      >
>      > Sounds good!
>      >
>      >>>     test/jdk/java/util/Arrays/FailedFloat.java
>      >>>
>      >>>     Is this test necessary, given the addition of
>      >>>     testFloatNegativeZero() in
>      >>>     Sorting.java ?
>      >>
>      >> Not necessary, because testFloatNegativeZero() covers this case.
>      >> This class was created to reproduce bug when float-pointing zeros
>      >> and NaNs are sorted.
>      >>
>      >> Please remove FailedFloat.java. It makes sense to add the source of
>      >> this class to 8226297.
>      >
>      > Done and done.
>      >
>      > -Brent
>