uasort() does NOT preserve sort order, but core assumes so (Element::children, css sort, ...)

You are not explicitly listing what the sort method is that is being used. We need to know the exact uasort example that is failing so that we can determine what approach will be necessary to solve the problem. The uasort takes an array and a function as arguments so if the function isn't correct, the sort order will be affected.

@sher1 Drupal\Component\Utility\SortArray::sortByWeightProperty was the affected sort function in the linked issue, but this is a meta issue to investigate all uses of uasort(), not just one specific case.

One simple way of handling this in the wrapper drupaluasort could be to add the array index to each element, so that comparison functions callbacks could be wrapped and apply the array index as a secondary comparable when the primary callback returns equality. This would ensure stable sorting.

As I see, we have to use a helper function as @fabianx suggested, I tried to modify the sort callback for uasort, but probably this solution will not work 100% correctly, so I will try to create a helper function that assigns value the comparison key before it is passed to uasort.

+++ b/core/includes/common.inc
@@ -1267,7 +1267,7 @@ function drupal_get_updaters() {
+    \Drupal\Component\Utility\SortArray::drupalUASort($updaters, array('Drupal\Component\Utility\SortArray', 'sortByWeightElement'));

Add use \Drupal\Component\Utility\SortArray and then call SortArray::drupalUASort.

+++ b/core/lib/Drupal/Component/Utility/SortArray.php
@@ -128,10 +134,35 @@ public static function sortByKeyInt($a, $b, $key) {
+   * In case if items are equal or if the specified sorting key is no set it will preserve the original order.

Should be on 2 lines to respect line break.

This patch needs tests for drupalUASort.

+++ b/core/lib/Drupal/Component/Utility/SortArray.php
@@ -107,7 +107,13 @@ public static function sortByKeyString($a, $b, $key) {
-    return strnatcasecmp($a_title, $b_title);
+    $comparison_value = strnatcasecmp($a_title, $b_title);
+    if ($comparison_value == 0) {
+      // Sort based on array index.
+      return static::sortByKeyInt($a, $b, '#array_index');
+    }
+
+    return $comparison_value;
   }
 
   /**
@@ -128,10 +134,36 @@ public static function sortByKeyInt($a, $b, $key) {

@@ -128,10 +134,36 @@ public static function sortByKeyInt($a, $b, $key) {
     $b_weight = (is_array($b) && isset($b[$key])) ? $b[$key] : 0;
 
     if ($a_weight == $b_weight) {
-      return 0;
+      // Sort based on array index.
+      return static::sortByKeyInt($a, $b, '#array_index');

This changes make tests failed.

I added the library to composer.json and vendor, it is really hard to work with the vendor directory because it is included in the repository. That really should be removed. Some test failed because 'static::sort' callback was sent and the suasort function couldn't find the function, so I replaced this callbacks. No interdiff is required because it was a totally new solution.

I don't really understand what the CI error is.

@Fabianx tried a quick port to a utility class with static functions with the PHPUnit tests + travis still working. On the right track?

https://github.com/joelpittet/PHP-stable-sort-functions

@Fabianx thanks, the original developer was thinking of a class name change like that too, I think I'll go with that so there is an easier grep for PHP equivalent.

I would be usefull to evaluate a possible performance regression with this aproatch.

@GroovyCarrot the original author merged my changes upstream into classes. We could use this library I think, no?

https://github.com/vanderlee/PHP-stable-sort-functions

@GroovyCarrot ok I thought I'd ask, he seemed keen on getting PS4 setup so I'm sure a pull request for that would suffice.

Proving this is a bug through a test should likely be top priority before profiling how slow it has become.

I wrote a quick start of a test (which you can run with drush scr test.php from your drupal root after applying the patch. I tried to prove the Issue summary correct but got wildly different results...

use \Drupal\Core\Render\Element;
use \Drupal\Component\Utility\SortArray;

$test_pass = [
  'foo:1' => ['#markup' => 'foo - first'],
  'bar:2' => ['#markup' => 'bar - second'],
];
$test_fail = [
  'foo:1' => ['#markup' => 'foo - first'],
  'bar:2' => ['#markup' => 'bar - second'],
  'first:0' => ['#markup' => 'little things', '#weight' => -1000],
];

uasort($test_pass, array('Drupal\Component\Utility\SortArray', 'sortByWeightElement'));
uasort($test_fail, array('Drupal\Component\Utility\SortArray', 'sortByWeightElement'));
$uasort_test_pass = $test_pass;
$uasort_test_fail = $test_fail;

// Reset test data.
$test_pass = [
  'foo:1' => ['#markup' => 'foo - first'],
  'bar:2' => ['#markup' => 'bar - second'],
];
$test_fail = [
  'foo:1' => ['#markup' => 'foo - first'],
  'bar:2' => ['#markup' => 'bar - second'],
  'first:0' => ['#markup' => 'little things', '#weight' => -1000],
];

SortArray::suasort($test_pass, array('Drupal\Component\Utility\SortArray', 'sortByWeightElement'));
SortArray::suasort($test_fail, array('Drupal\Component\Utility\SortArray', 'sortByWeightElement'));
$suasort_test_pass = $test_pass;
$suasort_test_fail = $test_fail;

drush_print('Should be the same:');
drush_print($uasort_test_pass === $suasort_test_pass ? 'pass' : 'fail');
drush_print(key($uasort_test_pass) === 'foo:1' ? 'pass' : 'fail');
drush_print(key($suasort_test_pass) === 'foo:1' ? 'pass' : 'fail');
drush_print_r(array_keys($uasort_test_pass));
drush_print_r(array_keys($suasort_test_pass));

drush_print('Should be the different:');
drush_print($uasort_test_fail !== $suasort_test_fail ? 'pass' : 'fail');
drush_print(key($uasort_test_fail) === 'first:0' ? 'pass' : 'fail');
drush_print(key($suasort_test_fail) === 'first:0' ? 'pass' : 'fail');
drush_print_r(array_keys($uasort_test_fail));
drush_print_r(array_keys($suasort_test_fail));

Should be the same:
fail
fail
pass
Array
(
    [0] => bar:2
    [1] => foo:1
)

Array
(
    [0] => foo:1
    [1] => bar:2
)

Should be the different:
pass
pass
fail
Array
(
    [0] => first:0
    [1] => bar:2
    [2] => foo:1
)

Array
(
    [0] => foo:1
    [1] => bar:2
    [2] => first:0
)

Also not a meta anymore.

@GroovyCarrot ah thanks, totally spaced on the method name. Because this is a bug we can split the tests out into a test only patch for the core committers to see our tests are doing what they said. That way we can show it's broken before.

Upload the failing tests (test only patch) first and passing one second. Would you mind doing that @GroovyCarrot?

Oh and I guess that would be a regression tests-only patch because the current test just makes sure the new method works correctly.

Current tests look great BTW, much better than I could write;)

That is great! it would be nice even to have that as a regression test showing that they are 'not equal' to keep with this issue so people don't remove it without due process.

I'll help with the profiling with xhprof-kit if I can get a decent scenario where this gets called frequently. Any scenario suggestions in your travels on this patch?

Actually you're right xhprof would be bad for this anyway. Just like you did is good to narrow it down and do one with many arrays and one with large arrays.

I'll give this a test as well this evening. The profiling is secondary to fixing the bug but it's nice to know the hit we are taking fixing this.

@GroovyCarrot other than the minor ending commas on the array items in the test I reviewed the code with --color-words and everything looks good. The needed change to change protected to public on that one method may bump this up to 8.1.x but I'll let the committer decide that. Feel free to post a clean-up patch for the array items commas and leave it RTBC, you can also use short array syntax in your new test class method.

Your profiling is showing a slight performance improvement, which actually I confirmed as well while profiling the functions. As I added bigger arrays though that performance started to go south.

With 100,000 weights there gets a bit of a performance regression:

uasort: 4.66316 seconds
SortArray::suasort 6.703 seconds

With only 10,000 weights it's a performance improvement and is more likely use-case to be less.

SortArray::suasort: 0.28879 seconds
uasort: 0.65772 seconds

I don't think a test showing PHP is poor at this will serve us well (especially if they fix it) now that I think about it some more.

drush scr perf.php
https://gist.github.com/2978037a059f0bcd7dd5

+++ b/core/lib/Drupal/Component/Utility/SortArray.php
@@ -134,4 +134,61 @@ public static function sortByKeyInt($a, $b, $key) {
+   * Sort an array with a user-defined comparison function and maintain index association.

Nitpick: shouldn't go over 80 chars

This should probably have a change record.

Thanks @swentel, I start one, @GroovyCarrot feel free to correct my Change Record.

@GroovyCarrot these little niggles should be take care of, shouldn't take you long, I'd patch these for you but testing out the non-upload commit credit thing;)

1. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,61 @@ public static function sortByKeyInt($a, $b, $key) {
   +   * Sort an array with a user-defined comparison function and maintain index association.
   

   As @swentel mentioned, 80 chars, and if I remember it should be on one line if possible.

2. +++ b/core/tests/Drupal/Tests/Component/Utility/SortArrayTest.php
   @@ -310,6 +310,156 @@ public function providerSortByTitleProperty() {
   +        '#title' => 'C',
   +        '#weight' => -1000
   ...
   +        '#title' => 'D',
   +        '#weight' => -1000
   ...
   +        '#title' => 'G',
   +        '#weight' => -500
   ...
   +        '#title' => 'A',
   +        '#weight' => 0
   

   Missing commas

@GroovyCarrot et al. Have a peek and make sure the CR works for you.
https://www.drupal.org/node/2661308

Thanks for knocking those little things out. Back to RTBC.

1. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
   +   * Sort an array with a user-defined comparison function.
   

   Sorts an array stably using a user-defined comparison function. is the only way I could get in under 80 chars and mention the key fact that the sort is stable.

2. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
   +   * Maintains index association.
   ...
   +   * Usage of PHP's uasort() is avoided to prevent warning while debugging.
   

   These two lines should be together and describe what a stable sort is. Something like:

   Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). Additionally, this implementation does not call PHP's uasort() to avoid warnings while debugging.

   I have to honest though I always think that PHP warning is sensible. Sorting should not alter the array and if it does something is wrong. So are we losing a safeguard here?

3. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
   +   *   https://bugs.php.net/bug.php?id=50688
   +   *   https://bugs.php.net/bug.php?id=53341
   

   A list has - for each item.

4. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
   +   * @param $cmp_function
   

   Can typehint here... @param callable $cmp_function

5. +++ b/core/lib/Drupal/Component/Utility/SortArray.php
   @@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
   +  public static function suasort(&$array, $cmp_function) {
   

   Generally Drupal prefers method names that are less cryptic. How about stableUasort() or uasortStable(). My preference is for the first one.

6. +++ b/core/tests/Drupal/Tests/Component/Utility/SortArrayTest.php
   @@ -310,6 +310,156 @@ public function providerSortByTitleProperty() {
   +  public function providersuasort() {
   

   Given the way the method works can we add some tests with more than 3 elements? And some with 2 and some with 1.

7. The noticeable performance improvement is interesting!

@GroovyCarrot can we add a test proving that user-defined comparison functions can't alter the array?

Updated the method name in the CR too. I diffed the previous RTBC'd patch #53 an with #65 and nothing stood out. Now with more coverage;)

There's no test of sorting an array with a single element and there's no test of sorting an array with a user-defined function that changes values.

+++ b/core/tests/Drupal/Tests/Component/Utility/SortArrayTest.php
@@ -310,6 +310,374 @@ public function providerSortByTitleProperty() {
+    SortArray::stableUasort($test, [$this, 'sortByWeightProperty']);

This should have failed as $this does not have this method.

+++ b/core/lib/Drupal/Component/Utility/SortArray.php
@@ -134,4 +134,65 @@ public static function sortByKeyInt($a, $b, $key) {
+  public static function stableUasort(array &$array, $cmp_function) {

We can actually use the callable type hint... https://secure.php.net/manual/en/functions.arguments.php#functions.argum...

Is there any update to this issue? The last patch passed the tests so does that mean it is ready to be merged or is there more work to be done?

I currently have a quite nasty issue using the IEF module: #2653574: Unable to keep nested IEF data separate with multivalue fields.

IEF overwrites referenced entities in the table listing when creating new references. The issue only happens in PHP 7 and I suspect this could be the underlying problem.

@GroovyCarrot tried applying the patch but it did not help unfortunately. It was kind of a wild guess after all..

But even so, what is keeping this from being merged?

The concerns look to be addressed. Back to RTBC.

@GroovyCarrot Sorry for not reviewing sooner... I think we need to trigger a warning if a user comparison function alters the array - along the lines of what happens if you do this for usort().

PHP Warning: usort(): Array was modified by the user comparison function in /home/jcampbell/usortExceptionWarning.php

Silently succeeding and not telling the user feels problematic. I think the stable usort should be as close as possible in functionality to PHP's usort.

Implementing a sort in user space like this sounds like a terrible idea. I'm surprised there is no proper benchmark of this, especially on non-cached pages, or large forms like the permission form.

The code itself is obviously based on this comment by "php at clement dot hk" in the PHP documentation (including all the weird kinks, like using a float to slice an array...). This is probably a non-started as, as far as I can see, the documentation is released under Creative Commons Attribution 3.0, which might or might not be compatible with the GPL.

But really this whole thing is a solution in search of a problem. We have had sort stabilization code for years, it's not that complicated. You just need to make sure that if you care about sort stability, your comparison function never returns 0. Doing so for the simple case of #weight only requires to go through each item and set the weight if it is not set:

    // Assign a decimal placeholder weight to preserve original array order.
    if (!isset($element[$key]['#weight'])) {
      $element[$key]['#weight'] = $count/1000;
    }

If you want to be pedantic about it, wrap the sort function into something that throws an exception if the result is zero, and fix what breaks.

@GroovyCarrot: If you want to push it forward, this issue does need a reboot. Between the dubious origin of the code and the massive performance impact of the approach (implementing a merge-sort in PHP), there is not much to salvage from the original design.

Note that using uasort() to sort is a pretty bad idea in general anyway. The way this is implemented in PHP the comparison callback should be expected to be called in the range of O(n*log(n)) times for each sort operation.

A much better approach is to build a key that is a simple PHP type, and use the internal PHP implementation to sort on that. Once you have a key, making the sort stable is trivial.

A trivial implementation of a stable sort by a "#weight" key that might or might not be there:

function sort_by_weight($array) {
  $i = 0;
  $count = count($array);

  $sort_keys = [];
  foreach ($array as $k => $v) {
    $sort_keys[$k] = $v["#weight"] + $i / $count;
    $i++;
  }

  asort($sort_keys);

  $sorted_array = [];
  foreach ($sort_keys as $k => $_) {
    $sorted_array[$k] = $array[$k];
  }

  return $sorted_array;
}

Even on small arrays, this is vastly faster than even straight uasort() (about 4x for 10 items, about 10x for 100 items in my own quick benchmark), so let's not talk about the custom implementation of the merge sort.

So, no, our usages of uasort() should not be fixed. They should just die. There are very few good reasons to use uasort() in the first place.

If all we are doing is to provide stable alternatives to PHP sort functions, then this should not be part of Drupal core.
Either a 3rd party library already exists, or we create one.

(EDIT: Sorry, didn't read enough. Apparently an existing 3rd party library was already proposed, but decided against. I would prefer seeing this outside of Drupal, but I don't want to restart arguments that are already finished.)

#82

In your code, you've suggested using a fraction in order to stabilise the array sort.

There is another option. I would bet it is faster, but it is also more robust:

Option A: Keys by weight.

1. Group the keys of the original array by weight, using the weights as array keys.
2. Sort the grouped keys-by-weight with ksort().
3. Build the sorted array of items.

$grouped = [];
foreach ($items as $k => $item) {
  $grouped[(string)get_weight($item)][] = $k;
}
ksort($grouped, $sort_options);
$sorted = []:
foreach ($grouped as $weight => $keys) {
  foreach ($keys as $k) {
    $sorted[$k] = $items[$k];
  }
}
return $sorted;

EDIT: I was going to call this a "bucket sort" approach, but I think this label can be misleading.

EDIT: Just saying, we need to be careful when using item weights as array keys. E.g. [0.1 => 'x'] is the same as [0 => 'x'].

Option B: Weights by key

1. Build an array of weights by key.
2. Use a stable equivalent to asort().
3. Build the sorted array of items.

$weights = [];
foreach ($items as $k => $item) {
  $weights[$k] = get_weight($item);
}
// This assumes we have an asort_stable() implementation somewhere.
asort_stable($weights, $sort_flags);
$sorted = array();
foreach ($weights as $k => $weight) {
  $sorted[$k] = $items[$k];
}
return $sorted;

(EDIT:) Option C: Items by weight

$grouped = [];
foreach ($items as $k => $item) {
  $grouped[(string)get_weight($item)][$k] = $item;
}
ksort($grouped, $sort_options);
$sorted = []:
foreach ($grouped as $weight => $items_in_group) {
  $sorted += $items_in_group;
}
return $sorted;

We need some benchmark to see which option is faster.

How to get item weights

To avoid unnecessary callbacks, we should have different versions of the sort function, depending how the item weight is determined.
One for $item[$weight_key], one for $item->$weight_method(), one for $weight_callback($item). Hardcoding is usually good for performance.

(EDIT:) Array-by-reference or return $sorted?

This is something we can discuss..
function sort(array &$items) : void vs function sort(array $items) : array.

Render arrays

Render arrays are a special case.
Besides the sorting, they also require to distinguish element children and element properties ('#').
We should have a dedicated implementation for those, and not worry about them here.
#2522712-26: Simplify Element::children() stable sort.
There is also another special issue about references.

Render arrays are really a special cup of tea. Besides the sorting problem, we need to distinguish element children vs element properties (starting with '#'). And then there is the reference issue described in #11.

I think it is better for performance and for transparency to have a dedicated one-off sort implementation for this specific case. So, exactly what is being proposed in this issue.

How to move on

Imo this should be treated as two separate steps / problems:

1. Implement stable-sort-by-weight functions (+ tests).
   This should be in a dedicated issue, not here, imo. With clear specs in the issue summary.
   Or, for my taste, in a 3rd party library. But I heard we have policy that makes this not as easy.
   This should *only* introduce these functions, but not use them anywhere. Except in unit tests. And maybe a proof-of-concept patch which will be tested, but not committed.
   
2. Use the new functions to replace existing code.
   This should be a separate issue. Maybe reuse this one, or start a new.

@GroovyCarrot:
Please do not consider me an authority on whether or not to open new issues. I am just stating what I personally find reasonable. Others might disagree.

SortArray::sortBySubKeyInt() vs SortArray::sortBySubKeyString():
Is this distinction even necessary? I think not, If we use one of the approaches in #85, and accept a $sort_flags parameter.

My own preference for method names would be:

// $weight = isset($item[$weight_key]) ? $item[$weight_key] : 0;
SortArray::sortByWeightKey(&$items, $weight_key, $sort_flags);

// $weight = $item->$weight_method_name();
SortArray::sortByWeightMethod(&$items, $weight_method_name, $sort_flags);

// $weight = $weight_callback($item);
SortArray::sortByWeightCallback(&$items, $weight_callback, $sort_flags);

https://github.com/donquixote/stable/tree/drupal-org-2466097-87-benchmarks
(Please look at this specific tag. The rest of the library may change over time.)

This is sandbox code to evaluate which of the options in #85 and #81 is faster.

Output of php bench/run.php:

Array
(
    [itemsByWeight] => Array
        (
            [0] => 0.68853402137756
            [1] => 0.70416021347046
            [2] => 0.80906105041504
            [3] => 0.79766297340393
        )

    [keysByWeight] => Array
        (
            [0] => 1.0398819446564
            [1] => 1.1839768886566
            [2] => 1.2117691040039
            [3] => 1.1905200481415
        )

    [weightWithFraction] => Array
        (
            [0] => 1.5242249965668
            [1] => 1.7134919166565
            [2] => 1.6905879974365
            [3] => 1.7888038158417
        )

)

This means that "items by weight" (Option C in #85) is the fastest in the given scenario.

Option B in #85 was not tested, because I do not currently see a promising candidate for the asort_stable() this would require.

-----

Having the weight as an array key to group by is ok for numeric weights.
For string weights or more exotic weight types there are limitations:
E.g. what if two weights are different, but considered equally great?
What if the weights are not even strings, but objects, arrays, or something else?

I think it is ok to limit ourselves to two cases:

1. All weights are int or float. Sort flag is SORT_NUMERIC. (string)$weight gives us the array key. This would cause weird results if $weight is e.g. '' or ' ' or ' ' or some other string. But we said these values are not allowed, so we don't have to worry.
2. All weights are strings or numbers that we treat as strings. Sort flag is something different from SORT_NUMERIC, something suited for strings.

I think this is sufficient. So we can use the same code for all cases.

If we can agree whether or not to open a new issue "Introduce stable-sort-by-weight functions", I can/will start working on patches.

@Fabianx:
I am looking at backdrop_sort(), and I am not really convinced..

The implementation relies on comparison callbacks, which can be expected to be considerably slower than anything proposed in #85 ff.
It has multiple cases in the same function, which should be split up into subroutines.

The public API of the backdrop_sort() function also tries to cover different cases at once. I would much rather see separate functions for separate cases. This way, when you see a function call, you know which case this is. Also this generally allows for better optimization.

The sorting by more than one key can be useful, but in the majority of cases relevant to us there is only one key.

Can we also compare how these solutions fare performance-wise

Poor, I bet..
(numbers will follow)

against array_multisort(), which can also be used for stable sorting. (e.g. with a 1..count($items) generated array)?

How do you imagine this array_multisort() solution?

Oh, and the backdrop sort is not even stable.

Here is a new version of the sandbox which also benchmarks the backdrop sort.
https://github.com/donquixote/stable/blob/drupal-org-2466097-91-benchmar...
(Again: Look at this specific tag. The rest of the library may change over time.)

Benchmark result of php bench/run.php:

Array
(
    [itemsByWeight] => Array
        (
            [0] => 0.63954091072083
            [1] => 0.75006413459778
            [2] => 0.75336098670959
            [3] => 1.0024151802063
        )

    [keysByWeight] => Array
        (
            [0] => 1.0129480361938
            [1] => 1.0103509426117
            [2] => 1.0209269523621
            [3] => 1.1664638519287
        )

    [weightWithFraction] => Array
        (
            [0] => 1.3150410652161
            [1] => 1.3042709827423
            [2] => 1.3136579990387
            [3] => 1.321298122406
        )

    [backdrop] => Array
        (
            [0] => 26.689792871475
            [1] => 26.148816108704
            [2] => 26.052208900452
            [3] => 27.817613840103
        )

)

So, depending how you calculate it, the backdrop sort is around 36x slower than the "items by weight" sort.
(27 / 0.75 === 36)

What's missing is the array_multisort(), which I have yet to understand how this is supposed to work...

I think I do understand the idea with array_multisort() now.
https://github.com/donquixote/stable/commit/954360603477fb2aece698aa2b16...

One problem is that array_multisort does not preserve numeric indices. (says the php manual.) To circumvent this limitation, we need to pass the array keys as a 3rd array, which probably slows things down.

Here are the numbers. I removed backdrop sort from the benchmark, it took too long.

Array
(
    [itemsByWeight] => Array
        (
            [0] => 0.75949001312256
            [1] => 0.7157130241394
            [2] => 0.7151939868927
            [3] => 0.72723007202148
        )

    [keysByWeight] => Array
        (
            [0] => 1.0754590034485
            [1] => 1.0269019603729
            [2] => 1.0482859611511
            [3] => 1.0533368587494
        )

    [weightWithFraction] => Array
        (
            [0] => 1.3721950054169
            [1] => 1.3079779148102
            [2] => 1.270740032196
            [3] => 1.2985351085663
        )

    [arrayMultisort] => Array
        (
            [0] => 1.6991391181946
            [1] => 1.6858711242676
            [2] => 1.6876718997955
            [3] => 1.6864540576935
        )

)

Much better than the backdrop sort in #91, but still slower than the other functions.

Can this also be applied to arbitrary keys?

You mean more than one key?

I see two three options:

1. Sort (in a stable way) the entire array by the sort criterion with least precedence first, then the one with second least precedence, etc.
2. Group the array by the sort criterion with highest precedence, then sort any group with more than one item by the second sort criterion, etc.
3. (EDIT:) Use array_multisort(). This might get more attractive the more sort criteria we have.

I think the second option is more promising.
Code + numbers will follow.

Tag: https://github.com/donquixote/stable/tree/drupal-org-2466097-95-sort-keys
Commit: https://github.com/donquixote/stable/commit/08cbaf25c217ce2b2cd181cca1ca...

  /**
   * @param array[] $items_unsorted
   * @param int[] $sort_flags_by_weight_key
   *   Format: $[$weight_key] = $sort_flags
   *
   * @return array[]
   */
  public static function sortByWeightKeys_itemsByWeight(array $items_unsorted, array $sort_flags_by_weight_key) {

    $sort_flags = reset($sort_flags_by_weight_key);
    $weight_key = key($sort_flags_by_weight_key);
    unset($sort_flags_by_weight_key[$weight_key]);
    $neutral_value = self::sortFlagsGetNeutralValue($sort_flags);

    $items_by_weight = [];
    foreach ($items_unsorted as $k => $item) {
      if (isset($item[$weight_key])) {
        $items_by_weight[(string)$item[$weight_key]][$k] = $item;
      }
      else {
        $items_by_weight[$neutral_value][$k] = $item;
      }
    }

    ksort($items_by_weight, $sort_flags);

    $items_sorted = [];
    if ([] === $sort_flags_by_weight_key) {
      foreach ($items_by_weight as $weight => $items_in_group) {
        $items_sorted += $items_in_group;
      }
    }
    else {
      foreach ($items_by_weight as $weight => $items_in_group) {
        if (1 !== count($items_in_group)) {
          $items_sorted += self::sortByWeightKeys_itemsByWeight($items_in_group, $sort_flags_by_weight_key);
        }
        else {
          $items_sorted += $items_in_group;
        }
      }
    }

    return $items_sorted;
  }

No profiling numbers, but I think it will be ok.

In most cases, only a few items will have the same non-zero weight. E.g. 10 items without a weight (so the default weight is used), and then 5 items with distinct non-zero weights. This means the recursive call typically happens for only one group, the one with weight = 0. I think it is ok to optimize for this case.

I did not add any magic conversion of array value as sort key, as in backdrop.
If we really want this, it can be done in a separate function on top of this one.

I still think we should have distinct sort functions for different use cases. sortByWeightKey() accepts one weight key, sortByWeightKeys() accepts multiple weight keys. And then there is sortByWeightMethod() and sortByWeightCallback().
This should be enough for a start. We can add more, e.g. sortByWeightMethods(), when the need arises.

@Fabianx: In the patch in #72, there is one case with a $language->getWeight() method. This is why I proposed sortByWeightMethod().

But we can also have a hardcoded stable sort only for languages. This would be even faster, because then the method name can be hardcoded. And we don't need any method_exists() check.

Or we make an interface with a getWeight() method.

--------

Should we open a new issue "Introduce stable-sort-by-weight functions"?
This way, newcomers or people who want to understand the git history don't have to read 80 comments about an approach that was already discarded.

  /**
   * @param int|null $sort_flags
   *
   * @return int|string
   */
  public static function sortFlagsGetNeutralValue($sort_flags = null) {
    // @todo Support more cases.
    if ($sort_flags === SORT_STRING) {
      return '';
    }
    else {
      return 0;
    }
  }

Any opinion on this? What is the correct neutral value for other sort types?
Neutral value is the weight that will be assumed for items without an explicit weight.

#98: It does not need to be all-encompassing.

The problem is: If the method accepts a $sort_flags parameter, and we implement the "neutral weight" in a specific way, then changing it later would be a BC break.
E.g. if now we say that the "neutral weight" for SORT_REGULAR is 0, but we later change it to '', then this would be a BC break.

Since there was no other opinion on whether to open a new issue, I made the call myself.
#2757207: Introduce "stable sort by weight" functions to sort arrays (and objects)

I am currently working on this in other issues.
#2757207: Introduce "stable sort by weight" functions to sort arrays (and objects)
#2759479: Proof of concept: Replace uasort() with dedicated stable-sort-by-weight functions, where possible

@joelpittet, others:
I need a relevant use case with Drupal 8, where a call to uasort() is expensive enough that it shows up in xhprof, and is worth optimizing. Otherwise I don't know what to profile, except the raw functions.
Any hints or instructions are appreciated!

@donquixote I put a link of how I tested in #48 is that what you are refering to? In a real/heavy use-case I think the biggest and slowest render call is simpletest UI. Building that table (IIRC we build it twice for #type table). (Edit, not sure if uasort is used lots, I just know it's the slowest rendered thing I recall)

@donquixote I put a link of how I tested in #48 is that what you are refering to?

@joelpittet: Ok, so if I understand correctly, #48 (the gist) is just a raw functions test, similar to the benchmarks in #2757207: Introduce "stable sort by weight" functions to sort arrays (and objects), but not really something we know is really happening in Drupal.

In a real/heavy use-case I think the biggest and slowest render call is simpletest UI. Building that table (IIRC we build it twice for #type table). (Edit, not sure if uasort is used lots, I just know it's the slowest rendered thing I recall)

Ok I had a look. Drupal\simpletest\TestDiscovery::getTestClasses(), if not cached, uses uksort() with strnatcasecmp() for the groups and for the tests within each group.

    uksort($list, 'strnatcasecmp');
    foreach ($list as &$tests) {
      uksort($tests, 'strnatcasecmp');
    }

For me (core with very few contrib) this entire code snippet uses ~9.6 milliseconds (tested with microtime(TRUE)). Not very impressive, imo.

This could be replaced with ksort(*, SORT_NATURAL | SORT_FLAG_CASE);.
Doing this speeds it up to ~3.15 milliseconds. So 3x as fast.
But does it really matter?

Stability in ksort() / uksort():
One could think this is completely pointless, because all keys are distinct.
But if the (strict) order we are using is not a strict *total* order, then two distinct keys can be considered as equal for the sake of ordering, making the ksort() / uksort() less than 100% predictable.

There are some other calls to usort() and uksort() which I did so far neglect in the two issues I opened..
Also other sort functions without a callback, where stability might become relevant.

The other case where sort performance and stability does matter is sorting render arrays by weight.
But these should, imo, be dealt with in a separate issue, this one: #2522712: Simplify Element::children() stable sort.

It's to test the performance of the proposed solution at scales to see how it holds up vs the native sort.

I'm sure the author of the patch will be more capable of understanding your analysis/feedback than I. I'm taking it at face value, testable failure on an issue that seems like it could cause is problems in the wild.

The proof-of-concept patch in #2759479-25: Proof of concept: Replace uasort() with dedicated stable-sort-by-weight functions, where possible passes.
It is time for some DX review.
The main question to discuss at this point is whether the public API of the StableSort::*() methods is pleasant enough to use, or if we want something else.
(It is not a time for code style review, just saying.)

Thank you everyone for all the work done on this issue.

catch, alexpott, effulgentsia, xjm, Cottser and cilefen discussed this issue on a triage call. It was decided this issue should remain at major priority. I've tagged it for a title (it's a meta issue, right?) and summary update. We should remove the obsolete examples from the summary (because #2448765: Element::children sort order undefined and slower than it could be - This makes tests fail in PHP7 was fixed) and consider setting this back to active while alternate approaches are considered. These could even take the form of a documentation of best practices or a custom solution.

Notes from the discussion include:

• Are there remaining callers that don't use microweights but expect insertion order to be preserved?
• The non-deterministic nature can maybe lead to random or environment-specific test failures.
• Some PHP versions throw notices when sorting arrays of objects. Should we check the PHP version (cilefen: irrelevant with >=5.6)?
• Could this issue be more of a task/plan?
• In any case, this is needs work if array_multisort() is the way to go.

Adding a link to #2834022: drupal_sort_weight sort order undefined and possibly inconsistent between PHP 5 and PHP 7, which can essentially be a Drupal 7 backport of this issue.

It has some code that may make sense to borrow for the Drupal 8 patch here.

patch 72 probably needs a reroll, let's see what the testbot says.

What is the decision here?

The Needs Review Queue Bot tested this issue. It either no longer applies to Drupal core, or fails the Drupal core commit checks. Therefore, this issue status is now "Needs work".

Apart from a re-roll or rebase, this issue may need more work to address feedback in the issue or MR comments. To progress an issue, incorporate this feedback as part of the process of updating the issue. This helps other contributors to know what is outstanding.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.