Last Comment Bug 720695 - Lexicographic sort on integers broken on array of integers that includes -0x80000000
: Lexicographic sort on integers broken on array of integers that includes -0x8...
Status: RESOLVED FIXED
: regression, testcase
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla12
Assigned To: Luke Wagner [:luke]
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: 715265
  Show dependency treegraph
 
Reported: 2012-01-24 06:56 PST by :Ms2ger (⌚ UTC+1/+2)
Modified: 2012-01-28 19:02 PST (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Fixes sorting when integer digits equals 10 (13.84 KB, patch)
2012-01-24 09:45 PST, Santiago Gimeno
no flags Details | Diff | Splinter Review
fix and test (4.10 KB, patch)
2012-01-24 12:20 PST, Luke Wagner [:luke]
santiago.gimeno: review+
jwalden+bmo: review+
Details | Diff | Splinter Review

Description :Ms2ger (⌚ UTC+1/+2) 2012-01-24 06:56:36 PST
Test case:

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

Expected: [-2147483648,-3]
Got: [-3,-2147483648]
Comment 1 Santiago Gimeno 2012-01-24 07:31:46 PST
(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 2012-01-24 09:45:47 PST
Created attachment 591141 [details] [diff] [review]
Fixes sorting when integer digits equals 10
Comment 3 Luke Wagner [:luke] 2012-01-24 09:47:21 PST
Santiago: could you create a patch that applies to mozilla-inbound tip?
Comment 4 Luke Wagner [:luke] 2012-01-24 12:20:03 PST
Created attachment 591215 [details] [diff] [review]
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 2012-01-25 08:32:51 PST
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 2012-01-25 08:34:21 PST
(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 (⌚ UTC+1/+2) 2012-01-25 08:35:33 PST
https://wiki.mozilla.org/Tree_Rules/Inbound
Comment 8 Luke Wagner [:luke] 2012-01-25 08:41:34 PST
(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] (remove +bmo to email) 2012-01-27 15:10:11 PST
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] 2012-01-27 15:30:47 PST
(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 12 Joe Drew (not getting mail) 2012-01-28 19:02:24 PST
https://hg.mozilla.org/mozilla-central/rev/40b1a7a5e630

Note You need to log in before you can comment on or make changes to this bug.