64065 - Array.prototype.sort inefficiencies

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brendan Eich [:brendan]]

It copies memory unnecessarily and expensively, it doesn't avoid trivial
recursion, and js_qsort_r control flow is suboptimal.  Patch coming up.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: proposed fix

Comment 2

[Brendan Eich [:brendan]]

Attachment: diff -wu version

Comment 3

[Mike McCabe]

r=mccabe.

two bits I don't quite get:

647 gets skipped if we follow goto break2; this is OK because b and a are
identical in this case?

650 - new if (i > lo) conditional.  Similar case?

Comment 4

[Brendan Eich [:brendan]]

mccabe: right on first question, if i equals j we just need to finish the pivot
swap.

Same for second question (no point in copying the pivot over itself if it
happened to have the least key according to cmp), but that points out that the
goto could avoid an unecessary test by jumping inside the then statement
governed by if (i > lo):

+        if (i > lo) {
+      break2:
+            MEMMOVE(a, pivot, elsize);
+        }

We know we've done ++i at least once before the goto break2, so i must be > lo.

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: Fixed fix -- avoid i > lo test from goto, keep a == vec + i * elsize

Comment 6

[Brendan Eich [:brendan]]

Attachment: diff -wu version

Comment 7

[Brendan Eich [:brendan]]

Sorry, I hacked after testing the first patch in this bug, and screwed up the
induction variable a (which must be induced by i via a = (char*)vec+i*elsize).
All good now -- test it for yourselves.

/be

Comment 8

[John Bandhauer]

I'll buy this. It passes the tests, right? sr=jband

Comment 9

[Phil Schwartau]

I have just applied the patch on Linux and WinNT and ran the test suite
against debug and optimized builds of JS shell. No regressions were introduced -

Comment 10

[Brendan Eich [:brendan]]

Fix checked in -- thanks all.

/be

Comment 11

[Phil Schwartau]

Marking Verified - 

Comment 12

[Jesse Ruderman]

The patch from this bug apparently changed the behavior of sort when the 
comparison function returns 0.  I filed bug 78144 in Evangelism assuming that 
sort behavior is undefined when the comparison function returns 0.  If this bug 
did introduce a legitimate regression, please file another bug and cross-
reference it with bug 78144.

Comment 13

[Brendan Eich [:brendan]]

How exactly did the behavior change for the 0 return case?  From bug 78144, I
see a bogus comparison function that returns false for a >= b, which converts to
0, which is not the correct return code for a > b (that would be -1 for a
descending order or reversed sort).

Without more info, I would say the regression was entirely on ZDNet's side.

/be