Building One of the Fastest PHP Routers
Disclaimer: Almost all PHP routing libraries are fast enough. They almost never are the bottleneck of your application, which means you should focus more on features of a router rather than speed. This is more just an interesting exploration of the algorithm behind Aphiria’s router.
Two years ago, I set out to build a PHP router. I had previously built one for Opulence, but was interested in additional functionality such as custom constraints that let you match on headers (useful for header-based API versioning). I wasn’t that interested in speed until I read Nikita Popov’s excellent breakdown of his regex-based library FastRoute. I initially adopted a very similar matching approach to FastRoute, but couldn’t shake an idea I thought might rival his algorithm — tree-based routing.
For example, let’s say I had the following routes in my API:
usersusers/:idusers/:id/avatarusers/:id/email
I wanted the following tree structure to be generated for matching:
In computer science, this data structure is called a “trie” (pronounced just like “tree”). Each node shares the same prefix as every other sibling node.
The algorithm
My algorithm uses depth-first search to find a matching path in the trie. For static, ie non-variable segments, I use a simple hash table for O(1) lookup for each segment and, if no match is found, I iterate over variable segments for a match, giving us O(n) where n is the number of variable nodes at that level of the trie. I keep descending the trie until I either find a match candidate or I don’t, resulting in a 404. The final step is to loop through any route constraints on a match candidate, eg making sure the request HTTP method is accepted by the match candidate. If all the constraints pass, then this is the matching route. Otherwise, I yield return any other match candidates until I either find one, or return a 404 or 415 depending on if any match candidates were found with different HTTP methods. Yield returns are useful because I don’t have to collect all possible match candidates first before selecting one, which yields a slight performance improvement.
The runtime of the algorithm is dependent on the number of segments in the path (we’ll call that n). In the best case scenario with all static routes, the runtime is O(n), and in the worst case scenario O(nm), where m is the average number of variable segments per segment.
An example
Let’s say that the request path was /users/123/email. I’d scan our route trie for users, and find a match in O(1) because it exists as a static segment in the trie. Then, I’d search for 123 from the users node, but not find a static match. So, I’d iterate over the variable nodes until I found a match. In this case, the :id node doesn’t have any variable constraints, so it will match any value. Then, I search for email in :id's children, again find a matching static node in O(1). The trie will tell us that the email node maps to a particular route, and is a candidate for a match. In this case, I’ll say the route constraints all pass, and return this route as the match.
Benchmark results
So, how does this algorithm compare to FastRoute? I took a look at several benchmarks on the web, but saw issues with all of them, eg unrealistically long URIs with 9 path segments or only testing matching the first or last route in the collection. I decided to write a benchmark that matches every single route in a collection of 400 with paths like /abc{0-399}/{0-399}/:foo/{0-399}. The results: Aphiria’s algorithm is ~175% faster than FastRoute’s, but lags behind Symfony’s excellent router by roughly the same margin [shakes fist].
I am sure there are micro-optimizations I can make to improve Aphiria’s speed a bit (eg trying to match multiple static segments in one go), but they would almost certainly come at the price of increased complexity. Aphiria’s router is presently 3,976 lines (123 for just the matching) compared to Symfony’s 6,727 (not including tests). However, given that all three of these libraries’ speed is more than fast enough, I’m not particularly interested in closing the gap to Symfony. That being said, kudos to Nicolas Grekas and community for achieving that speed.
Conclusions
To reiterate — almost all PHP routers are fast enough. Why do I think you should use Aphiria’s? It supports:
- PHP 8.0 attributes and fluent builder syntaxes
- Matching paths and hosts
- Custom route constraints that can use any part of the request to match a route, eg header matching for API versioning
- Route grouping
- Binding framework-agnostic middleware to routes
- Creating URIs from route names
- No ties to any library of framework outside of Aphiria’s reflection library
If you’d like to try out Aphiria’s router, you can either install the skeleton application to get up and running quickly, or install just the library via Composer.
Thanks to James Rapp for listening to my endless pondering on the algorithm and for being a sounding board for optimizations.
