Introduce "stable sort by weight" functions to sort arrays (and objects)

It just came to my mind that in our current plans we don't have an option to sort descending instead of ascending.
The same is true for backdrop_sort(), see https://github.com/quicksketch/backdrop/blob/7bee8d0433e7401e7b5ff95790d...

I will add a parameter to choose a sort direction.

So far I am considering an algorithm with (simplified):

    foreach (..) {
      $values_by_weight[(string)$weight][$k] = $item;
    }
    ksort($values_by_weight);

I just found a possible "weakness" of this algorithm.
(string)'0.0' is not the same as (string)0.0 or (string)'0.00'.
https://3v4l.org/Ua5KU
This can lead to a non-stable sort behavior in some cases with SORT_NUMERIC.

I hope we can say it is the caller's responsibility to use "canonical" float representations.

  /**
   * Determines a "neutral weight" based on sort flags, to be used as a fallback
   * for items without an explicit weight.
   *
   * @param int|null $sort_flags
   *   Either SORT_NUMERIC or SORT_STRING.
   *
   * @return int|string
   *   The "neutral weight".
   */
  public static function sortFlagsGetNeutralWeight($sort_flags) {
    if ($sort_flags === SORT_NUMERIC) {
      return 0;
    }
    elseif ($sort_flags === SORT_STRING || $sort_flags === SORT_STRING | SORT_FLAG_CASE) {
      return '';
    }
    else {
      $sort_flags_export = var_export($sort_flags, TRUE);
      throw new \InvalidArgumentException("Sort flags must be either SORT_NUMERIC or SORT_STRING, $sort_flags_export found instead.");
    }
  }

What should be the "neutral weight" for SORT_REGULAR and SORT_NATURAL?
Maybe '' is ok for all of them?
backdrop_sort() uses '' for SORT_STRING, and 0 otherwise. But it says somewhere that only SORT_STRING and SORT_NUMERIC are supported.
Maybe we should use 0 for SORT_NUMERIC, and '' for any other, to avoid this artificial limitation.

Useful information about SORT_REGULAR: http://stackoverflow.com/a/38112705/246724

Thanks!
I will wait with a new patch until there is more feedback :)

I think just StableSort is fine.

Ok.
I was undecided about this. I personally like to prepend *Util to classes that are not meant to be instantiated. But this does not seem to be a pattern in Drupal. So I'm fine without it.

Unless we are sure we never want to extend that.

People can override the sortFlagsGetNeutralWeight() method, can't they?

But I have a different proposal (which I think should be done more often in Drupal):
Seal the class with "final", and open it up when someone actually has a valid use case for extending.
At this point we can decide to introduce the protected configuration map, or anything else we deem useful. The sortFlagsGetNeutralWeight() can remain, but will then use the conf map.

Btw by "configuration map" I hope we agree this should be treated as a constant, right? No fiddling around with dynamic settings!

And before we think of inheritance, maybe there are better options:

1. An additional parameter $neutral_weight. The only place where this does not work is the case with multiple keys. Because we would need a separate default weight per key.
2. An interface SortInterface, with different implementations WeightKeySort, WeightMethodSort, and a MultiSort which accepts a SortInterface[] parameter for an array of SortInterface objects. This allows to combine different types of sort, so it is not limited to array with weight keys. Implementations can simply call the static methods, I don't care.

Oh and it would be great if we could start some conversions of things from uasort() to this new method.

I would prefer if we could keep this patch small, and also keep the issue discussion focused.
Maybe we can upload proof-of-concept patches somewhere, which are not going to be committed but just show that it works? Maybe here, or maybe in another issue.

I just hate if a "git blame" sends me to a huge commit and then an issue with a really long list of comments, where only a small part of the commit and the issue actually talk about what I am looking for.
And then people complain if I post without having read all the comments...
It would be great if we can avoid this.

And we definitely should do some profiling.

Is it ok to do the profiling in the github library at https://github.com/donquixote/stable ?
The code has changed a bit, but performance should still be similar to what was measured there. There is a bit of added indirection due to the ksortAndMergeGroups() being factored out. But this call is outside of any loops, so it happens only once per sort.

I just noticed a case in Symfony that uses uasort() in a similar way as we do, likely with the same issues for performance and stability.

namespace Symfony\Component\HttpFoundation;
[..]
class AcceptHeader
[..]
    private function sort()
    {
        if (!$this->sorted) {

            uasort($this->items, function (AcceptHeaderItem $a, AcceptHeaderItem $b) {
                $qA = $a->getQuality();
                $qB = $b->getQuality();

                if ($qA === $qB) {
                    return $a->getIndex() > $b->getIndex() ? 1 : -1;
                }

                return $qA > $qB ? -1 : 1;
            });

            $this->sorted = true;
        }
    }

For me this is yet another indicator that this code should live in a 3rd party library.
This would also allow to follow through with the "advanced ideas" in #11.

I will proceed with this work as planned within core, until I get another opinion.

SortArray::sortByKeyString() uses strnatcasecmp().
I suppose this is equivalent to sorting with SORT_NATURAL, but after applying strotolower().

system_sort_modules_by_info_name() uses strcasecmp().
The PHP manual says this is "binary safe". I wonder if the PHP sort functions / flags are also "binary safe", and how we can verify this.

We could rely on the SORT_FLAG_CASE to achieve case insensitivity.
But then the grouping would make the sort unstable.

$sorted = array_values(StableSort::sortByValue(['a', 'A', 'a', A'], SORT_NATURAL | SORT_FLAG_CASE));
// These assertions will pass:
assert(['a', 'a', 'A', 'A'] === $sorted || ['A', 'A', 'a', 'a'] === $sorted);
assert(['a', 'A', 'a', 'A'] !== $sorted);

The correct order can only be achieved by calling strtolower() while building the groups. But this will likely destroy the performance gain.

The next best option is to use array_multisort() for such cases. Here the only question is whether this is "binary safe".

Quick note:
It turns out that the array_multisort() solution is equally fast as the grouping solution IF all or most items have different weights.
If a lot of items have the same weight, then the grouping solution (itemsByKey) is faster.

E.g. when sorting blocks by title, we can assume that each block has a different title, so array_multisort() is a good fit.
When sorting something by numeric weight, a lot of items will likely have weight === 0, which makes the grouping solution faster.

With string weights, calling strtolower() for each item's weight, which is necessary to achieve a stable case-insensitive sort by string weight, puts the nail in the coffin for the grouping solution, making it slower than the array_multisort() solution. Or even worse when using mb_strtolower() instead of strtolower().

There will be numbers. But for now I am only posting this quick note.

More benchmark results! Smaller number = faster.
https://github.com/donquixote/stable/blob/drupal-org-2757207-16-benchmar...
Everyone is invited to reproduce this stuff and play with the code.

Percentiles (medians at different %) are better than averages!
http://apmblog.dynatrace.com/2012/11/14/why-averages-suck-and-percentile...

sortByWeightKey()
php bench/run.php
Comparing sortByWeightKey() functions with SORT_NUMERIC, where the weight key is present in some items, but not all.
Size of sortable array reduced to 100.

                         25%   50%   75%   90%
itemsByWeight_isArray    122   123   125   129
itemsByWeight             63    63    64    66
keysByWeight              90    90    91    95
weightWithFraction       103   103   104   109
arrayMultisort           110   110   111   117
backdrop (NOT STABLE!)  1811  1818  1841  1927

This means: A sort which checks is_array() for each item takes 2x the time than it would without this check.
Whenever we already know that items are arrays, it is worthwhile to skip the is_array() check.

sortByKnownWeightKey()
php bench/run-knownKey.php
Comparing sortByWeightKey functions with SORT_NUMERIC, where the weight key is present in each item, but the weight is 0 a lot of times. The version with _knownKey omits the isset($item[$key]) check. The version with _isArray checks for each item whether it is an array, in addition to the isset() check. _arrayKeyExists uses array_key_exists() instead of isset.

                              25%  50%  75%  90%
itemsByWeight_knownKey         67   68   71   74
itemsByWeight                  78   79   83   85
itemsByWeight_isArray         144  146  153  157
itemsByWeight_arrayKeyExists  137  139  145  148

We can see that omitting the isset() makes the sort slightly faster. But the difference is not big enough to justify a separate implementation.

array_key_exists() is not a good idea at all, from a performance point of view. Let's just forget about it. This was to be expected, but now we have it in numbers.

Sort by string weight, case insensitive, even distribution
php bench/run-strtolower-evendist.php
Comparing sort by weight functions that sort by string weight with SORT_NATURAL, case insensitively.
Precise implementations can be seen in the git tag.
Here each item has a distinct string weight at $item['x'].

                           25%  50%  75%  90%
itemsByWeight (FLAWED!!)   149  151  153  158
itemsByWeightStrtolower    208  209  212  218
itemsByWeightMbStrtolower  662  665  674  706
arrayMultisort             152  153  156  165
weightCallback function    218  220  223  241
weightCallback closure     458  462  471  494
weightsCallback function   144  145  149  154
schwartzian (FLAWED!!)     140  141  144  156

It should be noted that the first one, itemsByWeight(), while it looks great, will not work correctly in all cases, because it puts different uppercase / lowercase variations of a string into distinct groups, thus destroying the initial order.
Also the Schwartzian transform solution (google it!) does not behave accurately, because it does not allow any sort flags other than SORT_REGULAR. This is because it compares arrays, not strings or integers.

From those options that actually work, array_multisort() is a clear winner.

Sort by string weight, case insensitive
php bench/run-strtolower.php
Comparing sort by weight functions that sort by string weight with SORT_NATURAL, case insensitively.
Precise implementations can be seen in the git tag.
Here 50% of items have distinct string weights at $item['x'], but the other 50% of items have $item['x'] === 'nn'.

                           25%  50%  75%  90%
itemsByWeight (FLAWED!!)               97   97   98  100
itemsByWeightStrtolower               153  154  155  157
itemsByWeightMbStrtolower             548  553  576  583
arrayMultisort                        139  140  141  144
weightCallback_callUserFunc function  278  279  281  284
weightCallback function               210  211  212  216
weightCallback_callUserFunc closure   535  538  541  555
weightCallback closure                454  456  459  463
weightsCallback function              130  131  132  135
schwartzian (FLAWED!!)                149  150  151  154

It can be seen that the grouping solution (itemsByWeight) is faster if a lot of items have the same (string) weight.
If they don't, then array_multisort() is faster.

Other interesting findings:
- When using a callback, a function name is much faster than a closure. Funny, eh?
- A callback that computes all weights at once is faster than one that we have to call in every iteration. Not really surprising I'd say..
- Using call_user_func($weight_callback, $item) is slower than calling the callback directly with $weight_callback($item). But the latter does not work for some callback types.

But either way, array_multisort() is the best of those options that actually work.

Making the array_multisort() option slightly faster using array_combine():
https://github.com/donquixote/stable/blob/drupal-org-2757207-18-faster-m...

  public static function sortByWeightKey_arrayMultisort_arrayCombine(array $items_unsorted, $weight_key, $sort_flags = null) {

    $neutral_value = self::sortFlagsGetNeutralValue($sort_flags);

    $weights_by_key = [];
    foreach ($items_unsorted as $k => $item) {
      $weights_by_key[$k] = isset($item[$weight_key])
        ? $item[$weight_key]
        : $neutral_value;
    }

    $keys = array_keys($items_unsorted);
    $range = range(1, count($items_unsorted));
    array_multisort($weights_by_key, SORT_ASC, $sort_flags, $range, SORT_ASC, $keys, $items_unsorted);

    return array_combine($keys, $items_unsorted);
  }

Output of bench/run.php:

                              25%   50%   75%   90%
itemsByWeight_isArray         153   154   155   158
itemsByWeight                  68    69    69    70
keysByWeight                   94    94    95    96
weightWithFraction            113   114   114   116
arrayMultisort                113   113   114   116
arrayMultisort_arrayCombine   102   102   103   104
backdrop (NOT STABLE!)       1912  1920  1928  1940

There is a clear improvement from sortByWeightKey_arrayMultisort() to sortByWeightKey_arrayMultisort_arrayCombine().

static methods should be used sparingly

There is a place and a time for everything...

Really I don't think a component like this should be injected.
The sort functions do not depend on anything dynamic, and there is little reason why any component would want a different sort implementation assigned dynamically.

Knowing which sort implementation is being used makes this entire system more predictable, which is good.

If we want injectable sorts that actually make sense, I would suggest something very different:

interface SortInterface {
  function sort(array $items_unsorted) : array;
}
class MySort {
  function sort(array $items_unsorted) : array {
    return StableSort::sortByWeightKey($items_unsorted, 'weight', SORT_NUMERIC, SORT_ASC);
  }
}

This would allow a configurable / pluggable sort order for various components. E.g. one could decide that entity types should be sorted alphabetically, but backwards. Or by their string length.

I currently do not see a valid use case for this. But at least it provides actual value.

The implementation can still live in the static methods. Or.. it does not matter.

----

Imo a class should be designed either to be used statically, or to be instantiated, but not both.
And if it is designed to be instantiated, then it should look very different from what is being proposed here.

I'd have to override that constructor again

Well you can't, it is final :)

sortByWeightKey_fractionStable

Isn't this largely the same as the existing sortByWeightKey_weightWithFraction()?
https://github.com/donquixote/stable/blob/drupal-org-2757207-18-faster-m...
In #18 this has the same performance as array_multisort(), but is less flexible. So maybe just use array_multisort instead?

Gives the following by your benchmark.

It would be more meaningful to actually compare this to something else :)
Ideally start with the git tag from #18, it has a nicer way of showing benchmark results.

If you can get faster than array_multisort(), then your proposal shall be considered! We could check the sort flags, and then choose the implementation that is fastest / suitable for the given sort flags.

It does solve the issue with casting weights to strings, and decimals not being equal.

True. It does prevent unstableness with e.g. '00.1' vs '0.1' vs '.1' vs '.100'.
But so does array_multisort(). So it has to be faster than array_multisort() to be considered an option.

You could try (string) floatval($weight)?

I'm afraid this will kill the performance benefit of the grouping. And sometimes float gives us fraction dirt.
And this means we need different code for SORT_NUMERIC and other sorts.

------

Btw I just realized that SORT_NATURAL, which I suppose uses the same comparison as strnatcmp(), also breaks stability with the grouping, even without SORT_FLAG_CASE. Because e.g. strnatcmp('0', '00') === 0, see https://3v4l.org/1V8MK.

Maybe we have to ditch the grouping altogether, and use array_multisort() in all cases.

Following your floatval() suggestion:
https://github.com/donquixote/stable/blob/drupal-org-2757207-22-float/sr...

                              25%   50%   75%   90%
itemsByWeight_isArray         130   130   131   131
itemsByWeight                  66    66    67    67
itemsByWeight_floatval        108   109   109   110
itemsByWeight_castFloat        79    80    80    81
keysByWeight                   93    94    94    95
weightWithFraction            106   107   107   108
arrayMultisort                112   112   113   113
arrayMultisort_arrayCombine   101   102   102   103
arrayMultisort_arrayReplace   102   103   103   104
backdrop (NOT STABLE!)       1898  1903  1911  1933

floatval() is expensive, but (float) is cheap.
I did not encounter any float dirt effects. I don't really know when these occur.
So it shall be

        $items_by_weight[(string)(float)$item[$weight_key]][$k] = $item;

https://github.com/donquixote/stable/blob/drupal-org-2757207-23-keys-mul...

With multiple keys, array_multisort() are sometimes faster, sometimes slower than the grouping solution.
But the results are quite "jumpy".. See

                4%  10%  25%  50%  75%  90%  96%
itemsByWeight  197  208  223  244  260  276  281
multisort      229  229  231  234  237  242  245

vs

                4%  10%  25%  50%  75%  90%  96%
itemsByWeight  236  238  243  257  266  425  443
multisort      229  231  232  234  240  390  392

Also it depends on how many items have the same weight.

I would say let's array_multisort() is generally preferable, because it is fast enough, and more reliable and versatile than other options.
The other solution might be ok for edge cases.

Patch contains the same StableSort class as in #2759479-25: Proof of concept: Replace uasort() with dedicated stable-sort-by-weight functions, where possible, but for 8.1.x, and without the changes to other code.

Example for fluid API:
https://github.com/donquixote/stable/blob/drupal-org-2757207-27-fluid-AP...
(The tag still contains all the benchmark stuff and the demo implementations, which should be disregarded this time.)

SortInterface:
https://github.com/donquixote/stable/blob/drupal-org-2757207-27-fluid-AP...

    // Create a sort.
    $sort = Sort_Multi::begin()
      ->byWeightKey('weight', SORT_NUMERIC)
      ->byWeightKey(1, SORT_STRING);

    // Then use it.
    $items_sorted = $sort->itemsGetSorted($items_unsorted);

    // By-reference syntax is also supported:
    $items = $items_unsorted;
    $sort->sort($items);
    $items_sorted = $items;

    // Without preserving keys:
    $items_sorted = $sort->itemsGetSorted($items_unsorted, false);

    // Create another sort, and sort immediately.
    $objects_sorted = Sort_Multi::begin()
      ->byWeightCallback(
        function(array $item) {
          return $item->getWeight();
        },
        SORT_NUMERIC)
      ->byWeightMethod('getTItle', SORT_STRING)
      ->byWeightProperty('status', SORT_NUMERIC)
      ->sort($objects_unsorted);

    // Sorts are immutable. Builder methods return modified clones.
    assert($sort !== $sort->byWeightKey('provider'));

Likely this has some performance overhead compared to the static methods, due to indirection and a bit of extra class loading.
But most of this overhead should be O(1) (constant), or maybe some of it O(n) (linear), because most of the indirect calls and builder operations happen at most once per sort operation.

Sort objects can be cached at runtime, which means that some possibly expensive decisions now only happen once per request, instead of once per sort operation.

This said: So far I am not planning to make this stuff part of Drupal, unless others specifically ask for it.