FastRoute icon indicating copy to clipboard operation
FastRoute copied to clipboard

Published 20 hours ago • verified publisher icon nikic

Implement new dispatcher

Open lcobucci opened this issue 4 years ago • 4 comments

More info will be coming soon...

  • [ ] Improve data generation performance
  • [ ] Generate multiple regexes instead of only 1 (using 2.5k char as limit - according to some tests that's the best regex size for handling first and last scenarios on a collection of over 4k routes)
  • [ ] Fix broken test

lcobucci avatar Jul 06 '21 22:07 lcobucci

Even though there's a broken test, the preliminary benchmarks are interesting:

+-----------------+--------------------+-----------------------------+----------+----------+---------+
| benchmark       | subject            | set                         | mem_peak | mode     | rstdev  |
+-----------------+--------------------+-----------------------------+----------+----------+---------+
| RealLifeExample | benchStaticRoutes  | mark,invalid-method         | 1.488mb  | 1.369μs  | ±1.71%  |
| RealLifeExample | benchStaticRoutes  | compact_mark,invalid-method | 1.488mb  | 0.479μs  | ±3.52%  |
| RealLifeExample | benchDynamicRoutes | mark,first                  | 1.490mb  | 0.725μs  | ±5.40%  |
| RealLifeExample | benchDynamicRoutes | compact_mark,first          | 1.490mb  | 0.765μs  | ±5.47%  |
| RealLifeExample | benchDynamicRoutes | mark,last                   | 1.490mb  | 0.859μs  | ±5.36%  |
| RealLifeExample | benchDynamicRoutes | compact_mark,last           | 1.490mb  | 0.783μs  | ±3.32%  |
| RealLifeExample | benchDynamicRoutes | mark,invalid-method         | 1.488mb  | 1.706μs  | ±3.60%  |
| RealLifeExample | benchDynamicRoutes | compact_mark,invalid-method | 1.488mb  | 0.889μs  | ±2.10%  |
| RealLifeExample | benchOtherRoutes   | mark,non-existent           | 1.486mb  | 1.610μs  | ±3.48%  |
| RealLifeExample | benchOtherRoutes   | compact_mark,non-existent   | 1.486mb  | 0.547μs  | ±10.94% |
| RealLifeExample | benchOtherRoutes   | mark,longest-route          | 1.491mb  | 1.281μs  | ±3.63%  |
| RealLifeExample | benchOtherRoutes   | compact_mark,longest-route  | 1.491mb  | 1.167μs  | ±2.70%  |
| ManyRoutes      | benchStaticRoutes  | mark,invalid-method         | 4.783mb  | 2.502μs  | ±2.89%  |
| ManyRoutes      | benchStaticRoutes  | compact_mark,invalid-method | 4.783mb  | 0.452μs  | ±2.10%  |
| ManyRoutes      | benchDynamicRoutes | mark,first                  | 4.785mb  | 0.773μs  | ±18.04% |
| ManyRoutes      | benchDynamicRoutes | compact_mark,first          | 4.785mb  | 0.767μs  | ±9.49%  |
| ManyRoutes      | benchDynamicRoutes | mark,last                   | 4.785mb  | 18.009μs | ±14.61% |
| ManyRoutes      | benchDynamicRoutes | compact_mark,last           | 4.785mb  | 1.078μs  | ±2.90%  |
| ManyRoutes      | benchDynamicRoutes | mark,invalid-method         | 4.783mb  | 16.582μs | ±2.63%  |
| ManyRoutes      | benchDynamicRoutes | compact_mark,invalid-method | 4.783mb  | 1.057μs  | ±8.79%  |
| ManyRoutes      | benchOtherRoutes   | mark,non-existent           | 4.782mb  | 2.893μs  | ±11.39% |
| ManyRoutes      | benchOtherRoutes   | compact_mark,non-existent   | 4.782mb  | 0.405μs  | ±3.05%  |
+-----------------+--------------------+-----------------------------+----------+----------+---------+

lcobucci avatar Jul 06 '21 22:07 lcobucci

Any news?

iAxel avatar May 17 '22 14:05 iAxel

@iAxel thanks for showing interest here!

I've changed the implementation and improved the registration performance a bit. However, I've noticed that the new strategy might not have that big of an impact on PHP 8.1+.

Here's the diff between 7.4 and 8.1

 +----------------------+-------------------+-----------------------------+------+-----+----------+-----------+
 | benchmark            | subject           | set                         | revs | its | mem_peak | mode      |
 +----------------------+-------------------+-----------------------------+------+-----+----------+-----------+
-| RealLifeExampleBench | staticRoutes      | mark,first                  | 500  | 5   | 1.487mb  | 0.330μs   |
+| RealLifeExampleBench | staticRoutes      | mark,first                  | 500  | 5   | 1.313mb  | 0.044μs   |
-| RealLifeExampleBench | staticRoutes      | compact_mark,first          | 500  | 5   | 1.487mb  | 0.226μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,first          | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | staticRoutes      | mark,last                   | 500  | 5   | 1.487mb  | 0.246μs   |
+| RealLifeExampleBench | staticRoutes      | mark,last                   | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | staticRoutes      | compact_mark,last           | 500  | 5   | 1.487mb  | 0.236μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,last           | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | staticRoutes      | mark,invalid-method         | 500  | 5   | 1.487mb  | 1.569μs   |
+| RealLifeExampleBench | staticRoutes      | mark,invalid-method         | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 1.487mb  | 0.477μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,first                  | 500  | 5   | 1.487mb  | 0.734μs   |
+| RealLifeExampleBench | dynamicRoutes     | mark,first                  | 500  | 5   | 1.313mb  | 0.049μs   |
-| RealLifeExampleBench | dynamicRoutes     | compact_mark,first          | 500  | 5   | 1.487mb  | 0.868μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,first          | 500  | 5   | 1.313mb  | 0.047μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,last                   | 500  | 5   | 1.487mb  | 0.982μs   |
+| RealLifeExampleBench | dynamicRoutes     | mark,last                   | 500  | 5   | 1.313mb  | 0.044μs   |
-| RealLifeExampleBench | dynamicRoutes     | compact_mark,last           | 500  | 5   | 1.487mb  | 0.864μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,last           | 500  | 5   | 1.313mb  | 0.045μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 1.487mb  | 1.846μs   |
+| RealLifeExampleBench | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 1.487mb  | 1.007μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 1.313mb  | 0.047μs   |
-| RealLifeExampleBench | otherRoutes       | mark,non-existent           | 500  | 5   | 1.487mb  | 1.666μs   |
+| RealLifeExampleBench | otherRoutes       | mark,non-existent           | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 1.487mb  | 0.563μs   |
+| RealLifeExampleBench | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | otherRoutes       | mark,longest-route          | 500  | 5   | 1.487mb  | 1.294μs   |
+| RealLifeExampleBench | otherRoutes       | mark,longest-route          | 500  | 5   | 1.313mb  | 0.048μs   |
-| RealLifeExampleBench | otherRoutes       | compact_mark,longest-route  | 500  | 5   | 1.487mb  | 1.235μs   |
+| RealLifeExampleBench | otherRoutes       | compact_mark,longest-route  | 500  | 5   | 1.313mb  | 0.048μs   |
-| RealLifeExampleBench | routeRegistration | mark                        | 500  | 5   | 1.486mb  | 83.131μs  |
+| RealLifeExampleBench | routeRegistration | mark                        | 500  | 5   | 1.312mb  | 86.458μs  |
-| RealLifeExampleBench | routeRegistration | compact_mark                | 500  | 5   | 1.486mb  | 128.557μs |
+| RealLifeExampleBench | routeRegistration | compact_mark                | 500  | 5   | 1.312mb  | 133.035μs |
-| ManyRoutesBench      | staticRoutes      | mark,first                  | 500  | 5   | 4.799mb  | 0.272μs   |
+| ManyRoutesBench      | staticRoutes      | mark,first                  | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | staticRoutes      | compact_mark,first          | 500  | 5   | 4.799mb  | 0.236μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,first          | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | staticRoutes      | mark,last                   | 500  | 5   | 4.799mb  | 0.249μs   |
+| ManyRoutesBench      | staticRoutes      | mark,last                   | 500  | 5   | 4.850mb  | 0.047μs   |
-| ManyRoutesBench      | staticRoutes      | compact_mark,last           | 500  | 5   | 4.799mb  | 0.236μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,last           | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | staticRoutes      | mark,invalid-method         | 500  | 5   | 4.799mb  | 2.928μs   |
+| ManyRoutesBench      | staticRoutes      | mark,invalid-method         | 500  | 5   | 4.850mb  | 0.051μs   |
-| ManyRoutesBench      | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 4.799mb  | 0.449μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,first                  | 500  | 5   | 4.800mb  | 0.691μs   |
+| ManyRoutesBench      | dynamicRoutes     | mark,first                  | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | dynamicRoutes     | compact_mark,first          | 500  | 5   | 4.800mb  | 0.672μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,first          | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,last                   | 500  | 5   | 4.800mb  | 16.407μs  |
+| ManyRoutesBench      | dynamicRoutes     | mark,last                   | 500  | 5   | 4.850mb  | 0.044μs   |
-| ManyRoutesBench      | dynamicRoutes     | compact_mark,last           | 500  | 5   | 4.800mb  | 1.038μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,last           | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 4.799mb  | 16.562μs  |
+| ManyRoutesBench      | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 4.850mb  | 0.047μs   |
-| ManyRoutesBench      | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 4.799mb  | 1.038μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | otherRoutes       | mark,non-existent           | 500  | 5   | 4.799mb  | 2.812μs   |
+| ManyRoutesBench      | otherRoutes       | mark,non-existent           | 500  | 5   | 4.850mb  | 0.049μs   |
-| ManyRoutesBench      | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 4.799mb  | 0.466μs   |
+| ManyRoutesBench      | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | routeRegistration | mark                        | 500  | 5   | 1.486mb  | 13.203ms  |
+| ManyRoutesBench      | routeRegistration | mark                        | 500  | 5   | 1.351mb  | 12.065ms  |
-| ManyRoutesBench      | routeRegistration | compact_mark                | 500  | 5   | 1.846mb  | 17.853ms  |
+| ManyRoutesBench      | routeRegistration | compact_mark                | 500  | 5   | 1.843mb  | 17.277ms  |

Comparing mark and compact_mark in PHP 8.1 doesn't show relevant improvements:

 +----------------------+-------------------+-----------------------------+------+-----+----------+-----------+
 | benchmark            | subject           | set                         | revs | its | mem_peak | mode      |
 +----------------------+-------------------+-----------------------------+------+-----+----------+-----------+
-| RealLifeExampleBench | staticRoutes      | mark,first                  | 500  | 5   | 1.313mb  | 0.044μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,first          | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | staticRoutes      | mark,last                   | 500  | 5   | 1.313mb  | 0.050μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,last           | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | staticRoutes      | mark,invalid-method         | 500  | 5   | 1.313mb  | 0.050μs   |
+| RealLifeExampleBench | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 1.313mb  | 0.050μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,first                  | 500  | 5   | 1.313mb  | 0.049μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,first          | 500  | 5   | 1.313mb  | 0.047μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,last                   | 500  | 5   | 1.313mb  | 0.044μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,last           | 500  | 5   | 1.313mb  | 0.045μs   |
-| RealLifeExampleBench | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 1.313mb  | 0.046μs   |
+| RealLifeExampleBench | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 1.313mb  | 0.047μs   |
-| RealLifeExampleBench | otherRoutes       | mark,non-existent           | 500  | 5   | 1.313mb  | 0.046μs   |
+| RealLifeExampleBench | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 1.313mb  | 0.046μs   |
-| RealLifeExampleBench | otherRoutes       | mark,longest-route          | 500  | 5   | 1.313mb  | 0.048μs   |
+| RealLifeExampleBench | otherRoutes       | compact_mark,longest-route  | 500  | 5   | 1.313mb  | 0.048μs   |
-| RealLifeExampleBench | routeRegistration | mark                        | 500  | 5   | 1.312mb  | 86.458μs  |
+| RealLifeExampleBench | routeRegistration | compact_mark                | 500  | 5   | 1.312mb  | 133.035μs |
-| ManyRoutesBench      | staticRoutes      | mark,first                  | 500  | 5   | 4.850mb  | 0.048μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,first          | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | staticRoutes      | mark,last                   | 500  | 5   | 4.850mb  | 0.047μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,last           | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | staticRoutes      | mark,invalid-method         | 500  | 5   | 4.850mb  | 0.051μs   |
+| ManyRoutesBench      | staticRoutes      | compact_mark,invalid-method | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,first                  | 500  | 5   | 4.850mb  | 0.048μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,first          | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,last                   | 500  | 5   | 4.850mb  | 0.044μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,last           | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | dynamicRoutes     | mark,invalid-method         | 500  | 5   | 4.850mb  | 0.047μs   |
+| ManyRoutesBench      | dynamicRoutes     | compact_mark,invalid-method | 500  | 5   | 4.850mb  | 0.050μs   |
-| ManyRoutesBench      | otherRoutes       | mark,non-existent           | 500  | 5   | 4.850mb  | 0.049μs   |
+| ManyRoutesBench      | otherRoutes       | compact_mark,non-existent   | 500  | 5   | 4.850mb  | 0.048μs   |
-| ManyRoutesBench      | routeRegistration | mark                        | 500  | 5   | 1.351mb  | 12.065ms  |
+| ManyRoutesBench      | routeRegistration | compact_mark                | 500  | 5   | 1.843mb  | 17.277ms  |

Running a comparison between FastRoute-mark, FastRoute-compact_mark, and Symfony (on PHP 8.1) still show some interesting results, though:

New router, cached data

+---------------------------------- Benchmark results for group cached. -----------------+-----------------+
| Case                                  | Scenario           | Routes | Time             | Per Second      |
+---------------------------------------+--------------------+--------+------------------+-----------------+
| fast-route(compact-mark):cached(file) | benchAll           | 364    | 0.001297 seconds | 280648.28235294 |
| symfony:cached(file)                  | benchAll           | 364    | 0.002014 seconds | 180741.87948384 |
| fast-route(mark):cached(file)         | benchAll           | 364    | 0.002934 seconds | 124053.51881043 |

| fast-route(compact-mark):cached(file) | benchLast          | 300    | 0.001274 seconds | 235502.75126334 |
| symfony:cached(file)                  | benchLast          | 300    | 0.001833 seconds | 163648.22473664 |
| fast-route(mark):cached(file)         | benchLast          | 300    | 0.002405 seconds | 124743.84851789 |

| fast-route(compact-mark):cached(file) | benchLongest       | 300    | 0.030557 seconds | 9817.6677121857 |
| symfony:cached(file)                  | benchLongest       | 300    | 0.030979 seconds | 9684.0050794627 |
| fast-route(mark):cached(file)         | benchLongest       | 300    | 0.032826 seconds | 9139.0454885499 |

| fast-route(compact-mark):cached(file) | benchInvalidRoute  | 300    | 0.001164 seconds | 257740.92585007 |
| symfony:cached(file)                  | benchInvalidRoute  | 300    | 0.001415 seconds | 212011.99663016 |
| fast-route(mark):cached(file)         | benchInvalidRoute  | 300    | 0.002225 seconds | 134836.17659666 |

| fast-route(compact-mark):cached(file) | benchInvalidMethod | 300    | 0.001399 seconds | 214432.7198364  |
| symfony:cached(file)                  | benchInvalidMethod | 300    | 0.002353 seconds | 127499.36163745 |
| fast-route(mark):cached(file)         | benchInvalidMethod | 300    | 0.002470 seconds | 121456.67953668 |
+---------------------------------------+--------------------+--------+------------------+-----------------+

Cached router

+------------------------------- Benchmark results for group instance. --------------+-----------------+
| Case                              | Scenario           | Routes | Time             | Per Second      |
+-----------------------------------+--------------------+--------+------------------+-----------------+
| fast-route(mark):instance         | benchAll           | 364    | 0.000060 seconds | 6082576.3187251 |
| fast-route(compact-mark):instance | benchAll           | 364    | 0.000062 seconds | 5872025.6       |
| symfony:instance                  | benchAll           | 364    | 0.000567 seconds | 641751.43169399 |

| fast-route(mark):instance         | benchLast          | 300    | 0.000151 seconds | 1987821.8009479 |
| fast-route(compact-mark):instance | benchLast          | 300    | 0.000156 seconds | 1923992.6605505 |
| symfony:instance                  | benchLast          | 300    | 0.000548 seconds | 547559.2689295  |

| fast-route(mark):instance         | benchLongest       | 300    | 0.028400 seconds | 10563.40099733  |
| fast-route(compact-mark):instance | benchLongest       | 300    | 0.028807 seconds | 10414.162631906 |
| symfony:instance                  | benchLongest       | 300    | 0.029549 seconds | 10152.585970405 |

| fast-route(compact-mark):instance | benchInvalidMethod | 300    | 0.000167 seconds | 1797558.8571429 |
| fast-route(mark):instance         | benchInvalidMethod | 300    | 0.000206 seconds | 1456355.5555556 |
| symfony:instance                  | benchInvalidMethod | 300    | 0.001107 seconds | 271008.22743914 |

| fast-route(compact-mark):instance | benchInvalidRoute  | 300    | 0.000449 seconds | 668237.49336166 |
| fast-route(mark):instance         | benchInvalidRoute  | 300    | 0.000509 seconds | 589363.55971896 |
| symfony:instance                  | benchInvalidRoute  | 300    | 0.000520 seconds | 576668.74427131 |
+-----------------------------------+--------------------+--------+------------------+-----------------+

I'll continue exploring this over the next couple weeks.

lcobucci avatar May 23 '22 22:05 lcobucci

Thank you for your hard work, looking forward to more updates :)

iAxel avatar May 25 '22 12:05 iAxel

After exhaustive testing, I've concluded that we should rather require PHP 8.1 and abandon this new dispatcher. I'll close this PR, bring some of its improves to another one, and require PHP 8.1 for master.

lcobucci avatar Jul 27 '23 20:07 lcobucci

@lcobucci Sounds like the next release will bring some nice improvements. Looking forward to it! Thanks for your work on this.

binaryfire avatar Aug 01 '23 16:08 binaryfire