Re[2]: RFR: 8226297: Dual-pivot quicksort improvements
Vladimir Yaroslavskiy
vlv.spb.ru at mail.ru
Thu Oct 24 11:30:22 UTC 2019
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