Add support for ES2023 `Array.prototype.toSorted`

[robik]

Summary

Overview

This PR implements support for new Array.prototype.toSorted(comparefn) method introduced in ES2023. Remaining methods are implemented in #1286.

Tasks

• [x] Implementation
• [x] Add tests
• [x] Format changes
• [ ] Add documentation somewhere?

Implementation/review notes

Also I'd like to highlight proposed toSorted implementation. I used sparseSort unconditionally, that might have some quirks when used with proxes, although from what I understand it only relates to modifying the original object and should not be an issue because we are creating a new array.

Test Plan

Code is annotated with algorithm steps from EcmaScript specification for easier verification and maintenance. I also added tests to verify that methods work as intended. There might be some more edge cases that might be covered based on your experience.

Quick test:

$ echo "[3,2,1,5,4].toSorted()" | ./bin/hermes
# >> [ 1, 2, 3, 4, 5, [length]: 5 ]

[mattbfb]

Thanks for putting this together! I think there are a couple lingering conflicts and test failures, but I believe rebasing will resolve both.

EDIT: Ah, the tests re-ran and the test failures have cleared already.

[tmikov]

There are a couple of issues that will need to be addressed here:

• The duplication of sortSparse() is probably unnecessary, since in both cases we are creating a new array
• Proxy and HostObject are not handled
• toSorted() of a normal dense array will be very slow because sortSparse() queries all property names, so for example for an array of 1000 elements, there will be a 1000 properties ("0", "1", "2", ...).

When looking into this, I noticed that Hermes itself is not spec-compliant when using Array.prototype.sort() on a dense array. We are sorting the array in place, but we should be copying it first as per the spec, which in turn will allow us to reuse the second part of sortSparse() (this then should enable us to optimize SortModel, but that is a different story altogether).

In the end there should be a lot of reuse between all these cases.

What I am proposing is that we can fix Array.prototype.sort() and if you wait a little you can base toSorted() on top of the same infra.

[robik]

@tmikov Sure thing! I can wait for the fix and rebase my PR on top of it, but if it is a low priority for you, maybe I can be of any help and dive into this topic. Would need a small guidance of how do you see it and some context 🙂

[tmikov]

@robik that is excellent! If you are interested, here is what I think needs to be done, in a few incremental stages, each adding more optimization:

Stage 1: correct implementation of sort

• We throw away sortSparse() (though we may reuse the code for some of the things it does). It is garbage. I take full responsibility, since I believe I added it! :-)
• We need to implement sortIndexedProperties() as per the spec. It will be somewhat similar to sortSparse(). It allocates a JSArray, copies all properties into it using the spec algorithm (for now it doesn't care about the type of the input object), sorts the JSArray using SortModel, and returns the new array.
• Implement sort() and toSorted() by invoking sortIndexedProperties() with the appropriate parameters as per the spec. In the case of sort(), we then need to copy the properties back into the original object using the spec algo.

At the end of this stage, we should have spec compliant sort() and toSorted() , fairly straight-forward code with good reuse. I suggest we land a PR at this stage.

Stage 2: optionally implement fast path for JSArray input

If the input object is a JSArray, we can use a fast path when copying the properties in sortIndexedProperties(). Basically using the technique from here: we can read the indexed property using a fast method, and only if it returns "empty" (a "hole"), we fallback to the slow method.

We can also use a fast path for copying the elements back into JSArray in sort() by relying on unsafeSetExistingElementAt() after ensuring the array has the correct size and capacity.

Again, if we get here, we should land a PR as an incremental improvement (though it will be a big one perf-wise).

Stage 3: optionally improve SortModel

SortModel is a general purpose model for sorting, using virtual functions and assuming the worse case for the underlying object - that it is not an array and thay it may have "holes". But that is no longer the case after Stage 1. Now SortModel is only used to sort either a truly dense JSArray or a TypedArray. Neither have holes and the latter doesn't even have "undefined".

So we can do a couple of things:

1. We can simplify the implementation of StandardSortModel to rely on having a truly dense JSArray which has not "escaped" and thus cannot be changed by user code. It can use unsafe operations to access the elements, etc. This already should be a good speedup.
2. We can turn the sort routine into a template and eliminate the virtual function calls. We will provide efficient implementations for JSArray and TypedArray. We should start getting close to C++ performance here (module the cost for the comparison function which is still JS).

Anyway, it would be great if you implemented any of these stages. Stage 1 would be great, since it simplifies the code and makes us compliant. Let me know, so I can remove it from my TODO list :-)

[robik]

Hey @tmikov, sorry for the delay and thanks for great write-up! I've pushed the changes covering stage 1. If all is good I will work on next stage :)

However, the tests seem to be failing on regress-invalidated-descriptor-std-sort-model-swap.js, which fails on Chrome/Firefox as well 🤔

[facebook-github-bot]

@tmikov has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator.

[tmikov]

@robik thanks! We will start reviewing it ASAP.

[facebook-github-bot]

@robik has updated the pull request. You must reimport the pull request before landing.