Everything

php

Home » Project » Newsgroups » php.internals » Make sorting stable »

Make sorting stable

php.internals

Nikita Popov

6 years ago

Hi internals,

Sorting function in PHP currently do not guarantee stability, which means
that the result order of elements that compare equal is not defined.

To achieve a stable sort, you need to do something like this (untested):

$arrayAndPos = [];
$pos = 0;
foreach ($array as $value) {
$arrayAndPos[] = [$value, $pos++];
}
usort($arrayAndPos, function($a, $b) use($compare) {
return $compare($a[0], $b[0]) ?: $a[1] <=> $b[1];
});
$array = [];
foreach ($arrayAndPos as $elem) {
$array[] = $elem[0];
}

This is both cumbersome and very inefficient. Those temporary arrays
significantly increase memory usage, and hurt performance of the sort.

I believe that it is important for us to provide a stable sorting option in
the standard library. We could introduce a separate stable function(s) for
this purpose, but I believe we can just as well make all our existing sorts
stable.

This does not require actually switching sorting algorithms to something
like Timsort. We can essentially do the same as the above PHP code, just
much more efficiently. Due to certain implementation details, we can do
this without memory usage increase, and with minimal performance impact.
I've put https://github.com/php/php-src/pull/5236 up as a prototype.

The only issue I ran into is that this change has a negative impact on code
using illegal comparison callbacks like this:

usort($array, function($a, $b) {
return $a > $b;
});

The return value of the sorting callback should be $a <=> $b, but using $a

> $b also works right now, due to implementation details of the sorting

implementation (only the outcome of $compare($a, $b) > 0 ends up being used
by the sort).

This kind of incorrect code will break under the proposed implementation,
because we will now compare by original position if the comparison function
reports equality. Because the comparator reports equality inconsistently
(it says that $a == $b, but $b != $a), the sort results are also
inconsistent.

What do people think about this? Is there interest in making sorting
stable? Is it okay to break code using illegal comparison callbacks?

Regards,
Nikita

Sara Golemon

6 years ago

On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com> wrote:

> The only issue I ran into is that this change has a negative impact on code
> using illegal comparison callbacks like this:
>
> usort($array, function($a, $b) {
>     return $a > $b;
> });
>
> Let's define what "negative impact" means in this regard.  Is it that one

still winds up with an essentially sorted array, but hitherto "stable
appering" output is now stable in a different way?  Or is the result
actually just NOT sorted in a way that a reasonable user would consider
correct (e.g. 5 sorted before "3")?

If it's the former, then I'm generally disinclined to be concerned about
the breakage.  We never made a promise about comparison equality
resolution, so moving to making a promise about it isn't violating anything.

> This kind of incorrect code will break under the proposed implementation,
> because we will now compare by original position if the comparison function
> reports equality. Because the comparator reports equality inconsistently
> (it says that $a == $b, but $b != $a), the sort results are also
> inconsistent.
>
> I read this user-space comparator as saying that values are never equal.

Sometimes $a > $b and $b > $a are both true, which is terrible.  But if
they never report equality, then position sorting should never come into
play.

> What do people think about this? Is there interest in making sorting
> stable? Is it okay to break code using illegal comparison callbacks?
>
> Generally +1, just curious about what breaks and how.

-Sara

Nikita Popov

6 years ago

On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:

> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com> wrote:
>
>> The only issue I ran into is that this change has a negative impact on
>> code
>> using illegal comparison callbacks like this:
>>
>> usort($array, function($a, $b) {
>>     return $a > $b;
>> });
>>
>> Let's define what "negative impact" means in this regard.  Is it that one
> still winds up with an essentially sorted array, but hitherto "stable
> appering" output is now stable in a different way?  Or is the result
> actually just NOT sorted in a way that a reasonable user would consider
> correct (e.g. 5 sorted before "3")?
>

"Negative impact" is PR speak for "completely broken" ;) Yes, it could sort
5 before 3. The comparison function becomes completely ill-defined and you
get Garbage-In-Garbage-Out.

If we are concerned about this (I'm not sure we should be, but I've at
least seen people be interested about this peculiar behavior:
https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers),
there's two things we can do:

1. As Tyson suggests, we can throw a warning if a boolean is returned from
the comparison callback (probably with a check to only throw it once per
sort), to make it obvious what the cause is.

2. We can fix this transparently by doing something like this internally:

$result = $compare($a, $b);
if ($result !== false) {
return (int) $result; // Normal behavior
}

// Bad comparison function, try the reverse order as well
return -$compare($b, $a);

That is, we will recover the full three-way comparison result from the
"greater than" result, by checking for both $a > $b and $b > $a.

> If it's the former, then I'm generally disinclined to be concerned about
> the breakage.  We never made a promise about comparison equality
> resolution, so moving to making a promise about it isn't violating anything.
>
>
>
>> This kind of incorrect code will break under the proposed implementation,
>> because we will now compare by original position if the comparison
>> function
>> reports equality. Because the comparator reports equality inconsistently
>> (it says that $a == $b, but $b != $a), the sort results are also
>> inconsistent.
>>
>> I read this user-space comparator as saying that values are never equal.
> Sometimes $a > $b and $b > $a are both true, which is terrible.  But if
> they never report equality, then position sorting should never come into
> play.
>

That's not what this comparator does: The result gets interpreted as the
usual -1/0/1 three-way comparison result, so "return $a > $b" will report
true == 1 == greater-than if $a is greater than $b (this is correct!) and
will report false == 0 == equals if $a equals $b (this is also correct) or
if $a is smaller than $b (this is wrong).

This ends up working, because the sort implementation happened to never
make a distinction between 0 and -1 return value. Now it does, and thus
results in an incorrect result.

Nikita

Sara Golemon

6 years ago

On Wed, Mar 4, 2020 at 12:12 PM Nikita Popov <nikita.ppv@gmail.com> wrote:

> On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:
>
>> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com>
>> wrote:
>>
>>> The only issue I ran into is that this change has a negative impact on
>>> code
>>> using illegal comparison callbacks like this:
>>>
>>> usort($array, function($a, $b) {
>>>     return $a > $b;
>>> });
>>>
>>> Let's define what "negative impact" means in this regard.  Is it that
>> one still winds up with an essentially sorted array, but hitherto "stable
>> appering" output is now stable in a different way?  Or is the result
>> actually just NOT sorted in a way that a reasonable user would consider
>> correct (e.g. 5 sorted before "3")?
>>
>
> "Negative impact" is PR speak for "completely broken" ;) Yes, it could
> sort 5 before 3. The comparison function becomes completely ill-defined and
> you get Garbage-In-Garbage-Out.
>
> Roger that, thanks for explaining. 👍

> If we are concerned about this (I'm not sure we should be, but I've at
> least seen people be interested about this peculiar behavior:
> https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers),
> there's two things we can do:
>
> 1. As Tyson suggests, we can throw a warning if a boolean is returned from
> the comparison callback (probably with a check to only throw it once per
> sort), to make it obvious what the cause is.
>
> 2. We can fix this transparently by doing something like this internally:
>
> $result = $compare($a, $b);
> if ($result !== false) {
>     return (int) $result; // Normal behavior
> }
>
> // Bad comparison function, try the reverse order as well
> return -$compare($b, $a);
>
>

¿Por que no los dos?

Fixing broken stuff transparently for a smooth upgrade path PLUS letting
people know they're doing it wrong seems win-win and low cost.

-Sara

Larry Garfield

6 years ago

On Wed, Mar 4, 2020, at 12:35 PM, Sara Golemon wrote:

> On Wed, Mar 4, 2020 at 12:12 PM Nikita Popov <nikita.ppv@gmail.com> wrote:
>
> > On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:
> >
> >> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com>
> >> wrote:
> >>
> >>> The only issue I ran into is that this change has a negative impact on
> >>> code
> >>> using illegal comparison callbacks like this:
> >>>
> >>> usort($array, function($a, $b) {
> >>>     return $a > $b;
> >>> });
> >>>
> >>> Let's define what "negative impact" means in this regard.  Is it that
> >> one still winds up with an essentially sorted array, but hitherto "stable
> >> appering" output is now stable in a different way?  Or is the result
> >> actually just NOT sorted in a way that a reasonable user would consider
> >> correct (e.g. 5 sorted before "3")?
> >>
> >
> > "Negative impact" is PR speak for "completely broken" ;) Yes, it could
> > sort 5 before 3. The comparison function becomes completely ill-defined and
> > you get Garbage-In-Garbage-Out.
> >
> > Roger that, thanks for explaining. 👍
>
>
> > If we are concerned about this (I'm not sure we should be, but I've at
> > least seen people be interested about this peculiar behavior:
> > https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers),
> > there's two things we can do:
> >
> > 1. As Tyson suggests, we can throw a warning if a boolean is returned from
> > the comparison callback (probably with a check to only throw it once per
> > sort), to make it obvious what the cause is.
> >
> > 2. We can fix this transparently by doing something like this internally:
> >
> > $result = $compare($a, $b);
> > if ($result !== false) {
> >     return (int) $result; // Normal behavior
> > }
> >
> > // Bad comparison function, try the reverse order as well
> > return -$compare($b, $a);
> >
> >
> ¿Por que no los dos?
>
> Fixing broken stuff transparently for a smooth upgrade path PLUS letting
> people know they're doing it wrong seems win-win and low cost.
>
> -Sara

I concur.  If a comparison function returns a non-legal value:

1) Fold it to a legal value. if feasible.
2) Raise a notice/warning, maybe deprecated? that tells them they're Doing It Wrong(tm)
3) Sometime in the future turn that notice/warning into a hard error.

If I'm understanding the definition of stable here, it means that if two values evaluate to equal they will always end up in the same order in the output that they were in the input, yes?  So (trivial example):

$a = ["3", 2, 3, 5];

Sorts to:

[2, "3", 3, 5];

always, whereas right now it may sort to that or to [2, 3, "3", 5], somewhat randomly.  Am I understanding correctly?

--Larry Garfield

Andreas Hennings

6 years ago

Note that a comparison callback can also be broken in other ways:
- It could contain a loop, e.g. 'a' < 'b', 'b' < 'c', 'c' < 'a'.
- It could have alternating return values in subsequent calls with the same
arguments.

This kind of misbehavior cannot be easily detected.
The best we can do is make sure these kinds of comparison functions do not
cause infinite loops.

This said: Yes, stable sort out of the box would be a welcome feature.

On Wed, 4 Mar 2020 at 20:49, Larry Garfield <larry@garfieldtech.com> wrote:

Andrew Faulds

6 years ago

Hi,

Larry Garfield wrote:

> If I'm understanding the definition of stable here, it means that if two values evaluate to equal they will always end up in the same order in the output that they were in the input, yes?  So (trivial example):
>
> $a = ["3", 2, 3, 5];
>
> Sorts to:
>
> [2, "3", 3, 5];
>
> always, whereas right now it may sort to that or to [2, 3, "3", 5], somewhat randomly.  Am I understanding correctly?

(That is _my_ understanding, though I'd take Nikita's word for it rather
than mine.)

I think you indirectly point out a good reason to have a stable sorting
algorithm for PHP: PHP's weird type-juggling equality rules mean several
kinds of values that are not really (===) equal will compare equal (==)
so far as sorting cares, which probably means messy results sometimes
when paired with an unstable sort?

Thanks,
Andrea

Nikita Popov

6 years ago

On Wed, Mar 4, 2020 at 8:49 PM Larry Garfield <larry@garfieldtech.com>
wrote:

> On Wed, Mar 4, 2020, at 12:35 PM, Sara Golemon wrote:
> > On Wed, Mar 4, 2020 at 12:12 PM Nikita Popov <nikita.ppv@gmail.com>
> wrote:
> >
> > > On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:
> > >
> > >> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com>
> > >> wrote:
> > >>
> > >>> The only issue I ran into is that this change has a negative impact
> on
> > >>> code
> > >>> using illegal comparison callbacks like this:
> > >>>
> > >>> usort($array, function($a, $b) {
> > >>>     return $a > $b;
> > >>> });
> > >>>
> > >>> Let's define what "negative impact" means in this regard.  Is it that
> > >> one still winds up with an essentially sorted array, but hitherto
> "stable
> > >> appering" output is now stable in a different way?  Or is the result
> > >> actually just NOT sorted in a way that a reasonable user would
> consider
> > >> correct (e.g. 5 sorted before "3")?
> > >>
> > >
> > > "Negative impact" is PR speak for "completely broken" ;) Yes, it could
> > > sort 5 before 3. The comparison function becomes completely
> ill-defined and
> > > you get Garbage-In-Garbage-Out.
> > >
> > > Roger that, thanks for explaining. 👍
> >
> >
> > > If we are concerned about this (I'm not sure we should be, but I've at
> > > least seen people be interested about this peculiar behavior:
> > >
> https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers
> ),
> > > there's two things we can do:
> > >
> > > 1. As Tyson suggests, we can throw a warning if a boolean is returned
> from
> > > the comparison callback (probably with a check to only throw it once
> per
> > > sort), to make it obvious what the cause is.
> > >
> > > 2. We can fix this transparently by doing something like this
> internally:
> > >
> > > $result = $compare($a, $b);
> > > if ($result !== false) {
> > >     return (int) $result; // Normal behavior
> > > }
> > >
> > > // Bad comparison function, try the reverse order as well
> > > return -$compare($b, $a);
> > >
> > >
> > ¿Por que no los dos?
> >
> > Fixing broken stuff transparently for a smooth upgrade path PLUS letting
> > people know they're doing it wrong seems win-win and low cost.
> >
> > -Sara
>
>
> I concur.  If a comparison function returns a non-legal value:
>
> 1) Fold it to a legal value. if feasible.
> 2) Raise a notice/warning, maybe deprecated? that tells them they're Doing
> It Wrong(tm)
> 3) Sometime in the future turn that notice/warning into a hard error.
>
> If I'm understanding the definition of stable here, it means that if two
> values evaluate to equal they will always end up in the same order in the
> output that they were in the input, yes?  So (trivial example):
>
> $a = ["3", 2, 3, 5];
>
> Sorts to:
>
> [2, "3", 3, 5];
>
> always, whereas right now it may sort to that or to [2, 3, "3", 5],
> somewhat randomly.  Am I understanding correctly?
>

That's right. Of course, this is not a particular useful case :) Typically,
stable sorting is useful if you are sorting only by some "part" of the
value. The most common case is sorting objects by one field:

usort($users, function($user1, $user2) {
return $user1->age <=> $user2->age;
});

With stable sorting, this will sort users by age, but otherwise leave the
order of the objects alone. For example, if $users was originally sorted by
ID, then the objects will now be sorted by age first and ID second. With
unstable sorting, the order within one age bracket would be undefined.

Another example is asort(), which sorts by value but preserves keys.

$array = [
'foo' => 1,
'bar' => 1,
'oof' => 0,
'rab' => 0,
];
asort($array);

With stable sorting, this will always result in

$array = [
'oof' => 0,
'rab' => 0,
'foo' => 1,
'bar' => 1,
];

while with unstable sorting, the order of keys for a given value is
undefined.

Because stable sorting is the more useful default choice, most high-level
languages nowadays default to stable sorting (Java and Python have been
stable for a long time, JavaScript mandates stability since recently --
Ruby is a counter-example that uses unstable sorting.)  Low-level languages
tend to expose both stable and unstable sorts.

Regards,
Nikita

Nikita Popov

6 years ago

On Wed, Mar 4, 2020 at 7:35 PM Sara Golemon <pollita@php.net> wrote:

> On Wed, Mar 4, 2020 at 12:12 PM Nikita Popov <nikita.ppv@gmail.com> wrote:
>
>> On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:
>>
>>> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com>
>>> wrote:
>>>
>>>> The only issue I ran into is that this change has a negative impact on
>>>> code
>>>> using illegal comparison callbacks like this:
>>>>
>>>> usort($array, function($a, $b) {
>>>>     return $a > $b;
>>>> });
>>>>
>>>> Let's define what "negative impact" means in this regard.  Is it that
>>> one still winds up with an essentially sorted array, but hitherto "stable
>>> appering" output is now stable in a different way?  Or is the result
>>> actually just NOT sorted in a way that a reasonable user would consider
>>> correct (e.g. 5 sorted before "3")?
>>>
>>
>> "Negative impact" is PR speak for "completely broken" ;) Yes, it could
>> sort 5 before 3. The comparison function becomes completely ill-defined and
>> you get Garbage-In-Garbage-Out.
>>
>> Roger that, thanks for explaining. 👍
>
>
>> If we are concerned about this (I'm not sure we should be, but I've at
>> least seen people be interested about this peculiar behavior:
>> https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers),
>> there's two things we can do:
>>
>> 1. As Tyson suggests, we can throw a warning if a boolean is returned
>> from the comparison callback (probably with a check to only throw it once
>> per sort), to make it obvious what the cause is.
>>
>> 2. We can fix this transparently by doing something like this internally:
>>
>> $result = $compare($a, $b);
>> if ($result !== false) {
>>     return (int) $result; // Normal behavior
>> }
>>
>> // Bad comparison function, try the reverse order as well
>> return -$compare($b, $a);
>>
>>
> ¿Por que no los dos?
>
> Fixing broken stuff transparently for a smooth upgrade path PLUS letting
> people know they're doing it wrong seems win-win and low cost.
>

I've implemented this variant now. If the comparison function returns a
boolean, you get

> Deprecated: usort(): Returning bool from comparison function is

deprecated, return one of -1, 0 or 1 instead in %s on line %d

once per usort() call, and we retry with swapped operands to ensure
compatibility.

Regards,
Nikita

Andrew Faulds

6 years ago

Hi,

Nikita Popov wrote:

>
> I've implemented this variant now. If the comparison function returns a
> boolean, you get
>
>> Deprecated: usort(): Returning bool from comparison function is
> deprecated, return one of -1, 0 or 1 instead in %s on line %d
>
> once per usort() call, and we retry with swapped operands to ensure
> compatibility.
>
> Regards,
> Nikita
>

I think that message could be a little misleading, because any negative
or positive value is valid, not just those of magnitude 1, right? IIRC
strcmp($a, $b) doesn't just return -1 and 1, and of course this is also
the case for the classic ($a - $b).

Thanks,
Andrea

Christoph Becker

6 years ago

On 04.03.2020 at 19:11, Nikita Popov wrote:

> 1. As Tyson suggests, we can throw a warning if a boolean is returned from
> the comparison callback (probably with a check to only throw it once per
> sort), to make it obvious what the cause is.
>
> 2. We can fix this transparently by doing something like this internally:
>
> $result = $compare($a, $b);
> if ($result !== false) {
>     return (int) $result; // Normal behavior
> }
>
> // Bad comparison function, try the reverse order as well
> return -$compare($b, $a);
>
> That is, we will recover the full three-way comparison result from the
> "greater than" result, by checking for both $a > $b and $b > $a.

Given that we have internal classes which deliberately have such
comparison behavior (i.e. returning 0 or 1, to signal that there is no
order defined), e.g. Closures[1], I tend to prefer raising a warning
instead of trying to recover.

[1]
<https://github.com/php/php-src/blob/php-7.4.3/Zend/zend_closures.c#L372>

--
Christoph M. Becker

Andrew Faulds

6 years ago

Christoph M. Becker wrote:

> Given that we have internal classes which deliberately have such
> comparison behavior (i.e. returning 0 or 1, to signal that there is no
> order defined), e.g. Closures[1], I tend to prefer raising a warning
> instead of trying to recover.

Oof… I wonder if we should make FALSE (maybe NULL too?) a special value
to signify “no ordering”?

Thanks,
Andrea

Nikita Popov

6 years ago

On Wed, Mar 4, 2020 at 11:12 PM Christoph M. Becker <cmbecker69@gmx.de>
wrote:

> On 04.03.2020 at 19:11, Nikita Popov wrote:
>
> > 1. As Tyson suggests, we can throw a warning if a boolean is returned
> from
> > the comparison callback (probably with a check to only throw it once per
> > sort), to make it obvious what the cause is.
> >
> > 2. We can fix this transparently by doing something like this internally:
> >
> > $result = $compare($a, $b);
> > if ($result !== false) {
> >     return (int) $result; // Normal behavior
> > }
> >
> > // Bad comparison function, try the reverse order as well
> > return -$compare($b, $a);
> >
> > That is, we will recover the full three-way comparison result from the
> > "greater than" result, by checking for both $a > $b and $b > $a.
>
> Given that we have internal classes which deliberately have such
> comparison behavior (i.e. returning 0 or 1, to signal that there is no
> order defined), e.g. Closures[1], I tend to prefer raising a warning
> instead of trying to recover.
>
> [1]
> <https://github.com/php/php-src/blob/php-7.4.3/Zend/zend_closures.c#L372>
>

This is a different case. The problem with my example is that it reports
equality where none exists, which is an issue if you try to change the
ordering of equal elements. Your case (which is indeed somewhat common in
extension code) always returns "greater-than" for non-equal elements. The
end result here is that the sort will not have any defined order regardless
of how we perform it. We can't really do anything about such cases.

I expect that a proposal for userland compare and equality overloading may
want to make the "not ordered" case more explicit, in which case we could
throw a warning when such comparisons are performed as part of sorting.

Nikita

Christoph Becker

6 years ago

On 05.03.2020 at 13:05, Nikita Popov wrote:

>> Given that we have internal classes which deliberately have such
>> comparison behavior (i.e. returning 0 or 1, to signal that there is no
>> order defined), e.g. Closures[1], I tend to prefer raising a warning
>> instead of trying to recover.
>>
>> [1]
>> <https://github.com/php/php-src/blob/php-7.4.3/Zend/zend_closures.c#L372>
>
> This is a different case. The problem with my example is that it reports
> equality where none exists, which is an issue if you try to change the
> ordering of equal elements. Your case (which is indeed somewhat common in
> extension code) always returns "greater-than" for non-equal elements. The
> end result here is that the sort will not have any defined order regardless
> of how we perform it. We can't really do anything about such cases.

Oops, of course.  Thanks for clarifying! :)

> I expect that a proposal for userland compare and equality overloading may
> want to make the "not ordered" case more explicit, in which case we could
> throw a warning when such comparisons are performed as part of sorting.

ACK.

--
Christoph M. Becker

Stas Malyshev

6 years ago

Hi!

> Given that we have internal classes which deliberately have such
> comparison behavior (i.e. returning 0 or 1, to signal that there is no
> order defined), e.g. Closures[1], I tend to prefer raising a warning
> instead of trying to recover.

I think there weirdness is because equality and comparison are mixed.
Equality can be defined for almost every object, but comaprison makes
sense for much smaller set of objects. So I wonder maybe a good solution
would be to somehow separate the two. And then maybe raise an exception
when trying to compare objects that can't be compared?

--
Stas Malyshev
smalyshev@gmail.com

tyson andre

6 years ago

Nicolas Grekas

6 years ago

Le mer. 4 mars 2020 à 18:30, tyson andre <tysonandre775@hotmail.com> a
écrit :

> > What do people think about this? Is there interest in making sorting
> > stable? Is it okay to break code using illegal comparison callbacks?
>
> I'd be interested in having a stable sort.
>

A new SORT_STABLE flag would be great!

Andrew Faulds

6 years ago

Hi Nikita,

Nikita Popov wrote:

> I believe that it is important for us to provide a stable sorting option in
> the standard library. We could introduce a separate stable function(s) for
> this purpose, but I believe we can just as well make all our existing sorts
> stable.

I agree with having a stable sorting algorithm, because I suspect
comparison functions in the wild are not exhaustive[0] enough to provide
very stable orderings, so having a well-defined ordering is kinder to
users — nobody wants sort() to scramble their array members if they
compare equal, right?

[0] By “exhaustive” I mean checking _every_ part of each value, not just
e.g. $a->name. Also, you might have SELECT'd some items from a database
and the DB explicitly (ORDER BY) or implicitly ordered them, but you
didn't think to include the thing ordered by in the SELECT'd columns.

> The only issue I ran into is that this change has a negative impact on code
> using illegal comparison callbacks like this:
>
> usort($array, function($a, $b) {
>      return $a > $b;
> });
>
> The return value of the sorting callback should be $a <=> $b, but using $a
>> $b also works right now, due to implementation details of the sorting
> implementation (only the outcome of $compare($a, $b) > 0 ends up being used
> by the sort).
>
> This kind of incorrect code will break under the proposed implementation,
> because we will now compare by original position if the comparison function
> reports equality. Because the comparator reports equality inconsistently
> (it says that $a == $b, but $b != $a), the sort results are also
> inconsistent.

My personal feeling is stable sorting is more important than supporting
broken callbacks, but I have no stats to base that on.

I think the suggestions in other emails of either trying to “fix” broken
algorithms or to warn the user they're broken are good ideas. I might
lean towards the latter given that:

• If such code was written before PHP 7.0 (IIRC) switched PHP to an
unstable sort, the code would have been broken then and hopefully
already fixed.
• PHP 7.0 introduced <=> to make writing correct comparison callbacks
easier.
• We help the programmer to do the right thing by pointing it out to
them, so they know what to do in future, and they get improved
performance (I think?) for it.

Thanks,
Andrea

Mike Schinkel

6 years ago

> On Mar 4, 2020, at 11:42 AM, Nikita Popov <nikita.ppv@gmail.com> wrote:
>
> Hi internals,
>
> Sorting function in PHP currently do not guarantee stability, which means
> that the result order of elements that compare equal is not defined.
>
> ....
>
> What do people think about this? Is there interest in making sorting
> stable? Is it okay to break code using illegal comparison callbacks?

I see that most people are okay with the BC breaks on this, and worst case I am okay with them too.

However, maybe this is an opportunity to create an object-based interface for array sorting? This could:

1.) Provide the stability guarantee,
2.) Be an object alternate to functions,
3.) Allow for option discovery via auto-complete in IDEs, and
4.) Be easier to remember than the current set of functions.

In order to have something for people visualize I created this userland example implementation as a straw man for a potential API that could be provided in core:

https://gist.github.com/mikeschinkel/dd22513a23852add93f3817ed9544337

If people like this idea, let's discuss.

If not, no need to reply and a lack of interest will signal this is not a direction to pursue.

-Mike