Description of flat implementations and recommendation

[PhrozenByte]

First of all: Great project! 👍

However, I've a bit trouble to comprehend why FixedArraySort is the recommended implementation. According to the benchmarks in your README.md (and my own benchmarks I run with PHP 5.6), ArraySort always wins against FixedArraySort. The execution times are virtually identical (between -1% and +2,5% difference), whereas FixedArraySort has a significant higher memory footprint (up to +30%).

The Implementations section of the non-grouped storages generally doesn't seem to match the benchmarks: You say that \SplFixedArray is "much more memory friendly" compared to plain PHP arrays, but \SplFixedArray always has a higher memory footprint. The string implementation is described as storage with "no array overhead" and as "a bit faster and [..] almost equal memory footprint". This doesn't seem to be true either, it's actually both slower and more memory-intensive as the other implementations.

Do I miss something here?

[marcj]

I updated lately the benchmarks with a new script (using php7) and haven't obviously updated the description/recommendation above :)

I guess I also need to run the benchmark with PHP 5.6 to see which implementation is there faster.

[PhrozenByte]

fyi (Debian Jessie):

$ php --version
PHP 5.6.27-0+deb8u1 (cli) (built: Oct 15 2016 15:53:28)

$ ./bin/console benchmark
 5/5 [============================] 100%
+-----------+----------------+--------------+-----------+
| Count     | Implementation | Memory       | Duration  |
+-----------+----------------+--------------+-----------+
| 50        | FixedArraySort |       5,936b | 0.0009s   |
| 50        | ArraySort      |       5,640b | 0.0006s   |
| 50        | StringSort     |      11,904b | 0.0006s   |
| 1,000     | FixedArraySort |      97,320b | 0.0151s   |
| 1,000     | ArraySort      |      89,520b | 0.0119s   |
| 1,000     | StringSort     |     188,936b | 0.0108s   |
| 10,000    | FixedArraySort |     205,160b | 0.1298s   |
| 10,000    | ArraySort      |     125,080b | 0.1357s   |
| 10,000    | StringSort     |   1,105,496b | 0.1366s   |
| 100,000   | FixedArraySort |           0b | 2.1303s   |
| 100,000   | ArraySort      |           0b | 2.0611s   |
| 100,000   | StringSort     |   8,738,168b | 2.1189s   |
| 1,000,000 | FixedArraySort |           0b | 99.5372s  |
| 1,000,000 | ArraySort      |           0b | 107.2257s |
| 1,000,000 | StringSort     |  86,337,728b | 97.0378s  |
+-----------+----------------+--------------+-----------+
 5/5 [============================] 100%
+-----------+-------------------+--------------+-----------+
| Count     | Implementation    | Memory       | Duration  |
+-----------+-------------------+--------------+-----------+
| 50        | GroupedArraySort  |      11,352b | 0.0013s   |
| 50        | GroupedStringSort |      12,896b | 0.0011s   |
| 1,000     | GroupedArraySort  |     125,640b | 0.0271s   |
| 1,000     | GroupedStringSort |     176,440b | 0.0255s   |
| 10,000    | GroupedArraySort  |     504,888b | 1.3000s   |
| 10,000    | GroupedStringSort |     798,608b | 0.2385s   |
| 100,000   | GroupedArraySort  |   2,746,160b | 406.1090s |
| 100,000   | GroupedStringSort |   5,676,032b | 3.5799s   |
| 1,000,000 | GroupedStringSort |  57,340,688b | 159.0948s |
+-----------+-------------------+--------------+-----------+

[s4mr0n1]

Hi Nice Development TopSort.. is there any Topsort and DAG Shortest Path to calculating time travel thank ?