Last Comment Bug 181828 - heapsort implementation can be faster
: heapsort implementation can be faster
Status: VERIFIED FIXED
: perf
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Linux
: -- normal (vote)
: ---
Assigned To: Igor Bukanov
: Phil Schwartau
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2002-11-25 00:26 PST by Igor Bukanov
Modified: 2003-02-26 18:30 PST (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
jsarray.c, heapsort: no need to call compare with tail during sort phase (1.12 KB, patch)
2002-11-25 00:29 PST, Igor Bukanov
brendan: superreview+
Details | Diff | Splinter Review
try a JSBool (phase number was less clear after all) (1.13 KB, patch)
2002-11-25 10:46 PST, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
Compare patch with more comments and int->size_t replace (1.60 KB, patch)
2002-12-02 12:42 PST, Igor Bukanov
no flags Details | Diff | Splinter Review
Previous patch with tabs expanded (1.62 KB, patch)
2002-12-02 12:57 PST, Igor Bukanov
no flags Details | Diff | Splinter Review
// are replaced by proper /* */ (1.63 KB, patch)
2003-02-06 13:53 PST, Igor Bukanov
rogerl: review+
brendan: superreview+
Details | Diff | Splinter Review
Patch update to address the above comments and replace memmove by memcpy (3.27 KB, patch)
2003-02-23 15:24 PST, Igor Bukanov
brendan: review+
Details | Diff | Splinter Review
Patch I'll check in later today... (3.96 KB, patch)
2003-02-26 11:51 PST, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review

Description Igor Bukanov 2002-11-25 00:26:10 PST
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:
Comment 1 Igor Bukanov 2002-11-25 00:29:29 PST
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%.
Comment 2 Igor Bukanov 2002-11-25 00:31:21 PST
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;}
Comment 3 Brendan Eich [:brendan] 2002-11-25 09:26:13 PST
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
Comment 4 timeless 2002-11-25 09:45:21 PST
I'm almost certain that brendan meant JS_TRUE/JS_FALSE instead of PR_...
Comment 5 Brendan Eich [:brendan] 2002-11-25 10:00:55 PST
NSPR controls my fingers, sometimes.  Of course timeless is right....

/be
Comment 6 Brendan Eich [:brendan] 2002-11-25 10:34:56 PST
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
Comment 7 Brendan Eich [:brendan] 2002-11-25 10:46:12 PST
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
Comment 8 Igor Bukanov 2002-11-25 11:33:50 PST
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?
Comment 9 Brendan Eich [:brendan] 2002-11-25 17:27:36 PST
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 Brendan Eich [:brendan] 2002-11-25 17:41:06 PST
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
Comment 11 Igor Bukanov 2002-12-02 12:42:09 PST
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.
Comment 12 Igor Bukanov 2002-12-02 12:57:11 PST
Created attachment 107931 [details] [diff] [review]
Previous patch with tabs expanded
Comment 13 rogerl (gone) 2003-02-06 13:28:45 PST
The // comments have to be /* */ since we live in the K&R world.
Comment 14 Igor Bukanov 2003-02-06 13:53:55 PST
Created attachment 113727 [details] [diff] [review]
// are replaced by proper /* */
Comment 15 Markus Hübner 2003-02-16 05:58:52 PST
Isn't this ready for checkin now?
Comment 16 timeless 2003-02-16 06:06:45 PST
it'd need approval from drivers. follow the standard rules.
Comment 17 Brendan Eich [:brendan] 2003-02-23 14:30:21 PST
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;
Comment 18 Igor Bukanov 2003-02-23 15:24:35 PST
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.
Comment 19 Brendan Eich [:brendan] 2003-02-24 14:08:02 PST
Comment on attachment 115337 [details] [diff] [review]
Patch  update to address the above comments and replace memmove by memcpy

Beauty -- thanks again.

/be
Comment 20 Igor Bukanov 2003-02-26 05:55:10 PST
Given the above, can the patch be committed?
Comment 21 Brendan Eich [:brendan] 2003-02-26 11:51:22 PST
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 Phil Schwartau 2003-02-26 16:44:06 PST
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 Brendan Eich [:brendan] 2003-02-26 17:46:43 PST
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
Comment 24 Phil Schwartau 2003-02-26 18:30:17 PST
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

Note You need to log in before you can comment on or make changes to this bug.