New issue
Advanced search Search tips

Issue 900651 link

Starred by 1 user

Issue metadata

Status: WontFix
Owner:
Closed: Nov 2
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: Linux , Windows
Pri: 1
Type: Bug-Regression



Sign in to add a comment

The sort() method returns different results

Reported by 1piotrma...@gmail.com, Oct 31

Issue description

UserAgent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3538.77 Safari/537.36

Steps to reproduce the problem:
Execute the following code in dev tools console:

let arr = [{name: 'item A', index: 1},{name:'item B', index: 1}];
console.log(arr.sort((a,b) => a.index < b.index ? 1 : -1).map(i => i.name));
console.log(arr.sort((a,b) => a.index < b.index ? 1 : -1).map(i => i.name));
console.log(arr.sort((a,b) => a.index < b.index ? 1 : -1).map(i => i.name));
console.log(arr.sort((a,b) => a.index < b.index ? 1 : -1).map(i => i.name));

What is the expected behavior?
Above code SHOULD return the following output:

["item A", "item B"]
["item A", "item B"]
["item A", "item B"]
["item A", "item B"]

What went wrong?
Actually above code returns the following output:

["item B", "item A"]
["item A", "item B"]
["item B", "item A"]
["item A", "item B"]

This is wrong, sorting the same array using the same compare function returns different results. 

Did this work before? Yes Chrome 69

Chrome version: 70.0.3538.77  Channel: stable
OS Version: 10.0
Flash Version:
 
Your comparison function is non-deterministic as it produces different results for identical input elements compared in different order. In other words it says A>B && B>A, which is impossible. The correct code would have to return 0 here. Personally, I consider it a bug in your code that depended on an implementation quirk of the sort function in older versions of Chrome and V8, but let's see what Chromium developers think.

Bisected to r585462 "Update V8 to version 7.0.251"
Suspecting 9e48a24fd9b88712e4ec591c8b1fd40dc6381f18
"Reland "[array] Move Array.p.sort to Torque and use TimSort instead of QuickSort""
Landed in 70.0.3531.0
Ok, so please try the following example:

let arr = [{name: 'item A', index: 1},{name:'item B', index: 1}];
console.log(arr.sort((a,b) => -1).map(i => i.name));
console.log(arr.sort((a,b) => -1).map(i => i.name));
console.log(arr.sort((a,b) => -1).map(i => i.name));
console.log(arr.sort((a,b) => -1).map(i => i.name));

The result is the same. Is it still comparision function's fault?
Your new function has the same bug, it behaves exactly the same as the old one for identical arguments.
I don't know how else to explain (try asking on StackOverflow) except for showing the correct comparison function for a numeric "index" field:

  (a,b) => b.index - a.index
Cc: szuend@google.com viswa.karala@chromium.org
Labels: -Pri-2 RegressedIn-70 Triaged-ET ReleaseBlock-Stable Target-70 Target-71 Target-72 M-71 M-70 FoundIn-71 FoundIn-70 FoundIn-72 Needs-Triage-M70 hasbisect OS-Linux Pri-1
Owner: cbruni@chromium.org
Status: Assigned (was: Unconfirmed)
Able to reproduce the issue on reported chrome version 70.0.3538.77 and on latest chrome# 72.0.3597.0 using Windows-10, Mac 10.12.6 & Ubuntu 17.10, hence providing Bisect Info

Bisect Info:
================
Good build: 70.0.3530.0
Bad build: 70.0.3531.0

On performing per-revision bisect facing error, hence providing below change log from chromium bisect
You are probably looking for a change made after 585456 (known good), but no later than 585470 (first known bad).
Change Log: https://chromium.googlesource.com/chromium/src/+log/ac0405676146ce76211b297659aecd91714564f5..548ac6ffdaac420fbc90a96f09104ef401bc2c38
Suspecting: https://chromium.googlesource.com/v8/v8/+/9e48a24fd9b88712e4ec591c8b1fd40dc6381f18 from above change log
Change-Id: I7cd4287e4562d84ab7c79c58ae30780630f976de
Reviewed-on: https://chromium-review.googlesource.com/1151199

Note: As the author last visit is more than 30 days, hence assigning it to reviewer(Camillo Bruni)

@Camillo Bruni: Please confirm the issue and help in re-assigning if it is not related to your change.
Adding ReleaseBlock-Stable for M-71, feel free to remove it if not applicable.

Thanks!
Status: WontFix (was: Assigned)
woxxom@ described the problem correctly.

If the compare function does not return 0 for equal elements, the sorting algorithm performs a swap each time it sees these two equal elements.

This might seem confusing, but it's the only sane way the sorting algorithm can behave.
Ok, so, could you explain me why it was working correctly in previous Chrome versions? And why it performs a swap only when the return value is -1, not 1 also?
We've change the sorting algorithm which performs compare and swaps in different order now.

Check https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort the rest depends on the implementation of the sorting algo, we're reling on TimSort https://en.wikipedia.org/wiki/Timsort.

Sign in to add a comment