Bug in parallel sorting of float / double

[Doug Lea]

It's too bad that floating-point ordering issues that apparently no one
cares about (no reports) limit performance, but the solution seems OK.

Also: I've been reviewing drafts of this update for a year. They seem
OK. (Although they are very much focused on details of existing
primitive types; most likely a different approach will work better with
value/inline types.)

-Doug

On 7/24/19 9:15 AM, David Holmes wrote:
> 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
>>
>