Array#sort() implementations not interoperable

Brendan Eich brendan at mozilla.com
Thu Jun 13 14:40:39 PDT 2013


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


More information about the es-discuss mailing list