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

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

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

Comment 1

[Jinank Jain[:jj]]

I would like to work on this bug could someone help me with where to start off?

Comment 2

[André Bargull [:anba]]

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;
}
```

Comment 3

[Sumit Tiwari]

Attachment: Bug 1294156 - NaNs with sign-bit aren't sorted correctly

Review commit: https://reviewboard.mozilla.org/r/75530/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/75530/

Comment 4

[Sumit Tiwari]

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. :(

Comment 5

[André Bargull [:anba]]

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.

Comment 6

[André Bargull [:anba]]

@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.

Comment 7

[Morgan Phillips [:mrrrgn]]

Thanks for doing all of this André and Sumit. Looking at the patch now and submitting a try run.

Comment 8

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8786599 [details]
Bug 1294156 - NaNs with sign-bit aren't sorted correctly

https://reviewboard.mozilla.org/r/75528/#review73750

http://cdn.memegenerator.net/instances/400x/24707717.jpg

Comment 9

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8786599 [details]
Bug 1294156 - NaNs with sign-bit aren't sorted correctly

http://cdn.memegenerator.net/instances/400x/24707717.jpg

Comment 10

[Morgan Phillips [:mrrrgn]]

try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=0411414603e3

Comment 11

[Sumit Tiwari]

(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?

Comment 12

[André Bargull [:anba]]

Attachment: bug1294156.patch

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.

Comment 13

[Tom S [:evilpie]]

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.

Comment 14

[Sumit Tiwari]

@Andre:
I don't quite remember why I never ended up writing a test for this; thanks a ton!

Comment 15

[André Bargull [:anba]]

(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! :-)

Comment 16

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=badd1585f635dff770b73fc8d8bf811d5c6bba4b

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6cec51b18bc5
NaNs with sign-bit aren't sorted correctly. r=mrrrgn,evilpie

Comment 18

[Cristian Brindusan [:cbrindusan]]

https://hg.mozilla.org/mozilla-central/rev/6cec51b18bc5