@nicolas-grekas: you can't use it directly as it's not PHP, but you might want to look at the prefix matching approach used by https://github.com/hhvm/hack-router ; our benchmarks put it at ~ 5x faster than fast-route's approach, which AIUI is what you've been following here:

$ hhvm naive-benchmark.php
Map has 3718 entries and 6639 URIs
Cold run for simple regexp...
... done (init: 252.22ms, lookups: 18540.45ms, per lookup: 2.79ms, estimated total per request: 255.02ms)
Cold run for uncached fastroute...
... done (init: 2836.94ms, lookups: 493.74ms, per lookup: 0.07ms, estimated total per request: 2837.02ms)
Cold run for cached fastroute...
... done (init: 2463.76ms, lookups: 386.84ms, per lookup: 0.06ms, estimated total per request: 2463.81ms)
Cold run for uncached prefix match...
... done (init: 263.23ms, lookups: 236.94ms, per lookup: 0.04ms, estimated total per request: 263.26ms)
Cold run for cached prefix map...
... done (init: 69.98ms, lookups: 77.89ms, per lookup: 0.01ms, estimated total per request: 69.99ms)
Warm run for simple regexp...
... done (init: 34.87ms, lookups: 17566.62ms, per lookup: 2.65ms, estimated total per request: 37.51ms)
Warm run for uncached fastroute...
... done (init: 2416.26ms, lookups: 389.40ms, per lookup: 0.06ms, estimated total per request: 2416.32ms)
Warm run for cached fastroute...
... done (init: 22.53ms, lookups: 395.27ms, per lookup: 0.06ms, estimated total per request: 22.59ms)
Warm run for uncached prefix match...
... done (init: 30.47ms, lookups: 80.80ms, per lookup: 0.01ms, estimated total per request: 30.49ms)
Warm run for cached prefix map...
... done (init: 4.15ms, lookups: 77.49ms, per lookup: 0.01ms, estimated total per request: 4.17ms)

In short, what we do is:

• decide on a prefix length
• build a struct with:
  • a map of prefix => node
  • a map of regex => node where the is no literal string prefix we can use
  • Node is either a responder, or another similar struct
• when looking up, we fetch the prefix length - and then see if $map['prefixes'][substr($path, 0, $length)] is set - then return the responder or recurse into the sub-map. If not, check for a regex match. If that fails, fail.

This means that each common constant part of the URL can be looked up in constant time - but it will be linear in terms of number of parts, and where regexes are needed, that part will have usual regex complexity.

e.g. if we have /foo/bar => BarController, /foo/baz => BazController, and /herp/derp => DerpController, we'll make:

prefix len: 4
prefixes:
  /foo:
    prefix length: 4
    prefixes:
    /bar: BarController
    /baz: BazController
  /her:
    prefix length: 6
    prefixes:
      p/derp: DerpController

We'll then look up $map[$prefixes[substr($requested_path, 0, 4)]], then the appropriate subprefix.

If we have foo/bar/{id:\d+}, we'll use prefix matching for the 'foo/bar/' part, then a regexp match just for the id:\d+ part

@fredemmott happy to see you here :) That's interesting. I looked at the code but didn't run it. From what I understand, I'm not sure this would provide additional performances, because in the end there is still a regex call, and also because the regex we use embeds same-prefix tree optimizations. I also fear this approach is not compatible with our in-order logic. I'd be happy to be wrong though :)
I started writing something on the topic to explain the new matcher in depth:
https://twitter.com/nicolasgrekas/status/964513325815074817
I'm just not at the same-prefix tree optimization explanations yet. Next post.

So, there's no regexp call for static routes - only when there's a variable. We're also not using the regexp for any static prefixes before a variable.

The main advantage is that while the regexp is checking for common prefixes, we're looking them up with array key access; for large maps, this can be much faster.

This is definitely not representative of real world performance, but illustrates the difference:

<?php

// generate a bunch of /foo/{id} routes, then look them up

const LENGTH = 8;
const MAP_SIZE = 2500;
const LOOKUPS = 10000;

$random_parts = array_map(
  function() { return bin2hex(random_bytes(intdiv(LENGTH, 2))); },
  range(1, MAP_SIZE)
);

$prefix_map = [];
foreach ($random_parts as $part) {
  $route = '/'.$part.'/';
  $prefix_map[$route] = $part;
}
$regexp = '/^\/('.implode($random_parts, '|').')\/\d+$/';

$requests = array_map(
  function() use ($random_parts) {
    return [
      $random_parts[random_int(0, count($random_parts) - 1)],
      random_int(0, PHP_INT_MAX)
    ];
  },
  range(1, LOOKUPS)
);

// Optimize the requests for each map kind
$regexp_requests = array_map(
  function($request) {
    list($route, $id) = $request;
    return '/'.$route.'/'.$id;
  },
  $requests
);

$prefix_requests = array_map(
  function($request) {
    list($route, $id) = $request;
    return ['/'.$route.'/', (string) $id];
  },
  $requests
);

$regexp_results = [];
$prefix_results = [];

$start = microtime(true);
foreach ($regexp_requests as $request) {
  $matches = [];
  if (preg_match($regexp, $request, $matches) !== 1) {
    throw new Exception('failed to match regexp');
  }
  $regexp_results[] = [$matches[1], $matches[2]];
}
$regexp_time = microtime(true) - $start;

$start = microtime(true);
foreach ($prefix_requests as list($prefix, $id)) {
  $route = $prefix_map[$prefix] ?? null;
  if ($route === null) {
    throw new Exception('failed to match prefix');
  }
  $matches = [];
  if (preg_match('/^\d+$/', $id, $matches) !== 1) {
    throw new Exception('failed to match id regexp');
  }
  $prefix_results[] = [$route, $matches[1]];
}
$prefix_time = microtime(true) - $start;

printf(
  "Regexp time:\t%fs\nPrefix time:\t%fs\nEqual: %s\n",
  $regexp_time,
  $prefix_time,
  $prefix_results == $regexp_results ? 'yes' : 'no'
);

$ php test.php
Regexp time:	0.020579s
Prefix time:	0.001593s
Equal: yes

@fredemmott it would be great if you could run the router we have on master and compare it to yours!
The main description in #26059 contains an example to bootstrap a simple bench. I'd be happy to read any numbers you get with it :)

As for order: we have some hybrid approaches that preserve it, but not publicly. For hack-router, we:

• go for most-specific-first
• if two routes are 'as specific' as far as we can tell (e.g. we don't prioritize {id:\d+} over '{id}`), we preserve order

This means that if your map is

.+:   WildcardController
/foo: FooController

We wont' preserve order: /foo will go to FooController, rather than WildcardController.

Sorry, not going to be able to do that any time soon; just tried, and the 'urgent' PHP7 compatibility list for HHVM just got a fair bit larger :/

In particular:

• Parse error on direct calls to functions returned by method facebook/hhvm#7884
• Request: add support for private/protected const in classes, in hack and non-hack php 7.1 files facebook/hhvm#7812
• Add support for new array destructuring syntax facebook/hhvm#7535

Have fun, and thanks for the new ideas :)

@fredemmott FYI, here is the kind of optims I'm was referring to: #26208.

@fredemmott I wonder how your approach holds up against routes that have multiple variables for example /blog/{category}/{id}/{title}