Array.prototype.sort isn't stable #212

SinLucifer · 2020-04-14T08:17:32Z

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.

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.

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.

The text was updated successfully, but these errors were encountered:

SinLucifer · 2020-04-14T08:26:39Z

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 · 2020-04-14T17:35:58Z

I think both of these observed effects are due to the same underlying issue (that was touched upon in the last issue you mentioned #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 tc39/ecma262#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 · 2020-04-22T17:35:09Z

@dulinriley Can I try out this issue?

dulinriley · 2020-04-22T19:13:09Z

@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 · 2020-07-29T17:29:20Z

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

tinfoil-knight · 2020-07-29T17:34:42Z

@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 · 2020-08-10T18:43:32Z

@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 · 2020-08-10T22:18:48Z

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 · 2020-08-11T10:58:41Z

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

nairboh · 2020-08-11T22:47:36Z

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

dulinriley · 2020-08-12T00:15:25Z

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 · 2020-08-18T20:39:30Z

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

CoryWritesCode · 2020-08-19T16:51:36Z

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 · 2020-08-20T15:39:20Z

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

Summary: The implementation of a stable sort in Hermes had a bug in dealing with comparators that modified the array being sorted. Reopens issue #212 Reviewed By: tmikov Differential Revision: D23437337 fbshipit-source-id: b7a0c26ee7e6b171b857561d628c809581b2ed61

mikunimaru · 2020-12-30T22:46:47Z

This issue has recurred in version 0.7.2.

tmikov · 2020-12-31T01:49:47Z

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

mikunimaru · 2020-12-31T02:58:35Z

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 · 2021-01-01T01:03:16Z

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.

rlemasquerier · 2021-03-01T13:44:02Z

Hello @tmikov, does anyone has any update about this issue ?

I believe it's quiet a major issue, since it prevents us from using the native sort function along with a comparison function as soon as Hermes is enabled, right ?

@mikunimaru Did you find any workaround ?

Would be glad to help but I'm unsure about what needs to be done exactly to make that function stable, any directions ?

Thanks a lot

tmikov · 2021-03-01T16:42:18Z

@rlemasquerier someone needs to implement the stable sort in Hermes. Unfortunately it is not trivial, for a few reasons:

It needs to terminate even if the comparison function is incorrect
It needs to produce the same sequence of calls on all platforms
Implementing JS library functionality in C++ in Hermes requires understanding of implementation details like handles, etc.

The first two points mean that the standard C++ library is out. In practice an existing sort routine can't readily be reused, at least not without heavy customization.

The easiest solution probably is to find a stable sort implementation in JS and polyfill it. In fact, if it is suitably licensed, we can include it in Hermes. Though, of course, there will be a performance penalty.

Prakhar-Srivastava · 2021-04-24T16:22:18Z

Hey guys!
I wanted to ask if the Array.prototype.sort needs to sort an array inplace...?
As in V8 we can do something like:

let x = [8, 4, 9, 1, 0, 4, 3, 6];
const s = Array.prototype.sort.call(x, (a, b) => a - b);

And this would sort the array x inplace while s also has the sorted values of x. I suppose that line 2 copies the elements of x after it is sorted inplace, but just wanted to make sure.

ljharb · 2021-04-24T16:36:17Z

It does not; s and x are the same exact array instance.

vicky1999 · 2021-05-01T06:25:43Z

Hi, Is this issue available? I would like to work on this issue.

tmikov · 2021-05-01T17:03:02Z

Yes, it is available.

vicky1999 · 2021-05-01T17:10:21Z

can I work on it?

Prakhar-Srivastava · 2021-05-01T18:09:48Z

Hey @vicky1999, I'm working on an implementation (working on my machine locally and will fork the repo when I am done and commit the changes there). I'm trying to implement Timsort (bufferless) taking inspiration from std::inplace_stable_sort. You can take this up if you have something better in mind.

vicky1999 · 2021-05-02T08:05:57Z

Hey Guys,
I have implemented the selection sort algorithm. when using selection sort, the sorted array was stable. It was working fine.

Now, I'll try to implement in place merge sort.

chakrihacker · 2021-05-02T08:59:17Z

Just curious, timsort is built on top of insertion sort, then why can't we use stable insertion sort?

Prakhar-Srivastava · 2021-05-02T12:08:17Z

Just curious, timsort is built on top of insertion sort, then why can't we use stable insertion sort?

Hey!
It's based on merge sort and only uses insertion sort for small arrays and since both of these methods are stable, thus timsort is stable too, and in fact even faster than merge sort or insertion sort alone. And Hermes is about doing things efficiently using an algorithm that gives O(n²) in any case kinda criminal to me 😂

andreialecu · 2021-06-24T19:32:35Z

Ran into a quite nasty bug in a third party library after enabling Hermes due to this.

More details in: kylerjensen/react-native-font-faces#289

Was able to fix it in a PR, via the following JS based stable sorting function:

/**
 * The Hermes JS engine does not do a stable sort: https://github.com/facebook/hermes/issues/212
 */
export function stableSort<T>(array: T[], ...compareFns: Array<(a: T, b: T) => number>) {
  return compareFns.reduce((final, compareFn) => {
    return final
      .map((item, index) => ({ item, index }))
      .sort((a, b) => compareFn(a.item, b.item) || a.index - b.index)
      .map(({ item }) => item)
  }, array);
}

You can see the diff in: https://github.com/kylerjensen/react-native-font-faces/pull/290/files

Leaving it here in case it helps someone.

pdpd123 · 2021-07-19T18:24:33Z

I don't understand why is this not a P0 for Hermes team to fix?
This could potentially hang up the whole application if such a fundamental incompatibility. My team burnt 3 days on this because some(ONLY SOME) of out customer has the whole app frozen due to this but we can't repro (Because you need > 6 items..... )

This is a very nasty low level bug. PLease prioritize. Array.sort is very frequently used

kodafb · 2021-10-06T03:59:37Z

Array.prototype.sort is stable as of commit ec424a1

dulinriley added bug Something isn't working good first issue Good for newcomers help wanted Extra attention is needed labels Apr 14, 2020

dulinriley changed the title ~~Another problem about Array.prototype.sort~~ Array.prototype.sort isn't stable Aug 10, 2020

facebook-github-bot closed this as completed in 8a5d054 Aug 21, 2020

tmikov self-assigned this Sep 9, 2020

tmikov reopened this Jan 1, 2021

andreialecu mentioned this issue Jun 24, 2021

Does not work properly with the Hermes JS engine kylerjensen/react-native-font-faces#289

Closed

tmikov removed their assignment Aug 18, 2021

KrisGilicze mentioned this issue Aug 27, 2021

Categories don't work as expected hossein-zare/react-native-dropdown-picker#397

Closed

kodafb closed this as completed Oct 6, 2021

kodafb self-assigned this Oct 6, 2021

DevFuan mentioned this issue Jan 12, 2023

SIGSEGV - Native Crash running RN 0.70.6 (stacktrace included) #886

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Array.prototype.sort isn't stable #212

Array.prototype.sort isn't stable #212

SinLucifer commented Apr 14, 2020

SinLucifer commented Apr 14, 2020

dulinriley commented Apr 14, 2020 •

edited

Loading

tinfoil-knight commented Apr 22, 2020

dulinriley commented Apr 22, 2020 •

edited

Loading

dulinriley commented Jul 29, 2020

tinfoil-knight commented Jul 29, 2020 •

edited

Loading

tinfoil-knight commented Aug 10, 2020

dulinriley commented Aug 10, 2020

tinfoil-knight commented Aug 11, 2020 •

edited

Loading

nairboh commented Aug 11, 2020

dulinriley commented Aug 12, 2020

CoryWritesCode commented Aug 18, 2020

CoryWritesCode commented Aug 19, 2020

dulinriley commented Aug 20, 2020

mikunimaru commented Dec 30, 2020

tmikov commented Dec 31, 2020

mikunimaru commented Dec 31, 2020

tmikov commented Jan 1, 2021

rlemasquerier commented Mar 1, 2021

tmikov commented Mar 1, 2021

Prakhar-Srivastava commented Apr 24, 2021 •

edited

Loading

ljharb commented Apr 24, 2021

vicky1999 commented May 1, 2021

tmikov commented May 1, 2021

vicky1999 commented May 1, 2021

Prakhar-Srivastava commented May 1, 2021 •

edited

Loading

vicky1999 commented May 2, 2021 •

edited

Loading

chakrihacker commented May 2, 2021

Prakhar-Srivastava commented May 2, 2021

andreialecu commented Jun 24, 2021

pdpd123 commented Jul 19, 2021

kodafb commented Oct 6, 2021

Array.prototype.sort isn't stable #212

Array.prototype.sort isn't stable #212

Comments

SinLucifer commented Apr 14, 2020

SinLucifer commented Apr 14, 2020

dulinriley commented Apr 14, 2020 • edited Loading

tinfoil-knight commented Apr 22, 2020

dulinriley commented Apr 22, 2020 • edited Loading

dulinriley commented Jul 29, 2020

tinfoil-knight commented Jul 29, 2020 • edited Loading

tinfoil-knight commented Aug 10, 2020

dulinriley commented Aug 10, 2020

tinfoil-knight commented Aug 11, 2020 • edited Loading

nairboh commented Aug 11, 2020

dulinriley commented Aug 12, 2020

CoryWritesCode commented Aug 18, 2020

CoryWritesCode commented Aug 19, 2020

dulinriley commented Aug 20, 2020

mikunimaru commented Dec 30, 2020

tmikov commented Dec 31, 2020

mikunimaru commented Dec 31, 2020

tmikov commented Jan 1, 2021

rlemasquerier commented Mar 1, 2021

tmikov commented Mar 1, 2021

Prakhar-Srivastava commented Apr 24, 2021 • edited Loading

ljharb commented Apr 24, 2021

vicky1999 commented May 1, 2021

tmikov commented May 1, 2021

vicky1999 commented May 1, 2021

Prakhar-Srivastava commented May 1, 2021 • edited Loading

vicky1999 commented May 2, 2021 • edited Loading

chakrihacker commented May 2, 2021

Prakhar-Srivastava commented May 2, 2021

andreialecu commented Jun 24, 2021

pdpd123 commented Jul 19, 2021

kodafb commented Oct 6, 2021

dulinriley commented Apr 14, 2020 •

edited

Loading

dulinriley commented Apr 22, 2020 •

edited

Loading

tinfoil-knight commented Jul 29, 2020 •

edited

Loading

tinfoil-knight commented Aug 11, 2020 •

edited

Loading

Prakhar-Srivastava commented Apr 24, 2021 •

edited

Loading

Prakhar-Srivastava commented May 1, 2021 •

edited

Loading

vicky1999 commented May 2, 2021 •

edited

Loading