NFA тоже. DFA это детерминированный (ДКА)

а внутри там xs или оно на миниперле?

через JIT/INLINE-C веселее будет, там таблицы не нужны, на switch-goto есть мега-быстрая реализация.

там С++ библиотека, и маленький XS адаптер

в доказательство к сказанному выше
   my $r = URI::Router->new(
       qr#/aaaa#               => 1,
   );

   timethese(-1, {
       a => sub { $r->route('/aaaa') },
   });
это в качестве "а"

Benchmark: running a for at least 1 CPU seconds...
        a:  1 wallclock secs ( 1.07 usr +  0.00 sys =  1.07 CPU) @ 9354330.84/s (n=10009134)

теперь добавляем гавна

my $r = URI::Router->new(
       qr#/aaaa#               => 1,
       qr#/[bcd]+#             => 2,
       qr#.*e.*#               => 3,
       qr#.+(?:f|t+|z*)[0-9]+# => 4,
   );

   timethese(-1, {
       a => sub { $r->route('/aaaa') },
       b => sub { $r->route('/ddcb') },
       e => sub { $r->route('/qwer') },
       f => sub { $r->route('/xtt8') },
   });

Benchmark: running a, b, e, f for at least 1 CPU seconds...
        a:  1 wallclock secs ( 1.07 usr +  0.00 sys =  1.07 CPU) @ 9354330.84/s (n=10009134)
        b:  2 wallclock secs ( 1.06 usr +  0.00 sys =  1.06 CPU) @ 9442579.25/s (n=10009134)
        e:  2 wallclock secs ( 1.06 usr +  0.00 sys =  1.06 CPU) @ 9442579.25/s (n=10009134)
        f:  2 wallclock secs ( 1.06 usr +  0.00 sys =  1.06 CPU) @ 9442579.25/s (n=10009134)

ему пох

ну и предвкушая замечание что он не работает нихуя

say $r->route('/aaaa');
say $r->route('/ddcb');
say $r->route('/qwer');
say $r->route('/xtt8');

1
2
3
4

на самом деле там 70% времени съедает сраный MRO вызов в перле метода ->route() и еще немного создание перловых SV. в с++ там 30М

ну и еще особенность от которой не уйти: если использовать сохраняющие группы () он замедлится если совпал с регэкспом где они были, приходится память саллоцировать плюс в перл на стек все пихать (т.к. он возвращает скаптуренные скобки из route()

это константное замедление(х1.5) просто по факту были сохр группы или нет, плюс небольшое линейной от кол-ва таких групп из-за перла (приходится создавать N sv-шек)

на самом деле трек захватов его практически никак не замедляет (слабо измеримо), движок это бесплатно знает, но к сожалению вернуть в перл без пенальти не получается

Помнится, libpcre задачу аллоцирования вешал на вызывающего, требуя для match буфер x3 по количеству групп в регулярке, возвращая позиции во входной строке. У вызывающего это вполне может быть постоянный буфер. Но то Си был, в Перле потом substr заниматься никому не захочется.

Там кастомный аллокатор и так юзается. Ты не знаешь заранее какой роут совпадет и сколько в нем будет капчуресов, тебе всегда придется держать под худший самый длинный кейс, даже если в итоге ты долбанул по статическому урлу без каптуресов, замедляя все такие кейсы. Не вариант

Я тебе более того скажу, возьми любые 2 регулярки которые логически матчат одно и тоже, но написаны по разному, пусть одна из них максимально неээфективно а другая максимально эффективно - он сматчит за одинаковое время, потому что для ДКА вообще похуй как ты написал регулярку. Любая самая неээфективная будет работать со скоростью самой эффективной. Ну это базовое свойство дка