759337 - sort on arrays of arrays is quite slow

Status: RESOLVED DUPLICATE of bug 715181

(Core :: JavaScript Engine, defect)

Description

[Sam Tobin-Hochstadt [:samth]]

This program: 

var arr = [];
for(var i = 0; i< 25000; i++) {
    arr.push([Math.random(), String(i)])
}
var t = Date.now()
arr.sort(function(a,b) { return (a[0] < b[0]); })
var t2 = Date.now() - t;

Produces timings of about 15ms on Chromium 18 and 71ms on FF Nightly 5/28.  On my HTC Sensation, FF (Fennec) Nightly is 750-800ms, while Android stock(!) is between 50-150 ms and Opera Mobile is ~200ms.

The URL field contains a page that will run this on the browser of your choice.

Comment 1

[Luke Wagner [:luke]]

The source of the slow-down here isn't the array-of-arrays, but the use of a JS comparator.  Since Spidermonkey implements sort in C++, this requires a C++-to-JS call for each comparison.  v8 implements sort() in JS which allows them to do a fast (inlinable) JS-to-JS call for each comparison.  We already have bugs for this; we've been talking about self-hosting sort(), forEach(), replace() etc for a while now.  There's hope of it actually happening sometime soon since I think there are plans to add self-host functionality for all these new unicode functions.

Comment 2

[Guilherme Lima]

Firefox 43 = 86 ms
Nightly 46 after bug 715181 = 28 ms
Chrome 48 = 10 ms