Bug in parallel sorting of float / double

[David Holmes]

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
>