Specialcase numbers when comparing in sorting

VERIFIED INVALID

Status

()

VERIFIED INVALID
17 years ago
17 years ago

People

(Reporter: bratell, Assigned: khanson)

Tracking

({perf})

Trunk
x86
Windows 2000
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

17 years ago
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.
(Reporter)

Updated

17 years ago
Blocks: 117611
Depends on: 99120
Keywords: patch, perf
Sorry, see ECMA-262 Edition 3, 15.4.4.11 -- the default comparison is string <>,
not numeric <>.

/be
Status: NEW → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → INVALID
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

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

Comment 4

17 years ago
I knew it was too good to be true.
You need to log in before you can comment on or make changes to this bug.