Closed Bug 143354 Opened 22 years ago Closed 22 years ago

IE6 is 10x faster than Mozilla on random Array.sort()

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
All
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
VERIFIED FIXED

People

(Reporter: pschwartau, Assigned: khanson)

References

(
URL
)

Details

(Keywords: perf, Whiteboard: [ADT2 RTM])

Attachments

(2 files, 2 obsolete files)

indentation and comment improvements on khanson's last patch
2.44 KB, patch
brendan
: review+
shaver
: superreview+
jud
: approval+
Details | Diff | Splinter Review
jsarray.c, heapsort: no need to call compare with tail during sort phase
1.12 KB, patch
Details | Diff | Splinter Review 
The following was noted in bug 99120:


------- Additional Comment_ #64 From Markus Hübner 2002-05-09 11:07 -------

The sort() test at http://www.formula-one.nu/mozilla/jsTimeTest.htm
shows a huge difference (70ms vs. 1292ms) between IE6 and the latest
trunk  build.


------- Additional Comment_ #66 From Phil Schwartau 2002-05-09 17:40 -------

Here is the test mentioned in Comment #64:

<SCRIPT>
testSortArray();

function testSortArray()
{
  var theArray = new Array;
  for(i=0; i<=10000; i++)
    theArray[i] = parseInt(Math.random()*10000)

  start = new Date();
  theArray.sort();
  end = new Date();
  
  alert('Result in ms: ' + (end-start) + '\n');
}
</SCRIPT>



------------------------------  MY RESULTS  ------------------------------
WinNT 4.0 (SP6); 500MHz CPU; 128M RAM
All times in ms:

                  IE6                     172
                  NN4.7                   1800   
                  Moz (current trunk)     1700
                  Opt JS shell (current)  780
                  Opt JS shell (RC4a)     780
                  Opt JS shell (RC4)      1350
                  Opt JS shell (RC3)      1400


The change in the JS shell occurs between RC4 (Jan 01, 2002)
and RC4a (Mar 21, 2002). The fix for this bug went in Mar 12-13.

However, we see that on my box, IE6 is 10x faster than Mozilla
on this test, and 4.5x faster than the current JS shell.

I also tried a Mozilla binary from Mar 22, and got the same 
timings as with the current binary: about 1700ms.
Keywords: perf
Blocks: 117611
Reassigning to Kenton -
Assignee: rogerl → khanson
No longer blocks: 117611
Blocks: 117611
No longer blocks: 117611
Blocks: 117611
Changing summary "Can we improve Array.prototype.sort() performance?"
              to "IE6 is 10x faster than Mozilla on random Array.sort()"
Summary: Can we improve Array.prototype.sort() performance? → IE6 is 10x faster than Mozilla on random Array.sort()
Why is Mozilla so much slower than the JS shell?  It could be JS_THREADSAFE:
Phil, can you measure the optimized xpcshell perf on the same machine and input?
 If that's not it, then it must be some DOM/caps security check overhead.

/be
Probably the cost is peculiar to JS_THREADSAFE (i.e., locking overhead) and is
under js_ValueToString, in jsdtoa.c.  See bug 120992.

/be
Waldemar made a key observation concerning the test: we have been
calling Array.prototype.sort() without providing a compare function.
The ECMA-262 spec requires such a sort to be done lexicographically,
not numerically. Here is a Netscape reference for the JavaScript user:

http://developer.netscape.com:80/docs/manuals/js/core/jsref/array.htm#1196882

"If a compare function is not supplied, elements are sorted by converting
 them to strings and comparing strings in lexicographic not numerical order.
 For example, '80' comes before '9' in lexicographic order, but in a numeric
 sort 9 comes before 80."


So I re-ran the above test, replacing the line

              theArray.sort();
with          theArray.sort(function(x,y){return x-y;});



------------------------------  MY RESULTS  ------------------------------
WinNT 4.0 (SP6); 500MHz CPU; 128M RAM
All times in ms:

                  IE6                     3000
                  NN4.7                   15000 (yes, 15 thousand!)   
                  Moz (current trunk)     531
                  Opt JS shell (current)  407
                  Opt JS shell (RC4a)     407
                  Opt JS shell (RC4)      540
                  Opt JS shell (RC3)      600


On this test, a Mozilla trunk binary from March 22 was slightly faster
(484) than my current trunk binary. At any rate, this data presents a 
dramatically different picture vis-a-vis our sorting speed vs. IE6: 
Mozilla is nearly 6x faster!
Out of curiosity, I checked whether the IE6 implementation of JavaScript
obeys the ECMA spec on sort() with no compare function. Looks like it does:

                                          NN4.7      Moz        IE6
javascript: alert([80,9].sort())  --->   [80, 9]    [80, 9]    [80, 9]
Oh ho!  This is indeed good news.  And it means that when the performance patch
in bug 120992 goes in, the original test should be re-run.  (Bug 120992 is
performance in decimal to string conversion.)

--scole
Phil, another test to run would be to make sure the array contained strings
before the sort started:  in the initialization loop do

 theArray[i] = "" + parseInt(...)

and then put back the sort call like before.  (This would test a lexographic
sort without the number conversion thrown in.)

(I just realized that Brendan basically said this in comment 4, but it took
Waldemar's comment to make it sink in...)

--scole
Yes, you could rerun the tests when I check it in, but don't expect any big
improvements. The majority of the time is spent at other places than the one
removed. 

One things to look at when looking for ways to improve sorting is general string
handling. Do we convert too often? Can we do the conversion once for all numbers
and then sort the strings and throw the strings afterwards. Maybe we already do
that. 

Can we avoid allocating small chunks from the heap? If we know the size of the
generated strings before the conversion, we could allocate memory for all
strings in one big chunk, and place all strings in that chunk to be sorted.

Can we convert from number to string in a faster way? The current algorithm is
very complex to handle all kinds of numbers. Maybe we could use a simpler,
faster algorithm for some numbers and use the complex, correct algorithm for the
numbers not handled by the fast algoritm.

I'm pretty sure we can make ths test case much faster, but I wonder if sorting
is the most important thing to improve. I would gladly see any contributions but
for general JS performance I think there are bigger fish to catch. Incremental
GC? Ref counting for strings? Those things are quite complex, I think, so maybe
starting at sorting, or converting numbers can be a nice start point for someone
wanting to contribute to the js engine.


Thos
I tried Steve's suggestion in Comment #8: coercing each element
of the array to a string: |theArray[i] = "" + parseInt(...)|; 
and testing |theArray.sort()| with no compare function provided.



------------------------------  MY RESULTS  ------------------------------
WinNT 4.0 (SP6); 500MHz CPU; 128M RAM
All times in ms:

                  IE6                     125
                  NN4.7                   297
                  Moz (current trunk)     125
                  Opt JS shell (current)  125
                  Opt JS shell (RC4a)     125
                  Opt JS shell (RC4)      281
                  Opt JS shell (RC3)      313


So on this one we see equal performance of Mozilla and IE6.
What I find interesting, too, is that there seems to be no
difference between Mozilla and the JS shell on this one -
Attached patch sort improvement (obsolete) — — Splinter Review 
A patch to speed up default sorts of strings being sorted as strings.  Should
show improvement in Phil’s last test case.  My tests exhibited a 40% reduction
in sort times.

To recap, in the original comment IE6 is probably storing the array as strings
and sorting by strings (default) while Mozilla	is storing the values as
doubles and doing a number to string conversion at each compare step.

In comment #5 the sort is being done by value so IE6 takes the conversion hit.

In commet #10 all values are stored and sorted by string value.

In most of the tests I’ve seen posted no checks are performed to verify that
the sort is correct.  Inclusion of these tests would eliminate much of the
confusion about what is being sorted, strings or numbers.
Comment on attachment 84925 [details] [diff] [review]
sort improvement

>+static int
>+sort_compare_str(const void *a, const void *b, void *arg);

Nit: perhaps sort_compare_strings or sort_compare_strvals is a better name?

But see below for a question about the type of the jsvals addressed by a and b.

>@@ -698,5 +701,5 @@
>     void *pivot;
>     HSortArgs qa;
>-    int i;
>+    int i = 0;
> 
>     pivot = malloc(elsize);
>@@ -708,5 +711,5 @@
>     qa.cmp = cmp;
>     qa.arg = arg;
>-
>+    
>     for (i = nel/2; i > 0; i--)
>         HeapSortHelper(&qa, i, (int) nel);

Please undo both of these gratuitous changes (no need to initialize int i, no
need for trailing whitespace on an empty line).

>@@ -775,4 +778,12 @@
> }
> 
>+static int
>+sort_compare_str(const void *a, const void *b, void *arg)
>+{
>+    jsval av = *(const jsval *)a, bv = *(const jsval *)b;
>+
>+	return (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));

Eek, an inconsistent tab -- note that legacy tabs in this file are
8-space-equivalent -- use four spaces here please.

Bug: this code assumes all values are strings -- that JSVAL_IS_STRING(av) &&
JSVAL_IS_STRING(bv).  That's not necessarily so.  You need to call
js_ValueToString.  You might short-circuit to JSVAL_TO_STRING if
JSVAL_IS_STRING, to avoid the calling overhead.

>+}
>+
> /* XXXmccabe do the sort helper functions need to take int?  (Or can we claim
>  * that 2^32 * 32 is too large to worry about?)  Something dumps when I change
>@@ -787,4 +798,5 @@
>     jsval *vec;
>     jsid id;
>+    JSBool all_str; /* true if no compare function and all string arguments */

Nit on nit: all_str matches sort_compare_str nicely, but if you prefer
sort_compare_strings, then all_strings is better.  JS eschews pidgin for
long_underscored_variable_names, in my experience.

> 
>     if (argc > 0) {
>@@ -798,4 +810,5 @@
> 	fval = JSVAL_NULL;
>     }
>+    all_str = !fval;

Don't wire in JSVAL_NULL's zero-ness here with !fval, do use JSVAL_IS_NULL. 
But now we see that all_str doesn't mean all values are strings, only that they
should be converted to strings when comparing.

> 
>     if (!js_GetLengthProperty(cx, obj, &len))
>@@ -835,4 +848,5 @@
> 	if (!ca.status)
> 	    goto out;
>+   	all_str = all_str && JSVAL_IS_STRING(*(const jsval *) &vec[i]); 
>     }
> 
>@@ -840,5 +854,6 @@
>     ca.fval = fval;
>     ca.status = JS_TRUE;
>-    if (!js_HeapSort(vec, (size_t) len, sizeof(jsval), sort_compare, &ca)) {
>+    if (!js_HeapSort(vec, (size_t) len, sizeof(jsval),
>+            all_str ? sort_compare_str : sort_compare, &ca)) {
> 	JS_ReportOutOfMemory(cx);
> 	ca.status = JS_FALSE;
Attachment #84925 - Flags: needs-work+
Comment on attachment 84925 [details] [diff] [review]
sort improvement

I neglected to finish reviewing.

>@@ -798,4 +810,5 @@
> 	fval = JSVAL_NULL;
>     }
>+    all_str = !fval;
> 
>     if (!js_GetLengthProperty(cx, obj, &len))
>@@ -835,4 +848,5 @@
> 	if (!ca.status)
> 	    goto out;
>+   	all_str = all_str && JSVAL_IS_STRING(*(const jsval *) &vec[i]); 
>     }
> 

My apologies, I should have read this line.  Never mind my babblings about the
need for js_ValueToString.

However, why the *(const jsval *)&vec[i] cast?	Why not just use vec[i]?

>@@ -840,5 +854,6 @@
>     ca.fval = fval;
>     ca.status = JS_TRUE;
>-    if (!js_HeapSort(vec, (size_t) len, sizeof(jsval), sort_compare, &ca)) {
>+    if (!js_HeapSort(vec, (size_t) len, sizeof(jsval),
>+            all_str ? sort_compare_str : sort_compare, &ca)) {

Nit: custom indents arguments overflowing the first line of a call to
"underhang" -- to start in the column the first arg starts in.

> 	JS_ReportOutOfMemory(cx);
> 	ca.status = JS_FALSE;

How about a new patch with some nit-picks, and I'll review for good?

/be
shaver points out that you could say

        all_str &= JSVAL_IS_STRING(*(const jsval *) &vec[i]);

and save a branch.  I think that's a fine trick inside the engine, where we
"know" that JSVAL_IS_NULL and JSVAL_IS_STRING (and friends) all yield 0 or 1.

/be

Nice. Very nice. This still converts the values to strings once for every
comparision? Couldn't you, in the all_str case convert once in the beginning and
sort the strings and then move the real content by the looking how the strings
moved? Much bigger code change, maybe as a next step after this?

daniel, khanson's patch does not convert strings in a new special case --
rather, the case it specializes is where all element values in the array have
string type already.

/be
Attachment #84925 - Attachment is obsolete: true
Attached patch Revised patch (obsolete) — — Splinter Review 
Brendan, thanks for the input.
khanson: for some reason, CodeWarrior is showing you bad indentation as good. 
See the two lines setting all_strings in your patch, e.g. -- not sure why. 
This patch is yours, but commented more, and with the indentation fixes, and a
tweak to the multi-line function call (to put the final &ca on its own line,
and again to indent all non-initial lines so their params start under the first
param).

/be
Attachment #84968 - Attachment is obsolete: true
Comment on attachment 85048 [details] [diff] [review]
indentation and comment improvements on khanson's last patch

r=brendan@mozilla.org, maybe shaver will sr= this patch.

/be
Attachment #85048 - Flags: review+
Brendan,  Thanks for the added comments and r=.  I will be more careful about
tabs from CodeWarrior getting into patches.
Comment on attachment 85048 [details] [diff] [review]
indentation and comment improvements on khanson's last patch

I'll sr anything after a few glasses of wine.

sr=shaver.  I like it.
Attachment #85048 - Flags: superreview+
The wine or the patch?
Mike, thanks for the sr=.
Let's get the final patch into the trunk (let me know if I should do the
checkin, as I have the patch applied to one of my working trees).  Then after
1.0 ships, we should mail drivers to get this into 1.0.1.

/be
Patch checked into trunk.
Here are my latest results on the three different tests above.

WinNT 4.0 (SP6); 500MHz CPU; 128M RAM                   
All times in ms:


              Num elts, lex sort    Num elts, num sort    Str elts, lex sort
              
IE6                 172                   300                    125
Moz (May 20)        1656                  515                    125
Moz (current)       1656                  500                     62


Notice the patch was checked into the trunk on May 26 -
Um, seems like there's more to be done here, are there plans already?
Phil, is the IE6 case in comment #5 the same as the first IE6 case in column 2
of comment #26 (3000ms vs 300ms, respectively)?
Also, what about the "string elements, numeric sort" column?
Boris, sorting numbers by value and strings lexically is probably what is most
commonly desired in JavaScript.  Strings sorted by string value being the most
frequent case.  Sorting strings by numerical value and sorting numeric values
lexically are probably rare beasts.
Right.  But this bug exists because the same code makes Mozilla run 
the "numbers sorted lexically" sort and makes IE run the "strings sorted 
lexically" sort, right?

I was mostly interested in all the data we have available...
Kenton: you're right - I made a typo in my last posting. 
IE6 takes about 3,000 ms on that case, not 300 as I wrote.

The results should have been

WinNT 4.0 (SP6); 500MHz CPU; 128M RAM                   
All times in ms:


              Num elts, lex sort    Num elts, num sort    Str elts, lex sort
              
IE6                  172                  3000                   125
Moz (May 20)        1656                   515                   125
Moz (current)       1656                   500                    62
Would it be possible to make the call to (default lexical) sort first do
something like this (ie comment #8 integrated into sort function):
for(i=0;i<theArray.length;i++) theArray[i]+='';
This would fix the "Num elts, lex sort" test and only add a negligible delay to
sorting (we'd still be faster than IE on all accounts).
I am not familiar with the javascript engine, so I couldn't find how to force
such a call.
Mailing drivers to get this into 1.0.1.
Keywords: adt1.0.1, mozilla1.0.1
Should this be resolved as fixed, since this has been checked into the trunk?

pschwartau/hong - can you pls verify the fix and perf gains on the trunk? thanks!
Keywords: nsbeta1
Whiteboard: [Need ADT Impact]
> Should this be resolved as fixed, since this has been checked into the trunk?
No, it should remain open until the fix is checked into the branch as well.

> Can you pls verify the fix and perf gains on the trunk?
Done; see Comment #32 comparing Moz (May 20) to Moz (May 30)
please checkin to the 1.0.1 branch. once there remove the "mozilla1.0.1+"
keyword and add the "fixed1.0.1" keyword.
Keywords: mozilla1.0.1 → mozilla1.0.1+
Attachment #85048 - Flags: approval+
adt1.0.1+ (on ADT's behalf) approval for chekin into the 1.0 branch. pls check
this into the 1.0 branch, then add the "fixed1.0.1".
Blocks: 143047
Keywords: adt1.0.1 → adt1.0.1+
Whiteboard: [Need ADT Impact] → [ADT2 RTM]
Keywords: mozilla1.0.1+ → fixed1.0.1
Checked into branch.
Are we leaving this bug open to investigate further ideas,
such as that in Comment #33? 
Comment #33 suggests we change the JavaScript language specification to fine
tune the benchmark discussed at the beginning of this bug.  The language is
currently well defined.  Users, must be aware of 1) how they are storing array
elements and 2) what sorting criteria they are using (see comments #11 & #30).  

BTW a good method for forcing string elements is to use the toString() method.
for (i = 0; i < a.length; i++)  a [i] =
parseInt(Math.random()*a.length).toString ();

I am convinced that more performance can be squeezed out of the array sort
algorithm and would be willing to explore, but I think there are more important
problems to pursue. I suggest we retire this bug.
I agree with khanson, if someone wants to profile and tune more, file a new bug
with fresh data.

BTW, there are faster ways to force a string than this:

for (i=0; i<a.length; i++) a[i] = parseInt(Math.random()*a.length).toString();

Consider

for (i=0; i<a.length; i++) a[i] = String(Math.random()*a.length);

or even

for (i=0; i<a.length; i++) a[i] = '' + Math.random()*a.length;

The last is fastest.

/be
Status: NEW → RESOLVED
Closed: 22 years ago
Resolution: --- → FIXED
Marking Verified -
Status: RESOLVED → VERIFIED
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%.
Igor, could you open a new bug and attach that patch (and cc me on it)?
Ok, see a new bug 181828
Flags: testcase?
The former URL is now at:
http://wd-testnet.world-direct.at/mozilla/dhtml/funo/jsTimeTest.htm

Running with Deer Park Alpha 2 I get 516ms vs. 63ms with MSIE6 (on win-xp sp2).

So what are we doing about this?
URL: http://wd-testnet.world-direct.at/moz...
I assume you mean "what are we doing with this after I put up a pair of profiles
for the shell and DOM test models?", right? =)
This is a verified fixed bug, there's no point talking in it.

Before filing a new bug, though, check out the patch in bug 224128 and measure
its performance.  If that bug's patch fixes the performance problem, no need for
yet another bug.

/be
Flags: testcase? → testcase-
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: