Комментарии 12
Очень интересно!
Вы могли бы добавить бенчмарк ещё для Hyperscan?
И для boost.xpressive тоже хотелось бы.
Там есть в т.ч. compile time regex в c++-ных шаблонах, т.е. в результате получается, как раз, нативный оптимизированный код.
Мне сейчас затруднительно посмотреть ваши примеры и ткнуть в доки экспрессив, т.к. в данный момент пользуюсь гостиничным интернетом, а это боль ;(
И, ЕМНИП, xpressive in compile time mode существенно быстрее boost и std::regex.
Интересно сравнить скорость с re2
Я не очень вчитывался в код, но похоже тут недетерминированный конечный автомат моделируется на стеке вызовов? Если уж компилять, то может есть смысл привести к детерминированному автомату? У него скорость матчинга линейная, а у нка с бэктрекингом потенциально квадратичная.
Дело ведь в том, что если не будет отката назад, не будет возможности искать сопоставление для некоторых регулярных выражений, где эта самая квадратичность нужна. Но там, где она не нужна, компилятор и так во многих случая может заменить последовательность вложенных вызовов набором последовательных операций (в рамках одной функции).
Теорию автоматов Вы судя по всему не очень знаете? ДКА равномощен НКА. Регулярные выражения можно матчить без бэктрекинга (пока они именно регулярные, без рекурсивных бэкреференсов, и даже с ними не всё так плохо). Другой вопрос, что преобразование НКА в ДКА не самая "дешёвая" операция, и если регулярку предполагается использовать полтора раза, оно того не стоит. Но учитывая что Вы компиляете с оптимизацией, что уже не супер быстро, как раз кажется актуально выжать максимум производительности.
Чисто в теории я действительно не силён, я больше практик. Поделитесь ссылкой на алгоритм преобразование НКА в ДКА и/или на литературу по теме, с удовольствием почитаю.
без бэктрекинга
Я знаю такой способ, в нём входная строка просто обходится посимвольно и никогда не происходит отката назад. А вместо хранения стека состояний там хранится стек т. н. потоков.
Смотреть здесь, раздел Thompson's Implementation. Но, насколько я понимаю, такой алгоритм в реальности не самый быстрый, да и компилируется в нативный код он весьма плохо.
Ахо, Ульман, Сети "Компиляторы. Принципы, технологии и инструментарий.", второе издание, раздел 3.7.1
Или можете мой конспект посмотреть. Там правда нет одного важного момента: по приведённому алгоритму ДКА не обязательно оптимальный, нужно как минимум объединять эквивалентные состояния; у Ахо ещё приведены алгоритмы прямого построения ДКА (без НКА) и оптимизации ДКА (раздел 3.9)
Использование библиотеки LLVM для генерации кода регулярных выражений