RE: Array#sort() implementations not interoperable
Andreas Rossberg wrote: On 13 June 2013 23:40, Brendan Eichbren...@mozilla.com wrote: 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. IIUC, current IE versions are not been stable either, so calling it a de-facto bug is a bit of an overstatement. D'oh. Luke? /be That's right - IE9+ does not have a guaranteed stable Array.prototype.sort either. Luke ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Le 14/06/2013 02:37, Mark S. Miller a écrit :
Other things being equal, or even close, I am always in favor of specs
being more deterministic.
Even with this pinned down, we should still allow implementations to
switch among different algorithms based on the size of the array, the
cache hierarchy, or whatever. Because of getters/setters and proxies,
the differences between stable algorithms is still observable.
Maybe there is something that can be made more deterministic about sort.
var a = [yes, no, maybe, I don't know, can you repeat the
question?];
var pa = new Proxy(a, {
get: function(target, name){
console.log('get', name);
return target[name];
},
set: function(target, name, value){
console.log('set', name);
return target[name] = value;
}
})
pa.sort()
In Firefox, I see:
get sort
get length
get 0
get 1
get 2
get 3
get 4
set 0
set 1
set 2
set 3
set 4
Forgetting about the 2 first get, the behavior exposed here is:
1) [[Get]] all elements in order once
2) sort them internally (without touching the array!)
3) a serie of at most a.length [[Put]] calls
And this particular behavior might be standardizable without a loss
(even with a gain), because:
1) a sort algorithm only needs all the array values once at least once
(serie of [[Get]]s) and should probably avoiding touching the array
again since getter or get traps may be costly and return inconsistent
values (so [[Get]] the values at most once)
2) the sorting algorithms is on the values, not on the array (though
with membranes, if the comparator function touches more than the object
identity, it can be observable, but that's not the problem of the sort
algorithm)
3) No sort algorithm requires to rearrange more elements than the number
there is in the array.
In absolute terms, as you say, the sequence of [[Put]] may make the
stable algorithm observable, but I don't think that's a problem.
Standardizing the above behavior has some impact on memory (copying all
values out of the array for the sort algorithm) in theory. In practice,
the [[Get]] and [[Put]] sequences are only observable if there is a
getter or setter on the array or the array is a proxy, so the
implementation is free to choose its memory behavior when there is no
proxy nor getter/setter.
When there is a getter/setter or proxy, the reduction of number of
[[Get]]/[[Put]] calls may be worth the additional memory.
David
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Le 14/06/2013 09:55, Andreas Rossberg a écrit : On 14 June 2013 09:50, David Bruant bruan...@gmail.com wrote: And this particular behavior might be standardizable without a loss (even with a gain), because: 1) a sort algorithm only needs all the array values once at least once (serie of [[Get]]s) and should probably avoiding touching the array again since getter or get traps may be costly and return inconsistent values (so [[Get]] the values at most once) 2) the sorting algorithms is on the values, not on the array (though with membranes, if the comparator function touches more than the object identity, it can be observable, but that's not the problem of the sort algorithm) 3) No sort algorithm requires to rearrange more elements than the number there is in the array. Given that you can still observe implementation-dependent invocations of the comparison function I don't see what is really gained by this. The current non-determinism of sort allows: an implementation-dependent sequence of calls to the [[Get]] , [[Put]], and [[Delete]] internal methods of obj and to SortCompare I'm suggesting to make the [[Get]], [[Put]] and [[Delete]] sequence less implementation-dependent which means at least to bound them to the maximum of what is needed. That's a gain especially in the presence of getter/setter and proxies (where an impl-dependent sequence can lead to more calls than necessary). Trying to make a complex operation like sorting fully deterministic is a fruitless endeavour in an impure language. I didn't suggest to make it fully deterministic. Only to make a bit more predictable the [[Get]]/[[Put]]/[[Delete]] sequence. The sequence of SortCompare calls can remain as implementation-dependent as they want. David ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
On Fri, Jun 14, 2013 at 4:30 AM, Andreas Rossberg rossb...@google.com wrote: On 14 June 2013 10:17, David Bruant bruan...@gmail.com wrote: I'm suggesting to make the [[Get]], [[Put]] and [[Delete]] sequence less implementation-dependent which means at least to bound them to the maximum of what is needed. That's a gain especially in the presence of getter/setter and proxies (where an impl-dependent sequence can lead to more calls than necessary). I don't see much of a use case for an array with getters, let alone sorting a proxy. So the practical gain seems negligible. Sorting an array with a contract [1] seems pretty useful to me. [1] https://github.com/disnet/contracts.js Sam ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
On Fri, Jun 14, 2013 at 9:43 AM, Andreas Rossberg rossb...@google.com wrote: On 14 June 2013 14:11, Sam Tobin-Hochstadt sa...@ccs.neu.edu wrote: On Fri, Jun 14, 2013 at 4:30 AM, Andreas Rossberg rossb...@google.com wrote: I don't see much of a use case for an array with getters, let alone sorting a proxy. So the practical gain seems negligible. Sorting an array with a contract [1] seems pretty useful to me. Perhaps, but useful enough to justify burdening 'sort' with extra complexity and cost? I don't think we should change the specification for `sort` for this use case, just that we should remember that proxies can be useful basically everywhere that any kind of data is useful. Sam ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Andreas Rossberg wrote: On 13 June 2013 23:40, Brendan Eichbren...@mozilla.com wrote: 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. IIUC, current IE versions are not been stable either, so calling it a de-facto bug is a bit of an overstatement. D'oh. Luke? /be If there is agreement that we want stable sort, let's change the spec. I'd be fine with that. /Andreas ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Bumping this old thread since V8 issue #90 (https://code.google.com/p/v8/issues/detail?id=90) has been getting lots of comments lately. It appears that unstable sort, while perfectly spec-compliant, doesn’t match user expectations. It doesn’t help that some browsers/engines _do_ use a stable sorting algorithm, while others don’t — which surprises people and occasionally breaks (badly-written, but hey) code. (See the thread I linked to for examples.) Then, there’s V8, which uses stable sort for small arrays with 10 or fewer elements, but an unstable sorting algorithm for larger arrays, causing even more confusion. Here’s a test case that tests arrays of varying sizes: http://ofb.net/~sethml/is-sort-stable.html The results in different browsers are listed, too. IMHO it would be nice if ES would require a stable sorting algorithm: it would match user expectations, cause fewer issues in existing code, and improve operability in general. What would be the best way to make TC39 consider this change? ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Even if stable sorts don't get required, it would make sense to require that a given implementation is either always stable or always not stable. The current situation with V8 seems likely to result in subtly broken software shipping to the web, where it works in testing environments with small amounts of data and then breaks in the wild only on certain browsers and only if you have a certain amount of data. Yuck. -kg On Thu, Jun 13, 2013 at 6:05 AM, Mathias Bynens math...@qiwi.be wrote: Bumping this old thread since V8 issue #90 ( https://code.google.com/p/v8/issues/detail?id=90) has been getting lots of comments lately. It appears that unstable sort, while perfectly spec-compliant, doesn’t match user expectations. It doesn’t help that some browsers/engines _do_ use a stable sorting algorithm, while others don’t — which surprises people and occasionally breaks (badly-written, but hey) code. (See the thread I linked to for examples.) Then, there’s V8, which uses stable sort for small arrays with 10 or fewer elements, but an unstable sorting algorithm for larger arrays, causing even more confusion. Here’s a test case that tests arrays of varying sizes: http://ofb.net/~sethml/is-sort-stable.html The results in different browsers are listed, too. IMHO it would be nice if ES would require a stable sorting algorithm: it would match user expectations, cause fewer issues in existing code, and improve operability in general. What would be the best way to make TC39 consider this change? ___ 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
Re: Array#sort() implementations not interoperable
I don't really care about the precise language or semantics. 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. 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? -kg On Thu, Jun 13, 2013 at 8:16 AM, Mark S. Miller erig...@google.com wrote: On Thu, Jun 13, 2013 at 7:01 AM, Kevin Gadd kevin.g...@gmail.com wrote: Even if stable sorts don't get required, it would make sense to require that a given implementation is either always stable or always not stable. How would such a requirement differ from the status quo? Doesn't the current v8 impl satisfy it, since a sort that happens to be stable still meets the requirements of an unstable sort? What does always not stable mean? The current situation with V8 seems likely to result in subtly broken software shipping to the web, where it works in testing environments with small amounts of data and then breaks in the wild only on certain browsers and only if you have a certain amount of data. Yuck. -kg On Thu, Jun 13, 2013 at 6:05 AM, Mathias Bynens math...@qiwi.be wrote: Bumping this old thread since V8 issue #90 ( https://code.google.com/p/v8/issues/detail?id=90) has been getting lots of comments lately. It appears that unstable sort, while perfectly spec-compliant, doesn’t match user expectations. It doesn’t help that some browsers/engines _do_ use a stable sorting algorithm, while others don’t — which surprises people and occasionally breaks (badly-written, but hey) code. (See the thread I linked to for examples.) Then, there’s V8, which uses stable sort for small arrays with 10 or fewer elements, but an unstable sorting algorithm for larger arrays, causing even more confusion. Here’s a test case that tests arrays of varying sizes: http://ofb.net/~sethml/is-sort-stable.html The results in different browsers are listed, too. IMHO it would be nice if ES would require a stable sorting algorithm: it would match user expectations, cause fewer issues in existing code, and improve operability in general. What would be the best way to make TC39 consider this change? ___ 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 -- Cheers, --MarkM ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
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 http://es5.github.io/#x15.4.4.11with 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/http://gkoberger.github.io/stacksort/ ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
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
Re: Array#sort() implementations not interoperable
On 6/13/13 at 12:24 PM, oli...@apple.com (Oliver Hunt) wrote: 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. One possibility which will allow implementations to include a more performant sort is to specify two sorts: sort - which is stable unstablestort - which is either an alias for sort or is a faster unstable sort. Cheers - Bill --- Bill Frantz|Web security is like medicine - trying to do good for 408-356-8506 |an evolved body of kludges - Mark Miller www.pwpconsult.com | ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
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
___
Re: Array#sort() implementations not interoperable
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
Re: Array#sort() implementations not interoperable
On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd kevin.g...@gmail.com wrote: I don't understand why you would intentionally sidetrack a discussion about a simple problem with academic details. He brings up a very real point, which is that you can't realistically have an always unstable sort. If I understand you correctly, what you want by an always unstable sort is that you want developers to get bitten in testing due to instability, even for small test cases, so that the issue is caught earlier. The problem with that desire is that there are no sorting algorithms AFAIK that guarantee that they will *always* rearrange equal-sorting elements (i.e., always unstable): even a pure recursive quicksort (no insertion-sort base case) will sometimes not rearrange equal-sorting elements (i.e., seem stable). If I understand your desire correctly, then what you're asking for by always unstable is to require that if an implementation's sorting algorithm *might* rearrange equal-sorting elements, then it must *always* go out of its way to ensure that if equal-sorting elements are present, then it does not preserve their order; I haven't looked in detail at what this would mean from an implementation standpoint, but I'm pretty sure that it is unrealistic. -- Sean Silva ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Always-unstable is trivial: use a stable sort, and the first time you encounter two elements that compare equal, swap them. The problem with that is it isn't necessarily detectably unstable. The two elements you swap might be equal in all ways. To be detectably unstable, you need the sort function to know when two elements that compare equal are not otherwise equal, so you have to pass it a second comparison function, and if you can do that why are you bothering with an unstable sort in the first place? I think I'm confused about the point of always unstable. An alternate interpretation of always unstable is for sort to throw an error anytime it encounters two elements that compare equal. Which is pretty annoyingly useless. You might as well just use a stable sort all the time. On Thu, Jun 13, 2013 at 3:10 PM, Sean Silva sil...@purdue.edu wrote: On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd kevin.g...@gmail.com wrote: I don't understand why you would intentionally sidetrack a discussion about a simple problem with academic details. He brings up a very real point, which is that you can't realistically have an always unstable sort. If I understand you correctly, what you want by an always unstable sort is that you want developers to get bitten in testing due to instability, even for small test cases, so that the issue is caught earlier. The problem with that desire is that there are no sorting algorithms AFAIK that guarantee that they will *always* rearrange equal-sorting elements (i.e., always unstable): even a pure recursive quicksort (no insertion-sort base case) will sometimes not rearrange equal-sorting elements (i.e., seem stable). If I understand your desire correctly, then what you're asking for by always unstable is to require that if an implementation's sorting algorithm *might* rearrange equal-sorting elements, then it must *always* go out of its way to ensure that if equal-sorting elements are present, then it does not preserve their order; I haven't looked in detail at what this would mean from an implementation standpoint, but I'm pretty sure that it is unrealistic. -- Sean Silva ___ 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
Re: Array#sort() implementations not interoperable
On 6/13/13 at 3:53 PM, feli...@gmail.com (felix) wrote: Always-unstable is trivial... Not really. Doing it with a test case that has only one record is hard. It is also hard if the test case has all different records (according to the sort field(s). BTW _ I think having only one sort which is stable is a good solution if performance of sort is not a burning concern. Cheers - Bill --- Bill Frantz| Re: Computer reliability, performance, and security: 408-356-8506 | The guy who *is* wearing a parachute is *not* the www.pwpconsult.com | first to reach the ground. - Terence Kelly ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
I'll state it again since I guess maybe the third time is the charm: When I said 'always stable' or 'always unstable' i was referring to which implementation the browser uses, not what the sort actually does. There's nothing beneficial about the fact that an unstable sort happens to rearrange elements. My point is that explicitly forbidding Array.sort from conditionally switching between sort implementations (or at least from switching between implementations with observable differences) is beneficial to users. Let's not be ridiculous here. -kg On Thu, Jun 13, 2013 at 3:53 PM, felix feli...@gmail.com wrote: Always-unstable is trivial: use a stable sort, and the first time you encounter two elements that compare equal, swap them. The problem with that is it isn't necessarily detectably unstable. The two elements you swap might be equal in all ways. To be detectably unstable, you need the sort function to know when two elements that compare equal are not otherwise equal, so you have to pass it a second comparison function, and if you can do that why are you bothering with an unstable sort in the first place? I think I'm confused about the point of always unstable. An alternate interpretation of always unstable is for sort to throw an error anytime it encounters two elements that compare equal. Which is pretty annoyingly useless. You might as well just use a stable sort all the time. On Thu, Jun 13, 2013 at 3:10 PM, Sean Silva sil...@purdue.edu wrote: On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd kevin.g...@gmail.com wrote: I don't understand why you would intentionally sidetrack a discussion about a simple problem with academic details. He brings up a very real point, which is that you can't realistically have an always unstable sort. If I understand you correctly, what you want by an always unstable sort is that you want developers to get bitten in testing due to instability, even for small test cases, so that the issue is caught earlier. The problem with that desire is that there are no sorting algorithms AFAIK that guarantee that they will *always* rearrange equal-sorting elements (i.e., always unstable): even a pure recursive quicksort (no insertion-sort base case) will sometimes not rearrange equal-sorting elements (i.e., seem stable). If I understand your desire correctly, then what you're asking for by always unstable is to require that if an implementation's sorting algorithm *might* rearrange equal-sorting elements, then it must *always* go out of its way to ensure that if equal-sorting elements are present, then it does not preserve their order; I haven't looked in detail at what this would mean from an implementation standpoint, but I'm pretty sure that it is unrealistic. -- Sean Silva ___ 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
Re: Array#sort() implementations not interoperable
On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd kevin.g...@gmail.com wrote:
I'll state it again since I guess maybe the third time is the charm:
When I said 'always stable' or 'always unstable' i was referring to which
implementation the browser uses, not what the sort actually does. There's
nothing beneficial about the fact that an unstable sort happens to
rearrange elements. My point is that explicitly forbidding Array.sort from
conditionally switching between sort implementations (or at least from
switching between implementations with observable differences) is
beneficial to users. Let's not be ridiculous here.
Switching to other insertion sort for small input sizes is a key part of
getting high performance out of quicksort. The insertion sort is used as
the base case of the recursion, and I wouldn't really consider it
switching between sort implementations. There is no check like the
following:
Array.prototype.sort = function (cmp) {
if (this.length 20) {
doInsertionSort(this);
} else {
doQuicksort(this);
}
};
It's more like:
Array.prototype.sort = function (cmp) {
quicksortRec(this, 0, this.length, cmp);
};
function quicksortRec(arr, begin, end, cmp) {
if (end - begin 20) {
fastBaseCase(arr, begin, end, cmp); // what this does happens to be
stable
return;
}
// ... slow recursive case
}
-- Sean Silva
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
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
Array#sort() implementations not interoperable
Hello everyone,
Reposting, I think my previous attempt got stuck in a filter or something,
because I somehow managed to have the code there in several copies.
I was thinking about sorting algorithms yesterday and I realized that ES
implementations may have different sorting algorithms in use, and decided
to try it out. Now, if you sort strings or numbers, it doesn't matter, but
you may be sorting objects by a key and this is where things get nasty
(think non-deterministic vs deterministic). Here's an example:
function shuffle (arr, depth) {
var tmp = []
var pi = String(Math.PI).substr(2)
var i = 0
var p = 0
while (arr.length) {
i = (i + +pi[p]) % arr.length
p = (p + 1) % pi.length
tmp.push(arr[i])
arr.splice(i, 1)
}
if (!depth) return tmp
return shuffle(tmp, depth - 1)
}
var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'
var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
return {
unique: unique[i],
sorter: sorter.charCodeAt(i)
}
})
var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
return a.sorter - b.sorter
})
console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))
function shuffle (arr, depth) {
/* it's a silly way to shuffle, but at least it's deterministic. */
var tmp = []
var pi = String(Math.PI).substr(2)
var i = 0
var p = 0
while (arr.length) {
i = (i + +pi[p]) % arr.length
p = (p + 1) % pi.length
tmp.push(arr[i])
arr.splice(i, 1)
}
if (!depth) return tmp
return shuffle(tmp, depth - 1)
}
var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'
var arr = Array.apply(null, Array(unique.length)).map(
function (a, i) {
return {
unique: unique[i],
sorter: sorter.charCodeAt(i)
}
})
var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
return a.sorter - b.sorter
})
console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))
In Firefox, you get:
[s, m, q, l, e, b, k, i, f, g, o, j, d, t, n,
c, a, p, h, r, u]
[f, h, a, e, b, g, j, d, c, l, r, q, o, k, t,
n, p, u, i, m, s]
In Chrome, you get:
[s, m, q, l, e, b, k, i, f, g, o, j, d, t, n,
c, a, p, h, r, u]
[f, h, a, g, e, b, j, d, c, l, r, o, q, k, n,
t, p, u, i, m, s]
Real world consequences of this may include:
* A blog where posts are sorted by date (/MM/DD). Different browsers
will show the posts in different order if Array#sort is used to accomplish
this. Not a very severe consequence.
* A spreadsheet application. If it has some order-dependent algorithm to
calculate values, different browsers can give different results for the
same research data.
Now I'm not sure what could be done to this, if anything even should be,
just thought I'd bring it up.
Cheers,
Jussi
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
Jussi Kalliokoski wrote: Hello everyone, Reposting, I think my previous attempt got stuck in a filter or something, because I somehow managed to have the code there in several copies. You have three messages total on this topic at https://mail.mozilla.org/pipermail/es-discuss/2012-December/ I was thinking about sorting algorithms yesterday and I realized that ES implementations may have different sorting algorithms in use, and decided to try it out. Now, if you sort strings or numbers, it doesn't matter, but you may be sorting objects by a key and this is where things get nasty (think non-deterministic vs deterministic). Have you read the language dating from ES3 on Array sort in the spec? In particular Array#sort is not guaranteed to be stable. Perhaps it should be. /be ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
On Mon, Dec 3, 2012 at 8:46 PM, Brendan Eich bren...@mozilla.org wrote: You have three messages total on this topic at https://mail.mozilla.org/**pipermail/es-discuss/2012-**December/https://mail.mozilla.org/pipermail/es-discuss/2012-December/ Oh, sorry about the noise, I should've checked the archives! Have you read the language dating from ES3 on Array sort in the spec? In particular Array#sort is not guaranteed to be stable. Perhaps it should be Yes, I have, that's why I actually thought about trying this out it. I'm not sure if we should change it, but it'd be interesting to have the conversation, to see if there are any real world use cases that may benefit from doing so. Otherwise, I don't see a reason to change it. Don't fix it if it ain't broke. Cheers, Jussi ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
It's abort stability, and I think it's better to keep it un-stable for performance performance. On Mon, Dec 3, 2012 at 10:46 PM, Brendan Eich bren...@mozilla.org wrote: Jussi Kalliokoski wrote: Hello everyone, Reposting, I think my previous attempt got stuck in a filter or something, because I somehow managed to have the code there in several copies. You have three messages total on this topic at https://mail.mozilla.org/**pipermail/es-discuss/2012-**December/https://mail.mozilla.org/pipermail/es-discuss/2012-December/ I was thinking about sorting algorithms yesterday and I realized that ES implementations may have different sorting algorithms in use, and decided to try it out. Now, if you sort strings or numbers, it doesn't matter, but you may be sorting objects by a key and this is where things get nasty (think non-deterministic vs deterministic). Have you read the language dating from ES3 on Array sort in the spec? In particular Array#sort is not guaranteed to be stable. Perhaps it should be. /be __**_ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/**listinfo/es-discusshttps://mail.mozilla.org/listinfo/es-discuss ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Array#sort() implementations not interoperable
I haven't looked into sort algorithms in a while - how much slower are the fastest stable ones than the fastest non-stable ones? I ran into the stability issue recently when implementing a function to interpret HTTP Accept-Language headers [1]. The language tags in these headers can have quality values, but can also omit them, in which case they're assumed to be 1. In normal processing you want to get rid of the quality values and just have an ordered list. To get to the ordered list, you have to sort by quality value, but not change the order of tags with the same quality value, such as all the ones with the default 1.0. A workaround to ensure stability is to consider the original index of each array element in the comparison function, but a sort function that's guaranteed to be stable would be easier to use. Norbert [1] http://tools.ietf.org/html/rfc2616#section-14.4 On Dec 3, 2012, at 11:00 , Fedor Indutny wrote: It's abort stability, and I think it's better to keep it un-stable for performance performance. On Mon, Dec 3, 2012 at 10:46 PM, Brendan Eich bren...@mozilla.org wrote: Jussi Kalliokoski wrote: Hello everyone, Reposting, I think my previous attempt got stuck in a filter or something, because I somehow managed to have the code there in several copies. You have three messages total on this topic at https://mail.mozilla.org/pipermail/es-discuss/2012-December/ I was thinking about sorting algorithms yesterday and I realized that ES implementations may have different sorting algorithms in use, and decided to try it out. Now, if you sort strings or numbers, it doesn't matter, but you may be sorting objects by a key and this is where things get nasty (think non-deterministic vs deterministic). Have you read the language dating from ES3 on Array sort in the spec? In particular Array#sort is not guaranteed to be stable. Perhaps it should be. /be ___ 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
