RE: Array#sort() implementations not interoperable

[Luke Hoban]

>Andreas Rossberg wrote:
>> On 13 June 2013 23:40, Brendan Eich  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

[Brendan Eich]

Andreas Rossberg wrote:

On 13 June 2013 23:40, Brendan Eich  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

[Sam Tobin-Hochstadt]

On Fri, Jun 14, 2013 at 9:43 AM, Andreas Rossberg  wrote:
> On 14 June 2013 14:11, Sam Tobin-Hochstadt  wrote:
>> On Fri, Jun 14, 2013 at 4:30 AM, Andreas Rossberg  
>> 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

[Sam Tobin-Hochstadt]

On Fri, Jun 14, 2013 at 4:30 AM, Andreas Rossberg  wrote:
> On 14 June 2013 10:17, David Bruant  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

[David Bruant]

Le 14/06/2013 09:55, Andreas Rossberg a écrit :

On 14 June 2013 09:50, David Bruant  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

[David Bruant]

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

[Norbert Lindenberg]

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 > > 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 >> > 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

Re: Array#sort() implementations not interoperable

[Sean Silva]

On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd  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

[Kevin Gadd]

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  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  wrote:
> > On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd 
> 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

[Bill Frantz]

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

[felix]

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  wrote:
> On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd  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

[Sean Silva]

On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd  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

[Brendan Eich]

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 > 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 > 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
  

Re: Array#sort() implementations not interoperable

[David Bruant]

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

[Bill Frantz]

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

[Oliver Hunt]

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  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  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-consum

Re: Array#sort() implementations not interoperable

[Kevin Gadd]

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  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

Re: Array#sort() implementations not interoperable

[David Bruant]

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

Re: Array#sort() implementations not interoperable

[Kevin Gadd]

Like I said, I don't care about the language or semantics. If it's such a
big problem for you to overlook the way I phrased it initially, I'll
rephrase it:

If a stable sort is used by the browser to implement Array.sort in some
scenarios, a stable sort should always be used to implement Array.sort.

And like I said, the specific problem is that if users fail to test on data
sets that straddle both sides of whatever arbitrary boundary the JS
implementor picked, they will fail to observe the browser's actual
behavior, and failures will only occur in the wild. The threshold at which
V8 switches between stable/unstable could change at any time if they
decided the performance gains justified potentially breaking a few
applications, and then suddenly more developers would be vulnerable to this.

-kg


On Thu, Jun 13, 2013 at 9:09 AM, Andreas Rossberg wrote:

> On 13 June 2013 17:56, Kevin Gadd  wrote:
> > 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.
>
> It does not change. Stable is a subset of unstable. And vice versa,
> every unstable algorithm returns a stable result for some inputs.
> Mark's point is that requiring "always unstable" has no meaning, no
> matter what language you chose.
>
> /Andreas
>
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: Array#sort() implementations not interoperable

[Kevin Gadd]

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  wrote:

> On Thu, Jun 13, 2013 at 7:01 AM, Kevin Gadd  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  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

[Kevin Gadd]

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  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

[Mathias Bynens]

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

[Norbert Lindenberg]

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  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

Re: Array#sort() implementations not interoperable

[Fedor Indutny]

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  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

Re: Array#sort() implementations not interoperable

[Jussi Kalliokoski]

On Mon, Dec 3, 2012 at 8:46 PM, Brendan Eich  wrote:

> You have three messages total on this topic at
>
> 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

[Brendan Eich]

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