Closed Bug 371636 Opened 17 years ago Closed 17 years ago

IE Array sort on numbers using default string comparator is 5x faster

Categories

(Core :: JavaScript Engine, defect, P3)

defect

Tracking

()

VERIFIED FIXED
mozilla1.9beta2

People

(Reporter: BijuMailList, Assigned: crowderbt)

References

Details

(Keywords: perf, testcase)

Attachments

(4 files, 3 obsolete files)

Attached file slow_sort.html
Performance issue: 
On IE Array.sort is 5x to 10x faster than Moz,
and Array.concat is 2x faster 

See attached test suit slow_sort.html
2218 milliseconds on Fireox Trunk
 485 milliseconds on IE6


Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a3pre) Gecko/20070220 Minefield/3.0a3pre


PS: My PC is almost 10x slow than Brendan's
Keywords: perf, testcase
OS: Windows XP → All
First, please file separate bugs on separate issues. Any concat runtime problem is unrelated to sort performance.

Second, sorting was optimized in the trunk for the common mostly-sorted case. You are testing randomly distributed numbers on the unit interval. Can you test mostly-ordered data and confirm that we beat IE? See bug 224128.

Third, your avg_t computation looks wrong -- why is it happening on every call? You are computing (avg_t * 19 + t) / 20 for avg_t = t1 the first time, where t ranges from t1..tN for N=20, which makes avg_t follow this sequence:

t1, (t1*19+t2)/20, (((t1*19+t2)/20) * 19 + t3)/20, ...

which is not the same as (t1 + ... + tN)/N for N=20.

(In reply to comment #1)
> First, please file separate bugs on separate issues. 
> Any concat runtime problem is unrelated to sort performance.

see comment below, found issue of concat() as byproduct of attached test.
I can create another defect for it.

> Second, sorting was optimized in the trunk for the common mostly-sorted case.
> You are testing randomly distributed numbers on the unit interval. 

My test have sort on both "mostly sorted" and "random array"  
Test 0 : "mostly sorted" 
Test 2 : "random array" 

Test 1 and 3 are to find and eliminate the effect of push() and concat() on result for Test 0 and 2.

> Can you test mostly-ordered data and confirm that we beat IE? 
> See bug 224128.

Tested attachment 135062 [details] (Quick and dirty benchmark) at bug 224128
and here are the results

Result on IE6						
=================						
num	int random*	int sorted	string random	string sorted	object reverse*	
500	31	0	16	0	31	
1000	63	15	16	15	172	
2000	171	32	31	31	688	
4000	750	78	78	62	--	
8000	--	187	266	234	--	
16000	--	532	906	797	--	
32000	--	--	--	--	--	
64000	--	--	--	--	--	
						
Result on Firefox Trunk						
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a3pre) Gecko/20070220 Minefield/3.0a3pre						
num	int random*	int sorted	string random	string sorted	object reverse*	
500	0	15	16	0	0	
1000	16	15	15	16	16	
2000	31	78	15	16	47	
4000	188	94	63	140	94	
8000	172	343	156	110	313	
16000	375	609	313	219	563	
32000	781	--	656	453	--	
64000	--	--	--	906	--	
						

Here are the difference
=======================
My test was on float, but attachment 135062 [details] has test on int, string and object
I modified my test for testing int and string, and found:-
on string
   - Moz is fast 
on mostly sorted int
   - IE6 is faster (2x)
on random int array 
   - IE6 is faster (6x)


I see an issue with attachment 135062 [details] 

   var t = new Date ();
   check.sort (inttest);
   testsort (check, inttest);
   var t2 = new Date ();

we are not removing execution time of "testsort()" and "inttest()"



> Third, your avg_t computation looks wrong 
> -- why is it happening on every call?
> You are computing (avg_t * 19 + t) / 20 for avg_t = t1 the first time, where t
> ranges from t1..tN for N=20, which makes avg_t follow this sequence:
> 
> t1, (t1*19+t2)/20, (((t1*19+t2)/20) * 19 + t3)/20, ...
> 
> which is not the same as (t1 + ... + tN)/N for N=20.

It is just another way to show trend..
I know my way finding avg is not same as "(t1 + ... + tN)/N for N=20"
You can ignore it if you dont like

Reason why I used that formula was
I didnt want to see avg = total_time/total_num_of_iteration
or take complication of doing avg = (t1 + ... + tN)/N
ie, storing t1 to tN, and summing etc...

people liked my formula when I used it show rate / record processed

Attached file slow_sort_str.html
Attached file slow_sort_int.html
(In reply to comment #2)
> (In reply to comment #1)
> > First, please file separate bugs on separate issues. 
> > Any concat runtime problem is unrelated to sort performance.
> 
> see comment below, found issue of concat() as byproduct of attached test.
> I can create another defect for it.

Done bug 371688
Summary: Performance : IE Array.sort is 5x faster than Moz, [].concat is 2x fast → Performance : IE Array.sort is 5x faster than Moz
The test contains:

// collect random numbers
    for (i = 0; i < cnt; i++) {
        a.push(parseInt(1000 * Math.random()));
        b.push(parseInt(1000 * Math.random()));
    }
    a.sort(); // sort target array

But this is useless in practice since this compare integers as strings during sorting. For example,
  1 3 5 7 9 11 
will be sorted as
  1 11 3 5 7 9

For a useful sorting one has to pass an explicit compare function:
    a.sort(function(a, b) { return a - b });

I suspect that the reason MSIE is faster then FF is that MSIE optimizes this compare-integers-as-strings case. Given the amount of such useless soring benchmarks on the net claiming MSIE superiority, probably FF should also optimize it?
I agree, we should optimize this case if the size cost (data and code, code is more important) is small enough. One thought: memoize the first N natural numbers represented as strings, speeding up conversion to index into a lookup table (N = 1000 just for this benchmark ;-).

Igor, do you want to take this bug?

/be
(In reply to comment #7)
> I agree, we should optimize this case if the size cost (data and code, code is
> more important) is small enough. One thought: memoize the first N natural
> numbers represented as strings, speeding up conversion to index into a lookup
> table (N = 1000 just for this benchmark ;-).

There other ways to optimize this:

1. Avoid String construction during compare of non-strings. For integers and doubles we can definitely use stack-allocated storage.

2. Convert all array elements to strings only once during the sorting using extra storage.
Assignee: general → igor
When I added a special code to detect sorting array of ints using string compare and then call a special compare function for that, the timing for the following test case:

function test(power)
{
  var N = 1 << power;
  var a = new Array(N);
  for (var i = 0; i != N; ++i)
    a[i] = (N-1) & (0x9E3779B9 * i);
  var now = Date.now;
  var t = now();
  a.sort();
  return now() - t;
}

var t = test(18);
print(t);

dropped from 6s to 300ms (the code run 20 times faster!) for an optimized build of the shell compiled with JS_THREADSAFE defined. But that is a code that optimizes just for the benchmark that would never be executed for anything useful. I will try to see what kind of savings can be archived through more generic approach.
Status: NEW → ASSIGNED
(In reply to comment #9)
> dropped from 6s to 300ms (the code run 20 times faster!) for an optimized build
> of the shell compiled with JS_THREADSAFE defined.

That prototype patch had a bug. The real number is decrease from 6s to 1.6s.

Attached patch Implementation v1 (obsolete) — Splinter Review
Patch that drops the execution time for the test from comment 9 from 6s to 1.6s. But before asking for a review I will try to minimize the code bloat.
Blocks: 117611
Summary: Performance : IE Array.sort is 5x faster than Moz → IE Array sort on numbers using default string comparator is 5x faster
Comment on attachment 256739 [details] [diff] [review]
Implementation v1

Pinging for fresh patch for review.

/be
Ping - is this something we want to take to the finish for 1.9?
Flags: blocking1.9?
Attached patch Implementation v1a (obsolete) — Splinter Review
Updated patch to trunk.
Attachment #256739 - Attachment is obsolete: true
Igor, please check my work, then set review flag?
Giving P3; this seems like a very good perf fix to me, assuming my monkey patch-updating skills are up to snuff and Igor is satisfied with the original patch.
Priority: -- → P3
Flags: blocking1.9? → blocking1.9+
Comment on attachment 287868 [details] [diff] [review]
Implementation v1a

Brendan:  Can you take a look at this?  I'd like to wrap up this patch, and I don't see activity from Igor.
Attachment #287868 - Flags: review?(brendan)
Comment on attachment 287868 [details] [diff] [review]
Implementation v1a

For extra speed js_InternalCall in sort_compare can be replaced by js_Invoke like it is done in array_extra, but that can be done in a separated bug.
Attachment #287868 - Flags: review+
Brendan:  if you like this patch, can you go ahead and a+ it, as well?  Igor, have you opened a new bug for the js_InternalCall => js_Invoke enhancement?
Blocks: 403878
Brian: I filed bug 403878 about js_InternalCall => js_Invoke. Would you take it?
Blocks: 403977
I suggest an alternative approach to the patch from the comment 14. In array_sort when the code detects that not all elements are strings and the string comparator is requested, it can convert the elements to string only once using an auxiliary rooted array. This will not only address the original problem but also helps with bug 403977.  
Comment on attachment 287868 [details] [diff] [review]
Implementation v1a


>+    struct {
>+        jsval val;
>+        JSString *str;
>+        char *chars;
>+        char buf[DTOSTR_STANDARD_BUFFER_SIZE];

Nit: align member declarators (including * of course) on same column (typically 4-space tabstopped).

>+                /* Root as ToString for the second arg can GC it. */
>+                *ca->localroot = STRING_TO_JSVAL(c->str);

Comment wording is a little awkward -- how about "Root ToString result, as the second iteration can GC."

>+        for (;;) {
>+            if (n-- == 0) {

Would prefer --n; after this if.

>+                *result = n1 < n2 ? -1 : (n1 > n2) ? 1 : 0;

Parenthesize first ? condition as is done for second and elsewhere in SpiderMonkey.

>+                break;
>             }
>+            *result = (int)*jschars++ - (int)*chars++;
>+            if (*result != 0)
>+                break;
>         }
>+        if (conv[0].str)
>+            *result = -*result;

You want this negation of *result only if the strings differ in some character, right? Otherwise, you set *result correctly based on the chained ?: above, it seems to me. Move up to do right before the break if (*result != 0).

> /* The buf must be big enough for MIN_INT to fit including '-' and '\0'. */

Pre-existing comment wants to say INT_MIN here (<limits.h> macro).

r=me with these addressed.

/be
(In reply to comment #21)
> I suggest an alternative approach to the patch from the comment 14. In
> array_sort when the code detects that not all elements are strings and the
> string comparator is requested, it can convert the elements to string only once
> using an auxiliary rooted array. This will not only address the original
> problem but also helps with bug 403977.  
> 

Does this mean you think we should abandon the other patch?  Are you working on this, or should I take it?
> Does this mean you think we should abandon the other patch?

No! The patch avoids creation of JSString instances all together when sorting numbers. That should be kept. Since the problem comes from JSObject instances that will be repeatedly converted to strings during sorting using the default comparator, my idea is to extend the patch to make sure that such objects are converted to string only once.

> Are you working on this, or should I take it?

I am not working on that but it would be nice if somebody will to avoid bug 403977 and similar in future.
Alright.  I will update and push through this patch with brendan's remarks fixed, and then address the other idea in bug 403977
Attached patch Implementation v2 (obsolete) — Splinter Review
brendan: can you please clarify your comment re: the conv[0].str result negation?  It actually seems entirely bogus to me, since the char comparisons and length checks above seem as though they should take care of everything.  I'm -sure- I'm missing something obvious.
Assignee: igor → crowder
Attachment #287868 - Attachment is obsolete: true
Attachment #290602 - Flags: review?(brendan)
Attachment #287868 - Flags: review?(brendan)
+        i = conv[0].str ? 0 : 1;
+        jschars = JSSTRING_CHARS(conv[i].str);
+        n1 = JSSTRING_LENGTH(conv[i].str);
+        chars = conv[1 - i].chars;
+        n2 = strlen(chars);
+        n = JS_MIN(n1, n2);
+        for (;;) {
+            if (n == 0) {
+                *result = (n1 < n2) ? -1 : (n1 > n2) ? 1 : 0;
+                break;
             }
+            --n;
+            *result = (int)*jschars++ - (int)*chars++;
+            if (*result != 0)
+                break;
         }
+        if (conv[0].str)
+            *result = -*result;

Let conv[0].str = "abc"L, and conv[1].chars = "abcd". n1 = 3, n2 = 4, n = 3. First three character codes match so we hit the if (n == 0) then clause, which sets *result = (3 < 4) ? -1 : ...; and breaks to the if (conv[0].str) after the loop. Since conv[0].str is non-null, the -1 in result gets negated to be 1. But "abc"L is *not* greater than "abcd".

/be
Right, so in fact

+        if (conv[0].str)
+            *result = -*result;

should simply be removed from the patch?  Doesn't the code preceding it do the right thing in all cases?
No, sorry.

+        if (conv[0].str)
+            *result = -*result;

should be

+        if (conv[1].str)
+            *result = -*result;

To handle the case where the JSString is actually the second argument, and the comparison results need to be negated.
(In reply to comment #29)
> No, sorry.
> 
> +        if (conv[0].str)
> +            *result = -*result;
> 
> should be
> 
> +        if (conv[1].str)
> +            *result = -*result;
> 
> To handle the case where the JSString is actually the second argument, and the
> comparison results need to be negated.

Right. New patch? I'll r+a it.

/be
Attachment #290602 - Attachment is obsolete: true
Attachment #290602 - Flags: review?(brendan)
Comment on attachment 290623 [details] [diff] [review]
Implementation v2b

Great, thanks.

/be
Attachment #290623 - Flags: review+
Attachment #290623 - Flags: approval1.9+
If someone not-me lands this, patch credits go to Igor, I'm just babysitting (though of course anything wrong with the patch is my fault)
Keywords: checkin-needed
Hardware: PC → All
Checking in js/src/jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.131; previous revision: 3.130
done
Checking in js/src/jsnum.c;
/cvsroot/mozilla/js/src/jsnum.c,v  <--  jsnum.c
new revision: 3.91; previous revision: 3.90
done
Checking in js/src/jsnum.h;
/cvsroot/mozilla/js/src/jsnum.h,v  <--  jsnum.h
new revision: 3.35; previous revision: 3.34
done
Status: ASSIGNED → RESOLVED
Closed: 17 years ago
Keywords: checkin-needed
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9 M10
Checking in js1_5/extensions/regress-371636.js;
/cvsroot/mozilla/js/tests/js1_5/extensions/regress-371636.js,v  <--  regress-371636.js
initial revision: 1.1
done
Flags: in-testsuite+
verified fixed 2007-12-09 1.9.0 linux|mac|win
Status: RESOLVED → VERIFIED
With this patch I'm seeing the following results for the first attachment:

Test0
IE7: 188
FF3: 530

Test2
IE7: 135
FF3: 1379

For the second attachment I'm seeing:

Test0
IE7: 72
FF3:15

Test2:
IE7: 60
FF3: 48

===

Is that as expected?
Yeah, I think these results are to be expected.  The patch from bug 403977 is more general and will help with these cases.  It's worth mentioning that doing lexicographic sorts of arrays of numbers is probably bogus and that optimizing for it at the cost of doing at least _some_ extra work may be a bad idea.  I think the hit we take is pretty minor, though.
You need to log in before you can comment on or make changes to this bug.