Array#sort() implementations not interoperable

David Bruant bruant.d at gmail.com
Thu Jun 13 14:25:36 PDT 2013


Le 13/06/2013 21:16, Kevin Gadd a écrit :
> 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.
Agreed. The spec on the web. I re-read it the parts I have doubts about 
regularly. I write and read doc because spec prose can be tiresome. I 
just changed MDN to be very clear on the fact that sorts aren't expected 
to be stable. Feel free to contribute to MDN (or WebPlatform at your 
preference, both are wikis) whenever you feel that something should be 
easily found and shouldn't have to be remembered by developers.
Modern development isn't a person against a programming language. The 
web is part of modern development.

> 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
I only cared about the words "stable" and "unstable" which are at the 
heart of the debate. I'm not sure I understand what academic details 
you're referring to and why you're talking about proofs.

A sort being stable is a property on the position of elements which are 
considered equal by the sort algorithm. If people want equal elements to 
not be moved, they should let the comparator believe that they are equal.
This is not about academics or proof. It's about understanding what 
you're doing. Properly understanding the tools at your disposals, the 
abstractions. In essence, it's asking the very skills that are required 
to build any sort of software.

> 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.
My (implicit, sorry about that) point was that there is no need to 
change the sort function. Just for people to read the spec or doc. No 
one is a hero and expected to remember everything, but reading the 
second sentence of the Array.prototype.sort spec seems rather low-cost 
to me.

> 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.
That was a joke obviously :-) But open source, robust, well-tested 
algorithms exist.

Alternate proposal to forcing stable sorts in the spec based on the idea 
that "equal" elements shouldn't be equal:
Have the original index of a value passed to the comparator function. A 
stable sort can then be a few characters away:

     arr.sort(compare)

becomes:

     arr.sort((v1, v2, i1, i2) => { return compare(v1, v2) || i1 > i2; })

Where the compare function considers v1 and v2 to be equal (returns 0, 
only falsy number), original indices are used to decide which is 
greater. This should stabilize the output I think (by fully ordering 
elements either by their value when one is greater than the other and by 
original index when the 2 values are considered equal by the compare 
function)

A simple and optimistic static analysis (no "arguments", no "eval", 3rd 
and 4th arg undeclared, etc.) on the comparator body should leave perf 
roughly intact.

David


More information about the es-discuss mailing list