720695 - Lexicographic sort on integers broken on array of integers that includes -0x80000000

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Test case:

[-0x80000000, -3].sort()

Expected: [-2147483648,-3]
Got: [-3,-2147483648]

Comment 1

[Santiago Gimeno]

(In reply to Ms2ger from comment #0)
> Test case:
> 
> [-0x80000000, -3].sort()
> 
> Expected: [-2147483648,-3]
> Got: [-3,-2147483648]

The problem happens when one of the integers being has 10 digits, and the other when multiplied for a power of 10 to perform the comparison overflows. For example to compare these 2 numbers, we were multiplying 3*10e9 > INT32_MAX.

For example it also fails with:

[2147483647, 3]

I'll try to look into it

Comment 2

[Santiago Gimeno]

Attachment: Fixes sorting when integer digits equals 10

Comment 3

[Luke Wagner [:luke]]

Santiago: could you create a patch that applies to mozilla-inbound tip?

Comment 4

[Luke Wagner [:luke]]

Attachment: fix and test

I ended up thinking about this a bit.  The cause of comment 0 is actually that special-casing INT32_MIN is wrong for lexicographic ordering since, even if a = INT32_MIN, if b = -1, a < b.  What is great is that if we just lift the comparison to uint32_t, no special-casing is necessary at all (b/c of the commented algebraic identity)!  But also comment 1 is right in that there is a *separate* bug that the multiplication can overflow.  I think the simplest fix is to just carry out the multiplication and comparison in the uint64_t domain.

I was also remiss as a reviewer in not asking for a good test of CompareLexicographicInt32, so I attached one here (that would have found both the above bugs).

I was doubly remiss by not comparing our implementation with v8s: http://code.google.com/p/v8/source/browse/trunk/src/runtime.cc#7191.  They found the same INT32_MIN trick but it would seem they chose to go with a more-complicated/slower strategy involving integer division to deal with overflow.  Perhaps there is a case I'm missing that makes their strategy necessary?

Adding Waldo as a second reviewer just to be safe.

Comment 5

[Santiago Gimeno]

Comment on attachment 591215 [details] [diff] [review]
fix and test

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

Hi, I like your implementation better than mine :D.
I have one question though (sorry if it does not make any sense): Is there any penalty on having to cast to uint64_t for every comparison compared to having two different paths one for "could-overflow" comparisons(uint64_t) and other for "normal" comparisons(uint32_t)?

Comment 6

[Santiago Gimeno]

(In reply to Luke Wagner [:luke] from comment #3)
> Santiago: could you create a patch that applies to mozilla-inbound tip?

Sorry about it. I'm newbie on this. What exactly is mozilla-inbound? Is there any documentation I can refer to?

Comment 7

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

https://wiki.mozilla.org/Tree_Rules/Inbound

Comment 8

[Luke Wagner [:luke]]

(In reply to Santiago Gimeno from comment #5)
> I have one question though (sorry if it does not make any sense): Is there
> any penalty on having to cast to uint64_t for every comparison compared to
> having two different paths one for "could-overflow" comparisons(uint64_t)
> and other for "normal" comparisons(uint32_t)?

Good question.  I compared before/after this patch for a int-sorting microbench and found practically no difference.  Thus, I think we are free to do the simpler thing.

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 591215 [details] [diff] [review]
fix and test

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

r=me with the requested changes.

::: js/src/jit-test/tests/basic/testBug720695.js
@@ +1,2 @@
> +var v = [ -0x80000003, -0x80000002, -0x80000001, -0x80000000, -0x7fffffff, -0x7ffffffe, -0x7ffffffd,
> +          -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Add a few other numbers that aren't single-digit magnitudes for sanity, something like this to catch last-digit differences, extra-digit differences, and so on:

10, 11, 20, 21, 100, 101, 110, 111, 500

Add both negatives and positives for those while you're at it.

::: js/src/jsarray.cpp
@@ +2046,5 @@
> +            buint = bint;
> +        } else {
> +            /* uint32_t(-INT32_MIN) = uint32_t(INT32_MIN) = uint32_t(-int64_t(INT32_MIN)) */
> +            auint = (uint32_t) -aint;
> +            buint = (uint32_t) -bint;

-INT32_MIN has undefined behavior, 2**31 being greater than INT32_MAX.  Whee, fun.  Do this instead (with a comment if you can think of one that gives a good, pithy explanation of why - isn't used):

auint = ~uint32_t(aint) + 1;
buint = ~uint32_t(bint) + 1;

@@ +2056,5 @@
>           * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
>           * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
>           */
> +        int digitsa = NumDigitsBase10(auint);
> +        int digitsb = NumDigitsBase10(buint);

Shurely unsigned if you're changing the type the method returns...

Comment 10

[Luke Wagner [:luke]]

(In reply to Jeff Walden (remove +bmo to email) from comment #9)
> Shurely unsigned if you're changing the type the method returns...

You're right, and don't call me Shurley.

Comment 11

[Luke Wagner [:luke]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/40b1a7a5e630

Comment 12

[Joe Drew (not getting mail)]

https://hg.mozilla.org/mozilla-central/rev/40b1a7a5e630