121136 - Specialcase numbers when comparing in sorting

Status: VERIFIED INVALID

(Core :: JavaScript Engine, defect)

Description

[Daniel Bratell]

With this patch to sort_compare in jsarray.c, the time for sorting 10000 random
integers goes from a couple of seconds to ~133ms. As a matter of fact, that's
20% faster than MSIE5.5. I don't know if it's the right thing to do since I
don't understand why the sorting is done by comparing strings right now, but the
sort becomes way faster.

  	} else if (av == JSVAL_VOID || bv == JSVAL_VOID) {
  	    /* Put undefined properties at the end. */
  	    cmp = (av == JSVAL_VOID) ? 1 : -1;
+         } else if (JSVAL_IS_INT(av) && JSVAL_IS_INT(bv)) {
+             cmp =  JSVAL_TO_INT(av) - JSVAL_TO_INT(bv);
+         } else if (JSVAL_IS_DOUBLE(av) && JSVAL_IS_DOUBLE(bv)) {
+             cmp = JSVAL_TO_DOUBLE(av) - JSVAL_TO_DOUBLE(bv);
  	} else if ((astr = js_ValueToString(cx, av)) != NULL &&


Btw, the time is with the patch in bug 99120 attached.

Comment 1

[Brendan Eich [:brendan]]

Sorry, see ECMA-262 Edition 3, 15.4.4.11 -- the default comparison is string <>,
not numeric <>.

/be

Comment 2

[Brendan Eich [:brendan]]

We should be careful not to over-optimize one not particularly representative
benchmark.  I say this only because it seems like the benchmarks for sorting
tend to use the default comparison, and arrays of numbers.  Real-world sort
cases I've seen sort based on strings (e.g., directory listings for the filepicker).

/be

Comment 3

[Phil Schwartau]

Verifying Invalid through Brendan's observation in Comment #1: 
see steps 13, 16, 17 of the ECMA (Edition 3) 15.4.4.11 algorithm.

Comment 4

[Daniel Bratell]

I knew it was too good to be true.