Closed Bug 181828 Opened 22 years ago Closed 21 years ago

heapsort implementation can be faster

Categories

(Core :: JavaScript Engine, defect)

x86
Linux
defect
Not set
normal

Tracking

()

VERIFIED FIXED

People

(Reporter: user, Assigned: user)

Details

(Keywords: perf)

Attachments

(2 files, 5 obsolete files)

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:
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%.
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-
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+
Comments?  I'll check this in after thinking about it some more.

/be
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
Keywords: perf
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
Attachment #107927 - Attachment is obsolete: true
Attachment #107345 - Flags: review?(khanson)
Keywords: mozilla1.3
Attachment #107931 - Flags: review?(rogerl)
The // comments have to be /* */ since we live in the K&R world.
Attached patch // are replaced by proper /* */ (obsolete) — Splinter Review
Attachment #107931 - Attachment is obsolete: true
Attachment #107931 - Flags: review?(rogerl)
Attachment #107931 - Flags: review?(rogerl)
Attachment #113727 - Flags: review+
Isn't this ready for checkin now?
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+
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
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+
Given the above, can the patch be committed?
Attachment #107931 - Flags: review?(rogerl)
Attachment #107371 - Attachment is obsolete: true
...when the tree is open.  Slight cleanup (no need for (char*) cast, make major
comment be a proper sentence), sorry for any conflicts.

/be
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
Closed: 21 years ago
Resolution: --- → FIXED
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.

Attachment

General

Creator:
Created:
Updated:
Size: