Bug in parallel sorting of float / double
David Holmes
david.holmes at oracle.com
Wed Jul 24 13:15:29 UTC 2019
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.holmes at 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
>
More information about the core-libs-dev
mailing list