Infinite loop when sorting

[riso]

Looks like when given a comparator function that's not 'consistent' (as defined here https://www.ecma-international.org/ecma-262/6.0/#sec-array.prototype.sort), Hermes is unable to sort the given array and will instead end up in an infinite loop.

This of course causes apps to become completely unresponsive, and eventually be killed by Android.

The spec says that when a comparator function is not 'consistent' the sort order is implementation-defined. In the case of Hermes though no sort order will ever be produced.

A case that reproduces this issue is for instance this one

[1, 1, 1, 1, 1, 1, 1].sort(function(a, b) { 
  if (a === 1) return -1; 
  else if (b === 1) return 1; 

  return 0;
})

I tried to look at the code to submit a fix but I am unable to understand why Hermes doesn't just use std::sort (as for instance V8 seems to do). There's a comment here

hermes/lib/VM/JSLib/TypedArray.cpp

Line 1313 in e203638

// Use our custom sort routine. We can't use std::sort because it performs

but I'm not sure I understand the meaning of it.

[avp]

Thanks for the bug report - we'll work on fixing this. It appears like there are some untested paths in our sorting functionality that using inconsistent comparators can expose, so the test case is quite useful.

As for the comment in that file, we don't use std::sort because swapping has to use custom logic to be aware of JS semantics - we need to use our GC-aware classes and Handle, which don't play well with requirements for std::sort to function properly along with std::swap. I'll try and clarify the comment as well.

From what I could find, V8 doesn't appear to use std::sort these days - looks like it's a custom TimSort implemented in Torque.

[ljharb]

If you're going to look into sorting, it might be wise to match all browsers and the latest spec on github and implement a stable sorting algorithm.

[tmikov]

We want consistent behavior on all OS-es, so we need a single implementation of sort, meaning it needs to be a custom one. So, that is not entirely trivial, but we will do it... PRs are welcome :-)

[dorthwein]

this still an open issue? Also any suggestions on work arounds here?

[avp]

This is still an open issue, we haven't worked on rewriting sort yet.

The best workaround (which should probably be used even after we fix the infinite loop and implement a stable sort) is to write your comparator to be consistent.

If your comparator is given two values which are equal, it should return 0, and for any non-equal pair of values, it should always return the same result when given those values in the same order. The problem with the given code snippet at the top is that it never actually returns 0, for example.

[andidev]

Just want to mention that my experience was that writing a consistent comparator was too slow. I ended up using lodash sort instead. I am not 100 sure of this because I had some other performance issues as well but just thought I mention it in case someone is having trouble with this it is easier to figure out.

@avp is this sort issue mentioned in the docs? If not it should be, and it shouldn't be very clear. We'll have lost a lot of development time because of this issue and knowing it from start when switching to hermes would have helped.

[tmikov]

@andidev are you saying that writing an inconsistent comparator is actually desired? I find that very surprising. That is not a case that we ever intend to support - the spec says that in the case of an inconsistent comparator the behavior is implementation dependent, though it should always terminate.

We had a bug where the sort would loop infinitely with an inconsistent comparator, which has meanwhile been fixed. The result of such a sort is still unpredictable though.

Also, can you clarify what you think should be added to the documentation?

[andidev]

@tmikov

We had a bug where the sort would loop infinitely with an inconsistent comparator, which has meanwhile been fixed.

We had an inconsistent comparator which lead to the infinite loop bug. We tried to fix it as suggested in this issue by writing a consistent comparator. Then we did not get the infinite loop any more, but the sort was really slow. Then we switched to lodash sort and the sort was fast.

I meant you should document the infinite loop issue, but now that it is fixed there is no need for that anymore.

[tmikov]

@andidev we have never particularly optimized the performance of Array.prototype.sort. Can you give me some details on the case which was slow?

[andidev]

@tmikov
It was when sorting a list of 100-1000 objects. It involved parsing a date with moment and comparing it. Basically it looks like this:

transactions.sort((prev, next) => {
    const prevDate = parseCreationDate(prev);
    const nextDate = parseCreationDate(next);
    if (!prevDate && !nextDate) {
        return 0;
    }
    if (!nextDate) {
        return -1;
    }
    if (!prevDate) {
        return 1;
    }
    if (prevDate.isSame(nextDate)) {
        return 0;
    }
    return prevDate.isBefore(nextDate) ? -1 : 1;
});

function parseCreationDate(transaction) {
    if (!transaction) {
        return;
    }
    if (!transaction.date || !transaction.time) {
        return;
    }
    return moment(`${transaction.date} ${transaction.time}`, 'M/D/YYYY H:mm:ss A');

}

[tmikov]

@andidev the code looks reasonable to me. How did lodash sort improve it? It is very surprising that lodash sort, written in JavaScript, running in the same engine, is faster than the builtin sort. We should definitely fix that :-)

One obvious improvement that could be done to speed things up is to avoid parsing the date every time - that seems expensive. But does lodash sort change that?

[andidev]

@tmikov hmm the lodash solution maybe parses it only once per transaction I guess (depending on how it is written).

const sorted = sortBy(transactions, (transaction) => parseCreationDate(transaction));

Let me try saving the parsed date on object and then sort it and see if the difference is still big.