The default bug view has changed. See this FAQ.

heapsort implementation can be faster

VERIFIED FIXED

Status

()

Core
JavaScript Engine
VERIFIED FIXED
15 years ago
14 years ago

People

(Reporter: Igor Bukanov, Assigned: Igor Bukanov)

Tracking

({perf})

Trunk
x86
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 5 obsolete attachments)

(Assignee)

Description

15 years ago
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

15 years ago
Created attachment 107345 [details] [diff] [review]
jsarray.c, heapsort: no need to call compare with tail during sort phase

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

15 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;}
Attachment #107345 - Flags: superreview?(brendan)
Attachment #107345 - Flags: review?(khanson)
Status: UNCONFIRMED → NEW
Ever confirmed: true
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-

Comment 4

15 years ago
I'm almost certain that brendan meant JS_TRUE/JS_FALSE instead of PR_...
Assignee: rogerl → igor
Severity: normal → enhancement
NSPR controls my fingers, sometimes.  Of course timeless is right....

/be
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+
Created attachment 107371 [details] [diff] [review]
try a JSBool (phase number was less clear after all)

Comments?  I'll check this in after thinking about it some more.

/be
(Assignee)

Comment 8

15 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
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
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

Updated

15 years ago
Keywords: perf
(Assignee)

Comment 11

15 years ago
Created attachment 107927 [details] [diff] [review]
Compare patch with more comments and int->size_t replace

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

15 years ago
Created attachment 107931 [details] [diff] [review]
Previous patch with tabs expanded
Attachment #107927 - Attachment is obsolete: true

Updated

15 years ago
Attachment #107345 - Flags: review?(khanson)

Updated

15 years ago
Keywords: mozilla1.3

Updated

14 years ago
Attachment #107931 - Flags: review?(rogerl)

Comment 13

14 years ago
The // comments have to be /* */ since we live in the K&R world.
(Assignee)

Comment 14

14 years ago
Created attachment 113727 [details] [diff] [review]
// are replaced by proper /* */
Attachment #107931 - Attachment is obsolete: true

Updated

14 years ago
Attachment #107931 - Flags: review?(rogerl)

Updated

14 years ago
Attachment #107931 - Flags: review?(rogerl)

Updated

14 years ago
Attachment #113727 - Flags: review+

Comment 15

14 years ago
Isn't this ready for checkin now?

Comment 16

14 years ago
it'd need approval from drivers. follow the standard rules.
Attachment #113727 - Flags: superreview?(brendan)
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

14 years ago
Created attachment 115337 [details] [diff] [review]
Patch  update to address the above comments and replace memmove by memcpy

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

14 years ago
Attachment #115337 - Flags: review?(brendan)
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

14 years ago
Given the above, can the patch be committed?

Updated

14 years ago
Attachment #107931 - Flags: review?(rogerl)

Updated

14 years ago
Attachment #107371 - Attachment is obsolete: true
Created attachment 115667 [details] [diff] [review]
Patch I'll check in later today...

...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

14 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.
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
Last Resolved: 14 years ago
Resolution: --- → FIXED

Comment 24

14 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.