Closed
Bug 181828
Opened 22 years ago
Closed 21 years ago
heapsort implementation can be faster
Categories
(Core :: JavaScript Engine, defect)
Tracking
()
VERIFIED
FIXED
People
(Reporter: user, Assigned: user)
Details
(Keywords: perf)
Attachments
(2 files, 5 obsolete files)
3.27 KB,
patch
|
brendan
:
review+
|
Details | Diff | Splinter Review |
3.96 KB,
patch
|
Details | Diff | Splinter Review |
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.1) Gecko/20021003 Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.1) Gecko/20021003 Place for yet another attempt to optimize heapsort Reproducible: Always Steps to Reproduce:
Assignee | ||
Comment 1•22 years ago
|
||
This is a copy ot attachment 107338 [details] [diff] [review] for bug 143354 The patch removes one compare per call of HeapSortHelper during sort phase as there the last array element (pivot value) is a member of heap and can not bigger then the biggest of the first 2 elements. With the patch applied the run time for the above test decreases by 4%.
Assignee | ||
Comment 2•22 years ago
|
||
With above running time for the next script goes down 3270ms to 3145ms on average (about 4%): var N = 10000; testSortArray(); function testSortArray() { var array = new Array; for(i=0; i<=N; i++) array[i] = Math.random()*N; start = new Date(); array.sort(compare); end = new Date(); print('Result in ms: ' + (end-start) + '\n'); for(i=0; i<N; i++) { if (compare(array[i], array[i + 1]) > 0) { print("BAD: broken sort"); } } } function compare(x,y){return x-y;}
Updated•22 years ago
|
Attachment #107345 -
Flags: superreview?(brendan)
Attachment #107345 -
Flags: review?(khanson)
Updated•22 years ago
|
Status: UNCONFIRMED → NEW
Ever confirmed: true
Comment 3•22 years ago
|
||
Comment on attachment 107345 [details] [diff] [review] jsarray.c, heapsort: no need to call compare with tail during sort phase >Index: jsarray.c >=================================================================== >RCS file: /cvsroot/mozilla/js/src/jsarray.c,v >retrieving revision 3.41 >diff -u -r3.41 jsarray.c >--- jsarray.c 7 Nov 2002 10:51:23 -0000 3.41 >+++ jsarray.c 25 Nov 2002 07:46:39 -0000 >@@ -637,7 +637,7 @@ > sort_compare_strings(const void *a, const void *b, void *arg); > > static void >-HeapSortHelper(HSortArgs *qa, int lo, int hi) >+HeapSortHelper(int build_phase, HSortArgs *qa, int lo, int hi) Please use JSBool for the type, and pass PR_TRUE and PR_FALSE appropriately. Also, is there a clearer name than "build_phase"? I can't think of one right now. FYI, JS requires r= only, it's a restricted CVS partition. So for the next patch, just request review from me. Thanks, /be
Attachment #107345 -
Flags: superreview?(brendan) → superreview-
I'm almost certain that brendan meant JS_TRUE/JS_FALSE instead of PR_...
Assignee: rogerl → igor
Severity: normal → enhancement
Comment 5•22 years ago
|
||
NSPR controls my fingers, sometimes. Of course timeless is right.... /be
Comment 6•22 years ago
|
||
Comment on attachment 107345 [details] [diff] [review] jsarray.c, heapsort: no need to call compare with tail during sort phase Maybe sort_phase is better than build_phase, but then I'd want an enum whose enumerators named phases. But how is that better than phase numbers, as the original patch used? I'm sorry to pick nits that lead nowhere. This is a fine patch, but I would change build_phase (what build?) to sort_phase. /be
Attachment #107345 -
Flags: superreview- → superreview+
Comment 7•22 years ago
|
||
Comments? I'll check this in after thinking about it some more. /be
Assignee | ||
Comment 8•22 years ago
|
||
In the initial patch I needed that build_phase (now building) only to distinguish in HeapSortHelper the first sort that happens after the heap is almost ready and the only element which is not under heap is the last element of vec array. So in principle building is somewhat misleading indeed as it reflects not the real need for it but a different situation that turned out to coincide with the real usage... Potentially it is possible to reduce number of calls to compare during the sort phase farther by checking before comparing with the sub-heap biggest element if the pivot comes from that sub-heap, but asymptotically on average it brings only one more saving of compare call per HeapSortHelper and bookkeeping probably will eat that in any case. And unrelated questions: why i,j etc. indexes in the heapsort implementation are int and not size_t? And why it is necessary to have HSortArgs at all? Why not to pass all the necessary arguments for HeapSortHelper directly?
Severity: enhancement → normal
Comment 9•22 years ago
|
||
The HSortArgs struct derived from QSortArgs, back when QuickSort was used (see the cvs history via the links in the upper right-hand corner of http://lxr.mozilla.org/mozilla/source/js/src/jsarray.c). Note that all the members of the struct are invariants. It doesn't pay to pass them as separate parameters on many architectures (it'll spill from arg registers into memory, so you might as well use a struct). This was especially true with the naive, recursive QuickSort implementation used originally. (It is also a little less unsightly, in my opinion, but that's not a sound reason, it's just an aesthetic judgment.) /be
Comment 10•22 years ago
|
||
The mixing of int and size_t (and jsuint, elsewhere) seems like a minor problem worth fixing. Beware loops that want to decrement till < 0, if any. Igor, were you thinking of patching further? /be
Assignee | ||
Comment 11•22 years ago
|
||
The patch update adds comments and change type for index variables from int to size_t. As size_t is an unsigned type, loop condition in js_HeapSort is changed from i > 0 into i != 0 as well.
Attachment #107345 -
Attachment is obsolete: true
Assignee | ||
Comment 12•22 years ago
|
||
Attachment #107927 -
Attachment is obsolete: true
Updated•22 years ago
|
Attachment #107345 -
Flags: review?(khanson)
Updated•22 years ago
|
Keywords: mozilla1.3
Attachment #107931 -
Flags: review?(rogerl)
Comment 13•21 years ago
|
||
The // comments have to be /* */ since we live in the K&R world.
Assignee | ||
Comment 14•21 years ago
|
||
Attachment #107931 -
Attachment is obsolete: true
Attachment #107931 -
Flags: review?(rogerl)
Attachment #107931 -
Flags: review?(rogerl)
Updated•21 years ago
|
Attachment #113727 -
Flags: review+
Comment 15•21 years ago
|
||
Isn't this ready for checkin now?
Comment 16•21 years ago
|
||
it'd need approval from drivers. follow the standard rules.
Updated•21 years ago
|
Attachment #113727 -
Flags: superreview?(brendan)
Comment 17•21 years ago
|
||
Comment on attachment 113727 [details] [diff] [review] // are replaced by proper /* */ >@@ -663,7 +663,11 @@ > j++; > a = (char *)vec + (hi - 1) * elsize; > b = (char *)vec2 + j * elsize; >- if (cmp(a, b, arg) >= 0) >+ /* During sorting phase b points to a member of heap which can not be Nit: use the prevailing major comment style: /* * Blah blah blah ... * (blah). */ Fix that and r=me, too (no sr= needed in js/src, but I checked the + box anyway). >+ * bigger then biggest of vec[0] and vec[1] and cmp(a, b, arg) <= 0 >+ * always holds >+ */ >+ if ((building || hi == 2) && cmp(a, b, arg) >= 0) > return; > > MEMMOVE(pivot, a, elsize); >@@ -700,7 +704,7 @@ > { > void *pivot; > HSortArgs qa; Bonus points if you rename qa to ha or hsa (HeapSort Args). /be >- int i; >+ size_t i; > > pivot = malloc(elsize); > if (!pivot) >@@ -711,10 +715,10 @@ > qa.cmp = cmp; > qa.arg = arg; > >- for (i = nel/2; i > 0; i--) >- HeapSortHelper(&qa, i, (int) nel); >+ for (i = nel/2; i != 0; i--) >+ HeapSortHelper(JS_TRUE, &qa, i, nel); > while (nel > 2) >- HeapSortHelper(&qa, 1, (int) --nel); >+ HeapSortHelper(JS_FALSE, &qa, 1, --nel); > > free(pivot); > return JS_TRUE;
Attachment #113727 -
Flags: superreview?(brendan) → superreview+
Assignee | ||
Comment 18•21 years ago
|
||
The update includes cosmetics like fixing comments style and renaming qa->hsa and more nontrivial memmove->memcpy replace since arguments for copy operation never overlap and memcpy is faster. This triggered rename of MEMMOVE macro to MEMCPY rename. I also moved initialization of the fastmove flag to js_HeapSort to do it it only once, not each time per HeapSortHelper invocation.
Attachment #113727 -
Attachment is obsolete: true
Assignee | ||
Updated•21 years ago
|
Attachment #115337 -
Flags: review?(brendan)
Comment 19•21 years ago
|
||
Comment on attachment 115337 [details] [diff] [review] Patch update to address the above comments and replace memmove by memcpy Beauty -- thanks again. /be
Attachment #115337 -
Flags: review?(brendan) → review+
Assignee | ||
Comment 20•21 years ago
|
||
Given the above, can the patch be committed?
Attachment #107931 -
Flags: review?(rogerl)
Attachment #107371 -
Attachment is obsolete: true
Comment 21•21 years ago
|
||
...when the tree is open. Slight cleanup (no need for (char*) cast, make major comment be a proper sentence), sorry for any conflicts. /be
Comment 22•21 years ago
|
||
Just ran the latest patch (Comment #21) against the JS testsuite on Linux and WinNT, in both the debug and optimized JS shells. Everything looked fine - no test regressions were observed.
Comment 23•21 years ago
|
||
I just checked in attachment 115667 [details] [diff] [review], like so: [~/src/trunk-opt/mozilla/js/src]$ cvs ci -m"Checking in heap-sort speedup from Igor Bukanov <igor@icesoft.no> (bug 181828, r=me)." jsarray.c Checking in jsarray.c; /cvsroot/mozilla/js/src/jsarray.c,v <-- jsarray.c new revision: 3.42; previous revision: 3.41 done So I'm closing this bug. Thanks again, Igor. /be
Status: NEW → RESOLVED
Closed: 21 years ago
Resolution: --- → FIXED
Comment 24•21 years ago
|
||
Marking Verified FIXED. There are no test regressions observed (Comment #22), and we have performance improvements on the testcase in Comment #2: BEFORE THIS FIX AFTER THIS FIX WinNT Result in ms: 500 Result in ms: 469 Linux Result in ms: 507 Result in ms: 488
Status: RESOLVED → VERIFIED
You need to log in
before you can comment on or make changes to this bug.
Description
•