Hi Vladimir,
On 24/07/2019 10:58 pm, Vladimir Yaroslavskiy wrote:
Hi David,
Please, see how it works: Arrays.parallelSort(double[])
invokes ArraysParallelSortHelpers.FJDouble.Sorter
if size is big enough and ForkJoinPool.getCommonPoolParallelism()) > 1.
FJDouble.Sorter divides given array into 4 parts, sorts them recursively
in parallel and merges these parts.
Finally DualPivotQuicksort is invoked on small parts and only on this
step NaNs and -0.0s are arranged.
In other words, NaNs and -0.0s are arranged inside each small parts, but
this action must be
done once before the first splitting of the array.
My understanding** was that the merge of the correctly sorted sub-arrays
would correctly cause NaNs to bubble to the end as required, while
zeroes would also group - though I think I can see now that simply using
< would not correctly order NaNs relative to other values, nor order
-0.0 and +0.0
** It's been 7 years since I helped Doug Lea put the parallelising code
into the JDK so I'm a bit rusty on the details :) and I'm surprised such
a bug has not been detected before now.
Cheers,
David
Thank you,
Vladimir
Среда, 24 июля 2019, 15:39 +03:00 от David Holmes
<david.hol...@oracle.com>:
Hi Vladimir,
On 24/07/2019 8:53 pm, Vladimir Yaroslavskiy wrote:
> Hi all,
>
> I've found bug in parallel sorting of float / double arrays in
the latest JDK.
>
> When float / double values are sorted, additional actions are
> required: NaNs must be moved to the end and negative zeros
> must be placed before positive zeros.
>
> Current implementation of Arrays.parallelSort(float[] / double [])
> invokes parallel merge sort from ArraysParallelSortHelpers class,
> but it doesn't arrange NaNs and -0.0.
It ultimately uses DualPivotQuicksort which AFAICS does have code to
arrange NaNS:
static void sort(float[] a, int left, int right,
float[] work, int workBase, int workLen) {
/*
* Phase 1: Move NaNs to the end of the array.
*/
while (left <= right && Float.isNaN(a[right])) {
--right;
}
and also order +/-0
/*
* Phase 3: Place negative zeros before positive zeros.
*/
where does the bug arise?
Thanks,
David
-----
> @Alan, Brent, Laurent
> Could you please file a bug?
>
> New optimized version of DualPivotQuicksort (which is under
review) works fine and
> doesn't contain this bug. Please, look at my test case to
reproduce it.
>
>
----------------------------------------------------------------------------------------------------------------------
> import java.util.Random;
>
> public class FailedFloat {
>
> private static final int MAX_N = (1 << 13) /*
Arrays.MIN_ARRAY_SORT_GRAN */ + 10;
>
> public static void main(String[] args) {
> float[] a = new float[MAX_N];
> random(a);
> java.util.Arrays.parallelSort(a);
> check(a);
> System.out.println("PASSED");
> }
>
> private static void random(float[] a) {
> Random random = new Random(777);
> for (int i = 0; i < MAX_N; i++) {
> a[i] = random.nextBoolean() ? -0.0f : 0.0f;
> }
> }
>
> private static void check(float[] a) {
> for (int i = 0; i < a.length - 1; ++i) {
> if (Float.floatToRawIntBits(a[i]) == 0 &&
Float.floatToRawIntBits(a[i + 1]) < 0) {
> throw new RuntimeException(a[i] + " goes before "+ a[i + 1] + "
at position " + i);
> }
> }
> }
> }
>
------------------------------------------------------------------------------------------------------------------------
> Thank you,
> Vladimir
