There are two forms of typed arrays to detect here: Typed Arrays (http://www.khronos.org/registry/typedarray/specs/latest/) and objects where type inference tells us the array is packed and has a single element type. In either case, we should be able to use a simple in-place sort (facilitated by the new templated MergeSort) that would go significantly faster than what we have now in array_sort().

This sounds interesting, I'd like to work on this bug. Luke, is there any previous specialization work like this that I can look at?

Hmm, there are no awesome examples that come to mind. array_toString_sub contains an example of how we special-case array.join when performed on a dense array (isDenseArray()). I suggest starting with typed arrays; these can be detected (analogous to isDenseArray) via IsFastTypedArrayClass (in jstypedarray.h).

Typed Arrays don't actually have a sort method, so I suppose this only applies to the latter case with TI?

[:reuben] from comment #3) > Typed Arrays don't actually have a sort method, so I suppose this only > applies to the latter case with TI? On the other hand, |Array.prototype.sort.call(myTypedArray)| works. I suspect people will use it.

(In reply to David Rajchenbach Teller [:Yoric] from comment #4) > [:reuben] from comment #3) > > Typed Arrays don't actually have a sort method, so I suppose this only > > applies to the latter case with TI? > > On the other hand, |Array.prototype.sort.call(myTypedArray)| works. I > suspect people will use it. Ah, good to know, thanks! Luke, I'm probably missing something here, but as far as I can see, TI only guarantees the object is _not_ a packed/typed array. Can't we simply check if all elements in the array are numbers like we do with allStrings here: https://mxr.mozilla.org/mozilla-central/source/js/src/jsarray.cpp#2125 ? I'm attaching the patch as it is now for feedback, there are probably more cases to cover. Am I in the right direction?

(In reply to Reuben Morais [:reuben] from comment #5) > Luke, I'm probably missing something here, but as far as I can see, TI only > guarantees the object is _not_ a packed/typed array. The *absence* of OBJECT_FLAG_NON_PACKED implies packed. You can see some example uses of these by grepping for this flag in src/methodjit. > Can't we simply check > if all elements in the array are numbers like we do with allStrings here: > https://mxr.mozilla.org/mozilla-central/source/js/src/jsarray.cpp#2125 ? So one issue that I forgot in comment 0 is that numbers need to be compared lexicographically. Bug 715265 is already attacking this issue and should be landing a lexicographic int compare (that you can reuse in this bug; I should have filed a dependency) soon. Given this, there is less win to be had by used typedness. Since calling a comparator function is relatively quite slow and integer less-or-equals is relatively quite fast, you may also be interested in bug 715419.

(In reply to Luke Wagner [:luke] from comment #6) > (In reply to Reuben Morais [:reuben] from comment #5) > > Luke, I'm probably missing something here, but as far as I can see, TI only > > guarantees the object is _not_ a packed/typed array. > > The *absence* of OBJECT_FLAG_NON_PACKED implies packed. You can see some > example uses of these by grepping for this flag in src/methodjit. Ack. > So one issue that I forgot in comment 0 is that numbers need to be compared > lexicographically. Bug 715265 is already attacking this issue and should be > landing a lexicographic int compare (that you can reuse in this bug; I > should have filed a dependency) soon. Given this, there is less win to be > had by used typedness. I got a bit lost here in the end, could you clarify? With the patch from bug 715265, it seems I could simply extend/replicate its logic to work with larger integer sizes and use that for typed arrays, but in the end there you said it might not be worth the effort?

(In reply to Reuben Morais [:reuben] from comment #7) > With the patch from bug > 715265, it seems I could simply extend/replicate its logic to work with > larger integer sizes and use that for typed arrays, but in the end there you > said it might not be worth the effort? That is correct. Only Uint32Array (when there was a value above INT32_MAX in the array) would benefit since, for the other int array types, GetElement produces v.isInt32(). It would also be nice to sort typed arrays in-place instead of copying into the temporary 'vec', but, based on profiles I've seen, that is a relatively small % of total sort time. Sorry for the trouble.

Why does Value::payloadAsRawUint32() return incorrect uint32_t? For example, one of array element is set to 4294967295, but 4292870144 is returned from payloadAsRawUint32(). Therefore, uint32_t auint = static_cast<uint32_t>(a.toNumber()); is used instead in the patch. A new branch will be taken only if a value exceeds the int32 limit. script used to test performance on my local machine: var b = new ArrayBuffer(200000 * 4); var arr = new Uint32Array(b); arr[0] = 4294967295; for (var i = 1; i < 200000; ++i) arr[i] = Math.floor(Math.random() * 10000000000); var bef = new Date(); Array.prototype.sort.call(arr); var aft = new Date(); print(aft - bef + "ms"); about 59ms with patch about 112ms without patch

Comment on attachment 742209 [details] [diff] [review] WIP Hi Xin, thanks for looking at this! Unfortunately, it looks like the world has changed since this bug was filed and I don't think there is quite the same room for optimization as there was more than a year ago. (I should remove the [good first bug] tag.) Value::payloadAsRawUint32() is a low-level backdoor that breaks the Value abstraction and, as you've seen, is not generally safe for use. Fundamentally, v.isNumber() means (v.isInt32() || v.isDouble()), so int32_t and double are the fundamental C++ types you have to work with. Because of this, it is not sufficient for your patch to check v.isNumber() && v.toNumber() > 0 and then cast (uint32_t)v.toNumber(); that is incorrect for values larger than UINT32_MAX. To be honest, I'm not sure if people are going to be sorting typed arrays a la comment 4 enough to warrant the special case, so I'm inclined to resolve this bug WONTFIX. I hope you aren't discouraged and you keep looking at JS engine bugs or say 'hi' on #jsapi.

(In reply to Luke Wagner [:luke] from comment #10) > To be honest, I'm not sure if people are going to be sorting typed arrays a > la comment 4 enough to warrant the special case, so I'm inclined to resolve > this bug WONTFIX. I hope you aren't discouraged and you keep looking at JS > engine bugs or say 'hi' on #jsapi. Thanks for the feedback. I will look for other JS engine bugs.