Closed Bug 64065 Opened 24 years ago Closed 24 years ago

Array.prototype.sort inefficiencies

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

VERIFIED FIXED
mozilla0.8

People

(Reporter: brendan, Assigned: brendan)

Details

(Keywords: js1.5, perf)

Attachments

(4 files)

It copies memory unnecessarily and expensively, it doesn't avoid trivial recursion, and js_qsort_r control flow is suboptimal. Patch coming up. /be
Status: NEW → ASSIGNED
Keywords: js1.5, mozilla0.8
Target Milestone: --- → mozilla0.8
Attached patch proposed fix (deleted) — Splinter Review
Attached patch diff -wu version (deleted) — Splinter Review
Keywords: patch, review
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?
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
Attached patch diff -wu version (deleted) — Splinter Review
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
I'll buy this. It passes the tests, right? sr=jband
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 -
Fix checked in -- thanks all. /be
Status: ASSIGNED → RESOLVED
Closed: 24 years ago
Resolution: --- → FIXED
Marking Verified -
Status: RESOLVED → VERIFIED
Keywords: mozilla0.8
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.
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
Keywords: perf
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: