Router

Hey there! This repo is an experiment to create a well-tuned and speedy URI router. There's only two main goals:

• It's fast
• It's simple

Prior to this project, I built the SimpleRouter as a fork from a very cool project called the simplePHPRouter. That router was based on regex for parameterization, and the regex made it pretty painful to maintain if I ever left it alone for too long.

Since working on SimpleRouter, I've played with other languages (primarily Go) and found a few new ways of doing things.

Methodology

Radix trees (tries, but I prefer the normal spelling) are wonderful mathematical constructs; the basic concept is that you have the root of a tree and branches (nodes) that have leaves (nodes). When you add a branch, this branch gets merged with existing branches if they match, and the leaves are still at the ends to be separated.

Take for example these routes:

/api/v1/hello
/api/v1/hi
/api/v1/hello/:param
/api/v2/no
/foo

A radix (and more specifically, a PATRICIA) trie takes the commonalities in these routes and makes them into nodes, or branches. / exists as the root node. api/ is turned into a node, from which v1/ and /v2/no branch. hello is taken as another branch with the / and :param child nodes. /foo is naturally it's only branch from the root.

By splitting these routes up into a trie based on their segments, you're able to iterate far more quickly through the tree to find what you're looking for. If a user then requests /api/v1/hello/sky the router can jump from the root, to api/, to v1/, to hello/, then to the final node much faster than if we had to chop up, say, an associative array and compare for every registered route.

The nodes can contain any arbitrary information, such as HTTP methods or handlers. From my experience, this method of lookup prefers specificity, and so it will always prefer the edges over the inner structures.

Parameters

One flaw(-ish) of the SimpleRouter implementation (and many other implementations) is the use of regex as a way of identifying and extracting route parameters. As everyone knows, regex imposes time, overhead, and complexity to any system.

In order to circumvent this, we can rely on our node structure; if a node begins with our delimiter : then we can take the related segment from the URI and use that as a parameter, regardless of the value. This means we have extremely low overhead in the logic required to pull parameters from URIs.

To prevent creating many unnecessary children nodes and handlers, all parameters are converted to a :x node internally. Any value will satisfy a parameter node. These parameters are then passed into the hanlder function call.

Performance

Of course, what good is a router that's slow? We need to be able to lookup routes and get the handler as quickly as possible. Now, you may note there are multiple routers here; these are implementations in their experimental phase to find the most memory and time efficient lookup operations possible.

There are three tests performed, each running in iterations of 10000, 100000, 1000000;

• blog: 4 routes
• github: 203 routes
• big: 1000 routes

And one final test to ensure parameter handling is correct. You can run these tests by simply running php test.php in the /tests directory. These are my results for the big 1,000,000 test:

// CPU: 11th gen Intel Core i7-1185G7 @ 3.0GHz
// RAM: 32GB 3200MHz DDR4
🚀 Running 1000000 iterations...
✔️ Done!
Peak memory: 2726.5 kb
Time: 1.5776410103 s
Avg/lookup: 0.0000008231 s
Shortest lookup: 0.0000009537 s
Longest lookup: 0.0018200874 s

Usage

Using the router is simple! The implementations here must adhere to the Router interface;

$router->add('GET', '/api/v1/:test', function($test) {
	echo $test;
});

$router->lookup($_SERVER['REQUEST_METHOD'], $_SERVER['REQUEST_URI']); // ['code' => 200, 'handler' => callable, 'params' => []]

This API isn't expected to change, as all the router is expected to do is to look up our requested URI and return the handler and params for it.