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> 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> 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 > https://mail.mozilla.org/listinfo/es-discuss
_______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
