Bug in parallel sorting of float / double

[David Holmes]

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
>