Re[2]: Bug in parallel sorting of float / double

[Vladimir Yaroslavskiy]

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.

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