RFR: 8226297: Dual-pivot quicksort improvements
Brent Christian
brent.christian at oracle.com
Fri Oct 25 05:28:39 UTC 2019
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
>
More information about the core-libs-dev
mailing list