Improve MergeStreamIterator performance by using TimSort

[sandrokeil]

I figured out really slow performance with the comparison function in the MergeStreamIterator class. Our event store benchmarks needs dozens of minutes to complete the benchmark.

I've added a unit test and it shows that the TimSort is faster (857 ms vs. 1.44 seconds) than the current implementation. You can check it if you replace the prioritizeIterators method with the old implementation (adapted to the new structure).

private function prioritizeIterators(): void
{
    $compareValue = function (\Iterator $iterator): \DateTimeImmutable {
        /** @var Message $message */
        $message = $iterator->current();

        return $message->createdAt();
    };

    $compareFunction = function ($a, $b) use ($compareValue) {
        // valid iterators should be prioritized over invalid ones
        if (! $a[0]->valid() || ! $b[0]->valid()) {
            return $b[0]->valid() <=> $a[0]->valid();
        }

        return $compareValue($a[0]) <=> $compareValue($b[0]);
    };

    if ($this->numberOfIterators > 1) {
        \usort($this->iterators, $compareFunction);
    }
}

TimSort implementation was taken from GeeksforGeeks. A sort algorithm comparison can be found here.

/cc @prolic @basz @codeliner

Benchmark files: postgres12_timsort.log postgres12_usort.log postgres_without_merge_stream_iterator.log arangodb_3_6.log

[coveralls]

Coverage increased (+0.02%) to 99.498% when pulling d667e8a64c481a6db3a7c81e6b2b301c7e3dd087 on feature/timsort-merge-stream-iterator into e8cc75e74b9caf325da358750c7375e08620f59b on 7.x.

[sandrokeil]

There is something weird with the benchmark results, in particular case with the projectorsall result.

[sandrokeil]

Now we have some evidence with the benchmark.

\ProophBench\EventStore\MergedStreamIteratorBench

    sorted..................................I2 [μ Mo]/r: 808.02911 806.24938 (ms) [μSD μRSD]/r: 6.977ms 0.86%
    shuffled................................I2 [μ Mo]/r: 820.07822 820.59582 (ms) [μSD μRSD]/r: 8.370ms 1.02%
    shuffledDate............................I2 [μ Mo]/r: 809.53878 808.60318 (ms) [μSD μRSD]/r: 12.604ms 1.56%
    shuffledStreams.........................I2 [μ Mo]/r: 811.36589 802.78085 (ms) [μSD μRSD]/r: 14.949ms 1.84%
    sortedUsort.............................I2 [μ Mo]/r: 1,339.90411 1,325.15408 (ms) [μSD μRSD]/r: 31.085ms 2.32%
    shuffledUsort...........................I2 [μ Mo]/r: 1,329.95511 1,345.39639 (ms) [μSD μRSD]/r: 27.104ms 2.04%
    shuffledDateUsort.......................I2 [μ Mo]/r: 1,274.04811 1,282.46054 (ms) [μSD μRSD]/r: 14.642ms 1.15%
    shuffledStreamsUsort....................I2 [μ Mo]/r: 1,354.29033 1,344.14198 (ms) [μSD μRSD]/r: 17.678ms 1.31%

8 subjects, 24 iterations, 24 revs, 0 rejects, 0 failures, 0 warnings
(best [mean mode] worst) = 794,287.333 [1,068,401.208 1,066,922.778] 816,948.333 (μs)
⅀T: 25,641,629.000μs μSD/r 16,676.115μs μRSD/r: 1.512%
suite: 1343d0c9e8ad3cf2a6d97a9a45bf225743d67082, date: 2020-07-16, stime: 17:47:39
+---------------------------+----------------------+-------------+---------------+---------------+-------+
| benchmark                 | subject              | mem_peak    | mean          | best          | diff  |
+---------------------------+----------------------+-------------+---------------+---------------+-------+
| MergedStreamIteratorBench | sorted               | 11,061,547b | 808.02911ms   | 799.91667ms   | 1.00x |
| MergedStreamIteratorBench | shuffledDate         | 11,061,587b | 809.53878ms   | 794.28733ms   | 1.00x |
| MergedStreamIteratorBench | shuffledStreams      | 11,061,587b | 811.36589ms   | 799.49133ms   | 1.00x |
| MergedStreamIteratorBench | shuffled             | 11,061,421b | 820.07822ms   | 809.72400ms   | 1.01x |
| MergedStreamIteratorBench | shuffledDateUsort    | 11,061,469b | 1,274.04811ms | 1,253.38033ms | 1.58x |
| MergedStreamIteratorBench | shuffledUsort        | 11,061,461b | 1,329.95511ms | 1,291.79033ms | 1.65x |
| MergedStreamIteratorBench | sortedUsort          | 11,061,336b | 1,339.90411ms | 1,307.89567ms | 1.66x |
| MergedStreamIteratorBench | shuffledStreamsUsort | 11,061,469b | 1,354.29033ms | 1,340.66833ms | 1.68x |
+---------------------------+----------------------+-------------+---------------+---------------+-------+

So I'm not sure why the event store benchmark of the all projector leads to a different result.

[basz]

well, faster is better... nice