Opened 9 years ago

Last modified 3 years ago

#11460 new defect

Array.prototype.sort is unstable in some versions of V8, leading to weird behavior inside Dojo

Reported by: Mark Wubben Owned by:
Priority: high Milestone: 1.15
Component: Core Version: 1.5
Keywords: Cc: phiggins, bill
Blocked By: Blocking:

Description

Not sure where this should go, but wanted to raise it anyway.

In V8 Array.prototype.sort isn't defined to be stable, so the following might not work as expected:

["Foo", "Bar"].sort(function(){ return 0; });
// ["Foo", "Bar"] or ["Bar", "Foo"]

It seems fixed in Chrome 6, but not sure if that's on purpose or not. For the relevant V8 bug, see <http://code.google.com/p/v8/issues/detail?id=90>. It's broken in Chrome 5.

A problem scenario I ran into was when using a store for dijit.form.Select, without setting sortByLabel to false. My store also failed to return any label attributes, so the sorting defaulted to returning 0, messing up the expected sort order and selecting a different initial value.

I suppose we could fix this, but it won't be pretty. Still, it's odd browser behavior, according to the V8 bug other browsers do have stable sort, so it seems like something Dojo should resolve.

Change History (9)

comment:1 Changed 9 years ago by James Burke

Not sure what to do with this bug either. Does not seem like something that should be patched in core, as it will be fixed soon enough, and chrome's upgrade percentage is really good.

Would you want a specific change in perhaps the data store used by dijit.form.Select? Not sure what that change would be though, but I am not too familiar with that code.

comment:2 Changed 9 years ago by Eugene Lazutkin

I don't get the idea of sort(function(){ return 0; })??? IMHO, this ticket should be closed as invalid.

But if we have this code in our codebase it should be removed/re-coded. It looks like it happened inadvertently. Probably this is one situation, when we should fail rather than proceed when it happens: sortByLabel is set, yet there is no labels to be sorted.

comment:3 Changed 9 years ago by Mark Wubben

From the V8 ticket:

Small arrays are sorted using a simpler algorithm which happens to be stable. You need a larger array to trigger the quicksort algorithm which is non-stable. <http://code.google.com/p/v8/issues/detail?id=90#c12>

In other words, it's just luck that the problem doesn't occur in Chrome 6.

Eugene, agree, it shouldn't attempt to sort if there's nothing to be sorted. That's harmless in other browsers though, because they have a stable sort (hence returning 0, that's not actually a function but a result).

comment:4 Changed 8 years ago by Chris Mitchell

Owner: anonymous deleted

comment:5 Changed 6 years ago by Kitson Kelly

Cc: bill added

This apparently abandoned ticket still seems valid, as Chrome does not provide a stable sort, but now neither do others. Ideally, parts of the code, like dijit/form/Select that use Array.prototype.sort that need it to be stable would use a stable sort which was available in dojo/_base/array.

comment:6 Changed 6 years ago by bill

This Select example seems more like a user error. He didn't have a label. I admit the behavior is confusing but I don't it's justification to add a stable sort to Select. Maybe a stable sort is still useful somewhere else in Dojo but I'd like to see an example.

comment:7 Changed 3 years ago by dylan

Component: GeneralCore

comment:8 Changed 3 years ago by dylan

Milestone: tbd1.12

Cannot open ticket until #18154 is updated, so trying to batch modify a milestone for now.

comment:9 Changed 3 years ago by dylan

Milestone: 1.131.15

Ticket planning... move current 1.13 tickets out to 1.15 to make it easier to move tickets into the 1.13 milestone.

Note: See TracTickets for help on using tickets.