Hermes: Array.prototype.sort isn't stable

[SinLucifer]

Hermes version: 0.2.1 ~ 0.4.1

I noticed the issues about Infinite loop when sorting , and find two others problem about Array.sort with a comparator.

1. The sort result will not base on input order.

let array = [
    { "index": 0, "key": 1 }, 
    { "index": 1, "key": 1 }, 
    { "index": 2, "key": 1 }, 
    { "index": 3, "key": 1 }, 
    { "index": 4, "key": 2 }, 
    { "index": 5, "key": 1 }, 
    { "index": 6, "key": 1 },
    { "index": 7, "key": 1 }];

array.sort((item1, item2) => {
    return item1.key - item2.key
})

console.log(array);

and get result in hermes:

[{"index":0,"key":1},
{"index":5,"key":1},
{"index":7,"key":1},
{"index":6,"key":1},
{"index":3,"key":1},
{"index":1,"key":1},
{"index":2,"key":1},
{"index":4,"key":2}]

which we will get in chrome:

0: {index: 0, key: 1}
1: {index: 1, key: 1}
2: {index: 2, key: 1}
3: {index: 3, key: 1}
4: {index: 5, key: 1}
5: {index: 6, key: 1}
6: {index: 7, key: 1}
7: {index: 4, key: 2}

The order of the objects has been changed by Array.sort, I am not sure if it is a bug.

1. Array defined in global field and use Array.sort will give different result;

let array = [
    { "index": 0, "key": 1 }, 
    { "index": 1, "key": 1 }, 
    { "index": 2, "key": 1 }, 
    { "index": 3, "key": 1 }, 
    { "index": 4, "key": 2 }, 
    { "index": 5, "key": 1 }, 
    { "index": 6, "key": 1 },
    { "index": 7, "key": 1 }];

class TestSort extends Component {
    render() {
        return (
            <Button title="sort test" onPress={() => {
                array.sort((item1, item2) => {
                    return item1.key - item2.key
                })
                console.log(array);
            }} />
        );
    }
}

first sort result:

//index: 0, 5, 7, 6, 3, 1, 2, 4
[{"index":0,"key":1},
{"index":5,"key":1},
{"index":7,"key":1},
{"index":6,"key":1},
{"index":3,"key":1},
{"index":1,"key":1},
{"index":2,"key":1},
{"index":4,"key":2}]

second sort reslut:

//index: 0, 3, 2, 1, 6, 5, 7, 4
[{"index":0,"key":1},
{"index":3,"key":1},
{"index":2,"key":1},
{"index":1,"key":1},
{"index":6,"key":1},
{"index":5,"key":1},
{"index":7,"key":1},
{"index":4,"key":2}]

Every time I tap the button to get a sort result is different.

In our business code, key may be the weight of the object. The array will be displayed by ListView , because of the uncertain sort results, the display order will be changed and will confuse the user.

Of cause we can fix this by make the comparator more complex, but I don` t think it is a good idea.

BTW, this problem only happen when I define the array in global field, it is fine when I define the array into a function.

[SinLucifer]

There is more information of second problem:

first sort result:

//index: 0, 5, 7, 6, 3, 1, 2, 4

second sort result:

//index: 0, 3, 2, 1, 6, 5, 7, 4

third sort result:

//index: 0, 6, 7, 5, 1, 3, 7, 4

fourth sort reuslt:

//index: 0, 1, 2, 3, 5, 6, 7, 4 

Next time it will go back to first result.

[dulinriley]

I think both of these observed effects are due to the same underlying issue (that was touched upon in the last issue you mentioned https://github.com/facebook/hermes/issues/95):

Our current Array.prototype.sort is __not stable__. A stable sort means that the order of equivalent elements is guaranteed to be preserved.

We have a variety of sorting strategies based on the array:

• If the array has fewer than INSERTION_THRESHOLD (which is currently 6) elements, use insertion sort, which is a stable sort
• Else, use quicksort which is unstable
• If quicksort recurses too many times, use heap sort instead, which is also unstable

If you modify your examples to be 6 elements or fewer, you will notice they will produce the results you expect.

Your second example shows that an unstable sort can produce different results when called multiple times, since it doesn't guarantee that equal keys stay in the same position.

Since tc39 has made a stable Array.prototype.sort now part of the spec (as of https://github.com/tc39/ecma262/pull/1340), we'll need to update our implementation. This is actually a great first issue for someone from the community to dive into, since it's an easily testable change and fairly isolated from more complex parts of the VM.

The only changes that need to be made are in lib/VM/JSLib/Sorting.cpp, and you can use our existing SortModel to handle all the comparator logic.

[tinfoil-knight]

@dulinriley Can I try out this issue?

[dulinriley]

@tinfoil-knight Sure thing!

Here is some advice to get you started:

• First, familiarize yourself with our Building and Running guide to run the existing tests
• Next, choose a stable sorting algorithm to implement. I recommend Timsort, since it's used by both v8 and CPython (see this blog post from v8 on stable sorts)
• Implement the sort in hermes/lib/VM/JSLib/Sorting.cpp. Use the SortModel to do comparisons between keys, as that will do the right logic for exceptions and other miscellaneous JS stuff
• Add some tests for sort stability in the file hermes/test/hermes/array-functions.js
• If test262 has any tests for stable sorts, enable them by removing relevant lines from hermes/utils/testsuite/testsuite_skiplist.py

[dulinriley]

@tinfoil-knight Were you able to try out a stable sort implementation? Do you need any help?

[tinfoil-knight]

@dulinriley No. I tried to read and understand TimSort but I got nowhere. Sorry for not sending out an update. I still have no idea as to how to implement TimSort. I'll update you if I can solve the issue or not.

[tinfoil-knight]

@dulinriley Unfortunately, I don't think I've enough clarity on multiple things to make changes to the codebase. I find Timsort to be very complex. I'm freeing this issue up. I'm really sorry.

[dulinriley]

If Timsort is too difficult, we can use any stable sort for now (such as merge sort) to fix the immediate bug, and come back to optimize it with a more sophisticated algorithm later.

@tinfoil-knight do you want to try with a simpler sorting algorithm instead?

[tinfoil-knight]

No. I don't really know how the library is handling multiple things.

[nairboh]

@dulinriley would it be okay if I took a stab at this?

[dulinriley]

Hi @nairboh, we just found someone internally who was interested in working on it.
We'll let you know how that turns out, and if we'll still need any help with this issue

[CoryWritesCode]

Glad this is being worked on, @dulinriley any word on the internal progress?

[CoryWritesCode]

For those looking for a fix in the meantime, I was able to make use of lodash.sortBy() to get the sorting I needed.

[dulinriley]

We have a fix written up, and going through review. It'll auto-close this issue when it hits Github.

[mikunimaru]

This issue has recurred in version 0.7.2.

[tmikov]

@mikunimaru What issue? Without more information, we cannot help.

[mikunimaru]

Array.prototype.sort is not yet stable sort.

````
let array = [
{ "index": 0, "key": 1 },
{ "index": 1, "key": 1 },
{ "index": 2, "key": 1 },
{ "index": 3, "key": 1 },
{ "index": 4, "key": 2 },
{ "index": 5, "key": 1 },
{ "index": 6, "key": 1 },
{ "index": 7, "key": 1 }];

array.sort((item1, item2) => {
return item1.key - item2.key
})

console.log(array);
````

result (enableHermes: false)
[{"index":0,"key":1},{"index":1,"key":1},{"index":2,"key":1},{"index":3,"key":1},{"index":5,"key":1},{"index":6,"key":1},{"index":7,"key":1},{"index":4,"key":2}]

result (enableHermes: true)
[{"index":0,"key":1},{"index":5,"key":1},{"index":7,"key":1},{"index":6,"key":1},{"index":3,"key":1},{"index":1,"key":1},{"index":2,"key":1},{"index":4,"key":2}]

Since stable sorting is performed only when Hermes is disabled, there is a risk of causing a bug due to this difference in behavior.

Hermes version: 0.7.2
React Native version (if any): 0.64-rc2
Android version (if any): 10
Platform arm64-v8a

[tmikov]

Ah, yes, Hermes does not yet fully support ES2019, which is the first version of the spec requiring a stable sort. I will reopen the issue. We don't have immediate plans to work on this (there are higher priority tasks to finish first), but contributions are welcome.