https://github.com/tc39/ecma262/pull/2723

Invoke std::sort without a comparator function for integral types including
uint8_clamped. For floating point types invoke std::sort with a comparator
function to ensure negative zero is sorted before positive zero. To further
improve the performance when sorting floating point numbers, compare numbers
using their unsigned sort value using the same approach as currently used in
RadixSort.

When the backing buffer is a SharedArrayBuffer, we need to copy the TypedArray
contents to avoid UB in std::sort when a different thread is modifying the
same SharedArrayBuffer memory.

The next two patches in this queue will provide specialisations for
TypedArraySort() to select faster sort algorithms than std::sort for
certain TypedArray element types.

Direct translation of the JS counting sort implementation to C++. The stack
allocated buffer has inline storage to store the complete uint8_t range. (This
function will also be used in the next part for uint16_t, but in that case the
complete buffer will be heap allocated.)

The C++ implementation is faster than the JS implementation and therefore we
can use a smaller limit when we fallback to std::sort for small arrays.

Depends on D143285

An almost direct translation of the JS implementation to C++. In contrast to
the JS implementation, we're using a smaller fallback to std::sort, because
the C++ implementation is faster, but we're also calling into std::sort for
large arrays to avoid allocating a large heap buffer.

As a further improvement, the radix sort implementation calls the counting sort
function for 16-bit types when the number of elements reaches 2^16. That way
we can further reduce the number of allocated heap memory.

The pre- and post-process steps from the JS implementation can be omitted,
because we can directly interpret the TypedArray memory contents as unsigned
integers in C++.

The concurrent write access handling in SortByColumn is necessary to avoid
an out-of-bounds access when a different thread writes to the same shared
memory location. This was also an issue in the JS implementation, except the
only visible outcome in that implementation was that the internal aux array
could leak to the user.

Depends on D143286

Depends on D143287

https://github.com/tc39/ecma262/pull/1585 changed Array.prototype.sort to
first collect all elements in a temporary list. And because TypedArray.prototype.sort
follows Array.prototype.sort, the same copying has to happen here.

Depends on D143288

Similar to part 5, concurrent write accesses shouldn't affect the sort algorithm.

Depends on D143289

Remove the check per https://github.com/tc39/ecma262/pull/2723.

Depends on D143290

Backed out for causing reftest failures on sort-tonumber.js. CLOSED TREE

Backout link : https://hg.mozilla.org/integration/autoland/rev/ad488bea5c77cf79df56f9ea25df44f72bb3450d

Push with failures: https://treeherder.mozilla.org/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception%2Crunnable&revision=cac8af0a354284932bf33e385ae401e860c2efc7&selectedTaskRun=NoLZBMB9TvatgQ9FJucWfQ.0

Link to failure log: https://treeherder.mozilla.org/logviewer?job_id=377094672&repo=autoland&lineNumber=30659

Meh, test262 upstream now calls detachArrayBuffer on an already detached array buffer, which isn't supported in the browser.js implementation.

https://hg.mozilla.org/mozilla-central/rev/0214766ba072
https://hg.mozilla.org/mozilla-central/rev/b245af1692e1
https://hg.mozilla.org/mozilla-central/rev/2c8f470e2be8
https://hg.mozilla.org/mozilla-central/rev/b69a3b47f56d
https://hg.mozilla.org/mozilla-central/rev/d76311eb2427
https://hg.mozilla.org/mozilla-central/rev/0dc0d70ce93b
https://hg.mozilla.org/mozilla-central/rev/416ec1f14c2d
https://hg.mozilla.org/mozilla-central/rev/0b95325e435a

== Change summary for alert #34391 (as of Fri, 10 Jun 2022 08:34:46 GMT) ==

Improvements:

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=34391