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

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P3)

Description

[Biju]

Attachment: 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

Comment 1

[Brendan Eich [:brendan]]

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.

Comment 2

[Biju]

(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

Comment 3

[Biju]

Attachment: slow_sort_str.html

Comment 4

[Biju]

Attachment: slow_sort_int.html

Comment 5

[Biju]

(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

Comment 6

[Igor Bukanov]

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?

Comment 7

[Brendan Eich [:brendan]]

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

Comment 8

[Igor Bukanov]

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

Comment 9

[Igor Bukanov]

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.

Comment 10

[Igor Bukanov]

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

Comment 11

[Igor Bukanov]

Attachment: Implementation v1

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.

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 256739 [details] [diff] [review]
Implementation v1

Pinging for fresh patch for review.

/be

Comment 13

[Mike Schroepfer]

Ping - is this something we want to take to the finish for 1.9?

Comment 14

[Brian Crowder]

Attachment: Implementation v1a

Updated patch to trunk.

Comment 15

[Brian Crowder]

Igor, please check my work, then set review flag?

Comment 16

[Brian Crowder]

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.

Comment 17

[Brian Crowder]

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.

Comment 18

[Igor Bukanov]

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.

Comment 19

[Brian Crowder]

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?

Comment 20

[Igor Bukanov]

Brian: I filed bug 403878 about js_InternalCall => js_Invoke. Would you take it?

Comment 21

[Igor Bukanov]

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 22

[Brendan Eich [:brendan]]

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

Comment 23

[Brian Crowder]

(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?

Comment 24

[Igor Bukanov]

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

Comment 25

[Brian Crowder]

Alright.  I will update and push through this patch with brendan's remarks fixed, and then address the other idea in bug 403977

Comment 26

[Brian Crowder]

Attachment: Implementation v2

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.

Comment 27

[Brendan Eich [: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

Comment 28

[Brian Crowder]

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?

Comment 29

[Brian Crowder]

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.

Comment 30

[Brendan Eich [:brendan]]

(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

Comment 31

[Brian Crowder]

Attachment: Implementation v2b

Comment 32

[Brendan Eich [:brendan]]

Comment on attachment 290623 [details] [diff] [review]
Implementation v2b

Great, thanks.

/be

Comment 33

[Brian Crowder]

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)

Comment 34

[Reed Loden [:reed]]

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

Comment 35

[Bob Clary [:bc] (inactive)]

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

Comment 36

[Bob Clary [:bc] (inactive)]

verified fixed 2007-12-09 1.9.0 linux|mac|win

Comment 37

[Mike Schroepfer]

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?

Comment 38

[Brian Crowder]

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.