Making Symfony router lightning fast - 2/2
In Making Symfony’s Router 77.7x faster - 1/2, we learned how to build a faster URL matcher, using hash-map lookups for static routes, and combined regular expressions for routes with placeholders, while preserving all the advanced features of the Symfony router. However, more work was needed for some real world apps, as at least one of them experienced a slow down. Let’s see how fixing this provided us with (one of) the fastest PHP routers out there.
First and foremost, there is no faster way to match a static route than a hash-map lookup. This means this case is solved; I’m going to focus on non-static routes in the rest of the article.
Reclaiming the perf loss
The benchmark I worked on first was pretty simple: it generated 400 routes with /abc{foo}/123-like patterns, the trailing number going from 0 to 399. Matching URL /abc399/399 topped at 154k match/s. (a bit faster than our reference and inspiration, FastRoute, at 65k match/s.). The generated regular expression looked like this in both matchers (boundaries and marks removed for clarity, see previous article):
|/abc([^/]++)/0
|/abc([^/]++)/1
...
|/abc([^/]++)/399When I looked at the other real-world route collection that was having this slow down, here is what I found (with paths and repetitions ellipsed):
|(?i:go\.example\.com)/path1...
|(?i:go\.example\.com)/path2...
...
|(?i:widget\.example\.com)/path11...
|(?i:widget\.example\.com)/path12...
|(?i:widget\.example\.com)/path13...
...
|(?i:go\.example\.com)/path42...
|(?i:go\.example\.com)/path43...
|(?i:go\.example\.com)/path44...
...
|[^/]*+/path56...
...
|(?i:go\.example\.com)/path62...
...
|(?i:admin\.example\.com)/path123...
|[^/]*+/path124...
...This collection contains about 200 non-static routes, with alternating host-based matching. Most routing packages don’t handle host-based constraints, so we cannot have any reference benchmark here. Still, there is a pretty obvious thing to do; group same-host sequences together:
|(?i:go\.example\.com)(?
|/path1...
|/path2...
|...
)
|(?i:widget\.example\.com)(?
|/path11...
|/path12...
|/path13...
|...
)
|(?i:go\.example\.com)(?
|/path42...
|/path43...
|/path44...
|...
)
|[^/]*+(?
|/path56...
|...
)
|(?i:go\.example\.com)(?
|/path62...
|...
)
|(?i:admin\.example\.com)(?
|/path123...
)
|[^/]*+(?
|/path124...
|...
)This should allow the PCRE engine to do less backtracking (i.e. restarting back from root when a route doesn’t match.) And it worked! Well, at least we reclaimed the perf loss. Matching with this regex provided us a little bit faster matcher than we had before any of the new optimizations. Not what I’d call a success yet, but still, we learned something interesting: grouping by common prefix pays off.
Going lightning fast
When working on a codebase like Symfony’s, you can be pretty sure that many minds already looked at the code, and made it handle complex situations pretty well. On the Routing component, a significant perf boost was provided by Frank de Jonge, in a PR that added same-prefix route re-ordering and grouping. As it didn’t fit the new optimizations, I had to drop the code. From Frank’s Twitter timeline:
Looks like all the code I wrote for @symfony’s routing will soon be replaced by @nicolasgrekas’s new FastRoute inspired code. 🤘 #killYourDarlings
But as you might have understood already, this isn’t the case anymore: this same-prefix route re-ordering and grouping logic is exactly what we need! I “just” had to make it handle same-subpatterns. Basically, what we do is looping through our collection of routes, and before appending them to the list, we check if they can be merged with any of the previous ones, while preserving the in-order requirement. Here is what this looks like on our initial bench case:
|/abc([^/]++)(?
|/0
|/1(?
|
|0(?
|
|0
|1
|2
... ... ...
|/3(?
...
|9(?
...
|9
)
)
)Can you see? The common prefix and placeholder need to be matched only once, then the remaining is dumped as a tree of common prefixes, and route .../100 has moved next to routes .../1 and .../10. Another example is this simple routing table, extracted from the Symfony Demo app. Instead of this:
|/(en|fr)/admin/post/?
|/(en|fr)/admin/post/new
|/(en|fr)/admin/post/(\d+)
|/(en|fr)/admin/post/(\d+)/edit
|/(en|fr)/admin/post/(\d+)/delete
|/(en|fr)/blog/?
|/(en|fr)/blog/rss\.xml
|/(en|fr)/blog/page/([^/]++)
|/(en|fr)/blog/posts/([^/]++)
|/(en|fr)/blog/comment/(\d+)/new
|/(en|fr)/blog/search
|/(en|fr)/login
|/(en|fr)/logout
|/(en|fr)?We now generate:
|/(en|fr)(?
|/admin/post(?
|/?
|/new
|/(\d+)(?
|
|/edit
|/delete
)
)
|/blog(?
|/?
|/rss\.xml
|/p(?
|age/([^/]++)
|osts/([^/]++)
)
|/comments/(\d+)/new
|/search
)
|/log(?
|in
|out
)
)
|/(en|fr)?It might be a bit less readable for sure, but how much faster are we now? Using the simple benchmark from the beginning, matching the /abc399/399 URL 10k times takes just 10ms. That’s 1 million match/s.! That’s also 15x faster than FastRoute, and 77.7x faster than our best starting mark before any optimizations.
The “same-prefix route re-ordering and grouping” logic is also applied from right-to-left to host-suffixes. Job done :)
End of the story — part 2/2
If you want to look at the pull requests that provided this two-orders-of-magnitude improvement (and almost 400x for static ones by the way), here they are: #26059 and #26208, with a fix in between to handle very large sets of routes in #26169.
Does Symfony have the fastest PHP router out there? That’s likely possible as the margin between static routes and non-static ones is now quite thin (from 2ms to 10ms for 10k matches). Fred Emmott from Facebook reported an interesting approach they’re using in HHVM’s router: instead of big regular expressions, they split them by same static prefix. This frees PCRE from wondering about this prefix, but misses the tree of same-subpatterns we’re building right into the regex. Other people reported that there are routers out there that positively compare to FastRoute, so it might be worth doing more benchmarks. I’ll let these questions open for someone else. Please keep me posted if you manage to gain another order of magnitude, I’d be thrilled to know how you did it!
Symfony has always walked the line between academic design and being pragmatic. These optimizations show that those worlds can nicely co-exist. In this case, a well defined interface (UrlMatcherInterface) allowed for some pretty cool optimizations at the famous “implementation detail” level. Upgrading to Symfony 4.1 is all you’ll have to do to benefit from them.
Even if most of us don’t need this level of performance, some do, and it’s nice to know the limit is not going to be your dependencies any time soon, isn’t it?
P.S.: please Retweet if you liked this article, and don’t hesitate to follow me on Twitter, GitHub and/or here on Medium. ;-) Thanks for reading.
