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.g...@gmail.com >> <mailto:kevin.g...@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 <bruan...@gmail.com >>> <mailto:bruan...@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@mozilla.org <mailto:es-discuss@mozilla.org> >>> https://mail.mozilla.org/listinfo/es-discuss >> >> _______________________________________________ >> es-discuss mailing list >> es-discuss@mozilla.org >> https://mail.mozilla.org/listinfo/es-discuss > _______________________________________________ > es-discuss mailing list > es-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es-discuss _______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
