Array#sort() implementations not interoperable

Norbert Lindenberg ecmascript at lindenbergsoftware.com
Thu Jun 13 17:26:57 PDT 2013


Looking at the discussion on
https://code.google.com/p/v8/issues/detail?id=90
it seems the V8 team is waiting for TC39 to tell them that they have to switch to a stable algorithm.

An agenda item for the next meeting?

Norbert


On Jun 13, 2013, at 14:40 , Brendan Eich wrote:

> Just confirming: In ES1 days, the MS guy (Shon K.) suggested stability but we all agreed not to require it, but I believe he implemented it. This created a de-facto standard and SpiderMonkey and JSC matched.
> 
> I think V8 has a de-facto bug to fix. I'm ok with requiring stability as a normative property of Array.prototype.sort given such a V8 bugfix.
> 
> I don't yet see enough value in adding an unstableSort (to Bill F's point).
> 
> /be
> 
> Oliver Hunt wrote:
>> JSC switched to an always stable sort years ago due to compatibility problems with content targeting firefox and IE depending on it.
>> 
>> We also had issues with inconsistent comparison functions, but i can't recall exactly what the reasoning behind it was (nor the exact behavior we felt was necessary), but we ended up with an AVL tree being involved, so we may be attempting to only compare two elements with each other once.  Unfortunately this code is a little bit gnarly for me to read and understand today :-(
>> 
>> I believe that the spec should mandate a stable sort, but i'm not sure just how far we can go in trying to standardize exact behavior of the sort without tying implementations to a single implementation for all time.
>> 
>> --Oliver
>> 
>> 
>> On Jun 13, 2013, at 12:16 PM, Kevin Gadd <kevin.gadd at gmail.com <mailto:kevin.gadd at gmail.com>> wrote:
>> 
>>> I have read the ES specs multiple times, and still accidentally shipped an application that was broken by Array.sort's default behavior in the wild. I know other people who have had the same issues, and people who have read the spec and don't happen to have particular quirks defined in the spec memorized. People are not great at remembering spec details. Simply demanding that all JS developers in the wild read the spec will *not* address these issues. Modern application development occurs on multiple platforms, in multiple languages, using multiple libraries. No matter how many times the spec is read, if the developer is regularly writing and thinking in different languages using different primitives, the primitives that defy trends and act in unexpected ways will always be a stumbling block. The v8 issue and related issue reports against Underscore both serve to demonstrate this.
>>> 
>>> I don't understand why you would intentionally sidetrack a discussion about a simple problem with academic details. Yes, if your goal is to write proofs or rigorously demonstrate that your software is correct all the time, the exact definition of different sort algorithms and terminology really does matter, and yes, it is valuable for people to read the spec. But that is not remotely relevant to the original post in this discussion thread and was not suggested by my replies either. This thread *should* be about whether the ES spec can protect developers from subtle mistakes and errors by changing the specification of Array.sort. Is the point trying to be made here that it is impossible for the spec to clearly communicate that implementations should not do what V8 does, and this communication is impossible because of the academic definition? You haven't even once addressed the original core question of whether it would be possible to switch Array.sort to being stable, and what the obstacles to that would be.
>>> 
>>> There are examples out there in the wild of how difficult it is to write a performant sort in JS from scratch; you need only look at the Bugzilla bug about self-hosting Array.sort in Spidermonkey. Or we can look at the number of *broken* binary search implementations out in the wild caused by people copying from broken algorithms in textbooks that behave incorrectly in boundary cases. Please, for the love of $deity, do not just tell developers to type a query into stackoverflow and grab the top result. I don't necessarily think that it is automatically the right choice to say 'do it yourself' for a problem like this, though it could easily be correct in this specific case, since Underscore ships a stable sort function. Most developers probably use jQuery and/or Underscore already to make up for the small number of useful primitives in the JS standard library, and that's fine.
>>> 
>>> -kg
>>> 
>>> 
>>> On Thu, Jun 13, 2013 at 9:50 AM, David Bruant <bruant.d at gmail.com <mailto:bruant.d at gmail.com>> wrote:
>>> 
>>>    Le 13/06/2013 17:56, Kevin Gadd a écrit :
>>> 
>>>        I don't really care about the precise language or semantics.
>>> 
>>>    Maybe you should. In my opinion, that would certainly help having
>>>    your case better understood and heard.
>>> 
>>> 
>>>        I just don't want applications to break in the wild because
>>>        an Array.sort implementation's stability changes based on the
>>>        number of elements.
>>> 
>>>    A stable sort is just a particular case of an unstable sort. So,
>>>    if a sort is "sometimes unstable", then it is "always unstable".
>>>    The impression of a stability for some cases is just a distraction.
>>> 
>>>    It's also not like if "sort" was confusing like isNaN. "sort"
>>>    does its job.
>>> 
>>> 
>>>        That feels like a much easier problem to solve than the
>>>        problem of some browsers being unstable and some being
>>>        stable. This is absolutely the sort of thing that would bite
>>>        me as a JS dev and will bite every person who uses my
>>>        compiler to convert an application. Why would they test with
>>>        both small and large element counts?
>>> 
>>>    They can also read the spec and learn they can't rely on sort
>>>    stability (second sentence of ES5 - 15.4.4.11 !). Specs aren't
>>>    just for implementors. As a web developer, I feel it's a
>>>    time-consuming yet very healthy exercise to read specs to avoid
>>>    pain later down the road. I wouldn't have said that for ES3, but
>>>    ES5 is decently developer friendly, especially
>>>    http://es5.github.io/#x15.4.4.11 with links and all that.
>>> 
>>>    If people are unsatisfied with the language sort function, maybe
>>>    they should pick a different sort function, implement one that
>>>    fits their need, why not.
>>>    They can even monkeypatch array#sort!
>>>    Why not try a stackoverflow sort [1][2]? Try with "stable sort" ;-)
>>> 
>>>    David
>>> 
>>>    [1] http://xkcd.com/1185/
>>>    [2] http://gkoberger.github.io/stacksort/
>>> 
>>> 
>>> _______________________________________________
>>> es-discuss mailing list
>>> es-discuss at mozilla.org <mailto:es-discuss at mozilla.org>
>>> https://mail.mozilla.org/listinfo/es-discuss
>> 
>> _______________________________________________
>> es-discuss mailing list
>> es-discuss at mozilla.org
>> https://mail.mozilla.org/listinfo/es-discuss
> _______________________________________________
> es-discuss mailing list
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss



More information about the es-discuss mailing list