Array.sort arguments order changed in Node.js 11

Version: 11.1.0
Platform: Darwin hubert.local 18.2.0 Darwin Kernel Version 18.2.0: Fri Oct 5 19:41:49 PDT 2018; root:xnu-4903.221.2~2/RELEASE_X86_64 x86_64 (macOS 10.14.1)
Subsystem:

Hi!

I've noticed a change with Array.sort(). In Node.js 11 order of arguments passed to compare function is reversed. While in most cases it's not a problem, in some cases it causes problems.

In my project I have quite large compare function for .sort(): https://github.com/hudochenkov/postcss-sorting/blob/944da947a628192b54448368c197f586fbbe0c10/lib/sorting.js#L10-L62. It relies on arguments order. It works in Node.js 4—10. I don't expect anyone to figure out what my function does, and I can't simplify it for this issue report yet.

I created a gist, which shows how arguments get to compare function in Node.js 10 and Node.js 11.

$ npx -p node@10 npx https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6

a: 1, b: 2
a: 2, b: 3
a: 3, b: 4
[ 1, 2, 3, 4 ]

$ npx -p node@11 npx https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6

a: 2, b: 1
a: 3, b: 2
a: 4, b: 3
[ 1, 2, 3, 4 ]

Is it a regression or intentional change?

I tried to understand how V8 7.0 changed .sort(), but it's to complex for me :(

It's intentional: #22754 (comment)

@hudochenkov

Hello @hudochenkov, and thank you for the report.
As you mention, this is a change node get by way of a update V8. There was some discussion on the implication of the new algorithm #22754 (comment), but AFAIK this specific issue was reported for node

/CC @nodejs/v8 (esp. @targos @hashseed @mathiasbynens)

@hudochenkov

P.S. @hudochenkov can you provide some data that using your code sorts differently?

@hudochenkov

@hudochenkov stable sort means what if elements in the unsorted array were already in the correct order, they are guaranteed to be in the same order after sorting.

in any case, as long as you always return the correct number for two elements, no matter the order, the engine will properly handle it. if the engine switches the order of the arguments, it will also handle the switched return value.

Thank you for quick replies!

I'll simplify my sorting function as much as possible and will provide examples of how it sorts differently. I'll do it tomorrow.

simpler code:

const declarations = [
  {p: 'mottob', id: 1},
  {p: 'bottom', id: 2},
  {p: 'mottob', id: 3},
  {p: 'mottob', id: 4},
];

if (process.argv[2] === 'anti' ) {
  declarations.sort((b, a) => {
    const ret = sortDeclarations(a, b);
    console.log(`a: %o, b: %o - %d`, a, b, ret);

    return -ret
  });
} else {
  declarations.sort((a, b) => {
    const ret = sortDeclarations(a, b);
    console.log(`a: %o, b: %o - %d`, a, b, ret);

    return ret
  });
}

console.log(declarations);

function sortDeclarations(a, b) {
  if (b.p === 'bottom') {
    return 1;
  }
  return a.id - b.id;
}

Get me:

D:\code\prws>d:\bin\dev\node\node10.9.0.exe t.js
a: { p: 'mottob', id: 1 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 3 } - -2
a: { p: 'mottob', id: 3 }, b: { p: 'mottob', id: 4 } - -1
[ { p: 'bottom', id: 2 },
  { p: 'mottob', id: 1 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

D:\code\prws>d:\bin\dev\node\node11.0.0.exe t.js
a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 1 } - 1
a: { p: 'mottob', id: 3 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'mottob', id: 4 }, b: { p: 'mottob', id: 3 } - 1
[ { p: 'mottob', id: 1 },
  { p: 'bottom', id: 2 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

D:\code\prws>d:\bin\dev\node\node11.0.0.exe t.js anti
a: { p: 'mottob', id: 1 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 3 } - -1
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 3 } - -2
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 4 } - -3
a: { p: 'mottob', id: 3 }, b: { p: 'mottob', id: 4 } - -1
[ { p: 'bottom', id: 2 },
  { p: 'mottob', id: 1 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

Array#sort is returning the correct result, just like before the change in V8. This report is not about a spec correctness issue.
The order in which the elements are compared during sorting (and similarly, how many times the comparison function is called in total) is intentionally unspecified, and depends on the exact implementation. When the V8 implementation changed from QuickSort to TimSort, this order changed. But that’s the thing: this order wildly varies across implementations, and even within the same engine it can change at any point; developers shouldn’t rely on it. This is explicitly called out in https://v8.dev/blog/array-sort#accessors-prototype.

This is not a regression; it’s an implementation detail that shouldn’t be relied upon.

@refack

My above comment was in response to the gist in the OP, i.e. https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6.

@refack, let me respond to your test case now. This program demonstrates something separate from the issue OP reported. The sort callback in this code example is what the spec calls an inconsistent comparison function. For example, assume the following values:

a = { p: 'x', id: 3 }
b = { p: 'bottom', id: 4 }

Now, given the way sortDeclarations is written, we can observe the following:

if you compare a with b, sortDeclarations returns 1
if you compare b with a, sortDeclarations returns 4 - 3 which is… also 1

The result of a sort with an inconsistent comparison function is implementation-defined, and cannot be relied upon. In other words, this too is WAI.

@refack

Thank you for investigation, @refack! And thank you for clarification, @mathiasbynens!

this order wildly varies across implementations, and even within the same engine it can change at any point; developers shouldn’t rely on it.

I guess I was just lucky with my sorting function all these years :) I'm going to rewrite it to be independent of arguments order.

In https://github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/third_party/v8/builtins/array-sort.tq#L362

instead of:
const result: Number = sortCompare(context, userCmpFn, x, y);
do
const result: Number = -sortCompare(context, userCmpFn, y, x);

If I do that, then in Firefox browser it will be with the wrong order, because it uses the normal parameters order.

Take this example to get the admins at the beginning of the list:

const members = [
  { id: 1, isAdmin: true },
  { id: 2, isAdmin: false },
  { id: 3, isAdmin: true },
];

members.sort((a, b) => {
  if (a.isAdmin) return -1;
  if (b.isAdmin) return 1;
  return 0;
});

It will return order them by these IDs in Chrome 3, 1, 2 and by these in Firefox 1, 3, 2

@JJBocanegra

@JJBocanegra That's because your comparison function is inconsistent. It returns -1 for both check(members[0], members[2]) and check(members[2], members[0]). A better comparison would be this:

(a, b) => {
  if (a.isAdmin == b.isAdmin) {
    return a.id - b.id;
  }
  if (a.isAdmin) {
    return -1;
  }
  return 1;
}

@devsnek

@devsnek But that's implying that I want to order by ID, but I do not, I want the initial order to be respected. Consider this:

const members = [
  { id: 3, isAdmin: true },
  { id: 1, isAdmin: false },
  { id: 2, isAdmin: true },
];

I want the final order to be

[
  { id: 3, isAdmin: true },
  { id: 2, isAdmin: true },
  { id: 1, isAdmin: false },
]

And with your suggestion it would fail too.

@JJBocanegra

@JJBocanegra Can you open a new issue at https://github.com/nodejs/help/issues/ instead of discussing this one?

@addaleax

@addaleax sure, but isn't it better to have it here because is directly related to the issue?

@JJBocanegra

@JJBocanegra As @devsnek said, this is a bug in your code. It’s not really related to this issue here.

@addaleax

@addaleax I don't think it's a bug in my code, what If I want to use the initial order as a secondary sorting like is the case? With the arguments inverted is not possible without modifying the initial data adding some kind of index because other browsers use the correct arguments order.

@JJBocanegra

@JJBocanegra you could return 0 instead of return a.id - b.id The point is that if both items have the same isAdmin value, they need to compare consistently by some other metric.

reimplement noncommutative sort

Discovered an issue with sort with node v10 - nodejs/node#24294 - fixed

Add reference to nodejs/node#24294

Fix sorting back compatibility nodejs/node#24294

reimplement noncommutative sort

https://contribution-guttural8.github.io/jai/

Check out the response here

Navigation Menu

Repository navigation

Array.sort arguments order changed in Node.js 11 #24294

32 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Array.sort arguments order changed in Node.js 11 #24294

Description

Activity

richardlau commented on Nov 10, 2018

refack commented on Nov 10, 2018

refack commented on Nov 10, 2018

devsnek commented on Nov 10, 2018

hudochenkov commented on Nov 10, 2018

refack commented on Nov 10, 2018

refack commented on Nov 10, 2018

mathiasbynens commented on Nov 11, 2018

mathiasbynens commented on Nov 11, 2018

hudochenkov commented on Nov 11, 2018

32 remaining items

JJBocanegra commented on Aug 6, 2020

devsnek commented on Aug 6, 2020

JJBocanegra commented on Aug 6, 2020

addaleax commented on Aug 6, 2020

JJBocanegra commented on Aug 6, 2020

addaleax commented on Aug 6, 2020

JJBocanegra commented on Aug 6, 2020

devsnek commented on Aug 6, 2020

fidellucene commented on Oct 10, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions