On Fri, 21 Nov 2025 13:47:16 GMT, Doug Lea <[email protected]> wrote:
>> Vladimir Yaroslavskiy has updated the pull request incrementally with one
>> additional commit since the last revision:
>>
>> JDK-8266431: Dual-Pivot Quicksort improvements
>>
>> * Added @java.io.Serial
>> * Added information about the best data types for thresholds of sorting
>> * Added comments about native implementation based on AVX512 instructions
>
> Some general comments:
>
> The structure intrinsically gets more complicated and harder to read as
> options and sub-options increase -- 6 kinds of sorts, some with parallel
> and/or SIMD, some only applying to some element types, almost all of them
> with incremental improvements. I think the attempts to better organize these
> is OK, but the main DualPiviotQuicksort should include a brief account
> similar to the wording in the PR intro to better explain how the dispatching
> criteria and logic. And perhaps a summary of constants and thresholds, with
> notes on sensitivity of values.
>
> The changes related to parallel sorting all look good to me. I didn't read
> the other parts in detail
Hi Doug Lea (@DougLea),
I'm improving the test coverage of sorting and found a bug in parallel sorting.
According to the javadoc object sorting Arrays.sort() and Arrays.parallelSort()
are _stable_ (keep the order of the elements with the same key). But a simple
test shows that parallel sort of objects doesn't work correctly. I take an
already sorted array of elements with the same key and iascending ndex to check
the order. Minimal array length to reproduce the bug is 16_385. Both parallel
sort methods, with and without comparator, failed:
`FAILED: not stable at i = 4096: [1, 12287] and [1, 0]`
Sequential sorting methods Arrays.sort(Object[]) and Arrays.sort(Object[],
Comparator) work fine. Please find the test.
import java.util.Arrays;
import java.util.Comparator;
public class ParallelStability {
private static final int LENGTH = 16_385;
public static void main(String[] args) {
Pair[] a = new Pair[LENGTH];
for (int i = 0; i < LENGTH; ++i) {
a[i] = new Pair(1, i);
}
Arrays.parallelSort(a); // failed
// Arrays.parallelSort(a, byKey); // failed
// Arrays.sort(a); // ok
// Arrays.sort(a, byKey); // ok
checkStability(a);
System.out.println("PASSED");
}
record Pair(int key, int index) implements Comparable<Pair> {
@Override
public int compareTo(Pair p) {
return Integer.compare(key , p.key);
}
@Override
public String toString() {
return "[" + key + ", " + index + "]";
}
}
private static final Comparator<Pair> byKey =
Comparator.comparingInt(Pair::key);
private static void checkStability(Pair[] a) {
for (int i = 1; i < a.length; ++i) {
if (a[i - 1].key == a[i].key && a[i - 1].index > a[i].index) {
System.out.println("FAILED: not stable at i = " + i + ": " +
a[i - 1] + " and " + a[i]);
System.exit(1);
}
}
}
}
Could you please look at it?
-------------
PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-5745967780
