Closed Bug 1294156 Opened 4 years ago Closed 3 years ago

Float32 RadixSort: NaNs with sign-bit set aren't sorted correctly

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla59
Tracking Status
firefox59 --- fixed

People

(Reporter: anba, Assigned: anba)

References

Details

Attachments

(1 file, 1 obsolete file)

Test case:
---
const qsort_limit = 127; // builtin/Sorting.js

var f32 = new Float32Array(qsort_limit + 1);
f32[0] = NaN;
f32[1] = NaN;
f32[2] = 1;

new Int32Array(f32.buffer)[1] |= 0x80000000;

f32.sort();

print([].toString.call(f32.filter(v => v !== 0)));
---

Expected: Prints "1,NaN,NaN"
Actual: Prints "NaN,1,NaN"


In addition to that problem, we actually need to canonicalize all NaNs to the default NaN value per 24.1.1.5 GetValueFromBuffer, step 9.b [1], because %TypedArrayPrototype%.sort invokes [[Get]] ([2, 3, 4]).


[1] https://tc39.github.io/ecma262/#sec-getvaluefrombuffer
[2] https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.sort
[3] https://tc39.github.io/ecma262/#sec-integer-indexed-exotic-objects-get-p-receiver
[4] https://tc39.github.io/ecma262/#sec-integerindexedelementget
I would like to work on this bug could someone help me with where to start off?
Float32Arrays are sorted in this function [1]: By interpreting the float32 values as int32 numbers, we can use radix sort instead of quicksort (with a bit of pre- and post-processing [2,3]) to sort the typed array. But here's the catch: The pre-processing step doesn't handle all NaN values correctly. So what we need to do is to detect NaN values and normalise them to the default canonical NaN value. The detection and canonicalisation steps can either be performed through the Float32Array [4] or through the Int32Array [5], you may want to test both alternatives and then decide which one is faster. 

[1] https://dxr.mozilla.org/mozilla-central/source/js/src/builtin/Sorting.js#96
[2] https://dxr.mozilla.org/mozilla-central/source/js/src/builtin/Sorting.js#116-127
[3] https://dxr.mozilla.org/mozilla-central/source/js/src/builtin/Sorting.js#141-148
[4] Float32Arrays automatically normalise NaN values when read from the underlying array buffer, that means an expression like |view[i] = view[i]| is sufficient to normalise a NaN value.
[5] Untested (!) bit-twiddling to detect and normalise NaN values:
```
if ((view[i] & 0x7F800000) === 0x7F800000 && (view[i] & 0x007FFFFF) !== 0) {
  // Canonicalize NaN (using the "smallest" QNaN), sign-bit already set.
  view[i] = 0x7FC00000 ^ signMask;
}
```
In my tests, using the Int32Array for detecting NaNs was slightly faster than using a Float32Array directly, but I could be wrong. Andre: I think I should add your testcase as well, but I'll do that after the patch gets reviewed.

All tests under /TypedArray pass, but I wasn't able to run the entire suite or test for performance regressions. :(
The patch looks good to me. Thank you! I'd give it a feedback+, but reviewboard doesn't appear to support the feedback flags yet. :mrrrgn should probably do the "official" review, so I'll reassign the review request to her.
@Sumit: You can safely ignore the following explanations. Well, unless you want to train your spec-fu. :-)

(In reply to André Bargull from comment #0)
> In addition to that problem, we actually need to canonicalize all NaNs to
> the default NaN value per 24.1.1.5 GetValueFromBuffer, step 9.b [1], because
> %TypedArrayPrototype%.sort invokes [[Get]] ([2, 3, 4]).

Actually this doesn't seem to be true:
%TypedArray%.prototype.sort and Array.prototype.sort don't require to call [[Set]] with a value previously returned by [[Get]] (!). So we can call [[Set]] with any value we'd like to, including different distinct NaN values. Using a different NaN value also won't violate the sort order post-condition from sort(), quoting 22.1.3.25 Array.prototype.sort:
---
There must be some mathematical permutation π of the nonnegative integers less than len, such that for every nonnegative integer j less than len, if property old[j] existed, then new[π(j)] is exactly the same value as old[j]. 
---

Note that the post-condition uses the wording "same value" which typically means value comparison using the SameValue algorithm (7.2.9 SameValue, https://tc39.github.io/ecma262/#sec-samevalue). And SameValue treats all NaN values as equivalent, so replacing a NaN value with a different NaN value won't violate the "same value" requirement.

That being said, partial NaN canonicalization already happens for Float64Arrays, so if we want to canonicalize all NaNs when calling sort(), we should do this for Float32 _and_ Float64 arrays. But this should happen in a separate bug, definitely not this one.
Attachment #8786599 - Flags: review?(andrebargull) → review?(winter2718)
Thanks for doing all of this André and Sumit. Looking at the patch now and submitting a try run.
Comment on attachment 8786599 [details]
Bug 1294156 - NaNs with sign-bit aren't sorted correctly

http://cdn.memegenerator.net/instances/400x/24707717.jpg
Attachment #8786599 - Flags: review?(winter2718) → review+
(In reply to Morgan Phillips [:mrrrgn] from comment #7)
> Thanks for doing all of this André and Sumit. Looking at the patch now and
> submitting a try run.

You have only Andre to thank; I merely implemented and verified his solution - he is the real brains. :)

Anyway, do we also need a test for this case? If I add one after this try run is finished, we would have to run it again right?
Attached patch bug1294156.patchSplinter Review
Updated Sumit Tiwari's to apply cleanly on inbound (on top of bug 1290579).

Revisiting the patch I came to the conclusion it's probably more consistent to keep the NaN payload for negative NaNs, because we also (implicitly) keep the NaN payload for positive NaNs.

Requesting an additional review because of the NaN payload change and because the original patch didn't include tests.
Assignee: nobody → andrebargull
Attachment #8786599 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #8930457 - Flags: review?(evilpies)
Comment on attachment 8930457 [details] [diff] [review]
bug1294156.patch

Review of attachment 8930457 [details] [diff] [review]:
-----------------------------------------------------------------

Oh this code is quite clever. Thanks for the tests.
Attachment #8930457 - Flags: review?(evilpies) → review+
@Andre:
I don't quite remember why I never ended up writing a test for this; thanks a ton!
(In reply to Sumit Tiwari from comment #14)
> @Andre:
> I don't quite remember why I never ended up writing a test for this; thanks
> a ton!

No problem. :-D
And thanks for providing the patches for this one and in bug 1290579! :-)
Pushed by archaeopteryx@coole-files.de:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6cec51b18bc5
NaNs with sign-bit aren't sorted correctly. r=mrrrgn,evilpie
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/6cec51b18bc5
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
You need to log in before you can comment on or make changes to this bug.