Comments 27
Неплохая статья, я ещё слышал про ctre https://github.com/hanickadot/compile-time-regular-expressions, может также себя неплохо покажет)
проверки корректности введенного пользователем URL, адреса IPv4, адреса IPv6, телефонного номера и
(расслабляясь и выдыхая) Ну хоть кто-то не считает, что он может регулярками проверить емейл-адреса.
А где pcre?
Ещё бы в тестировании хорошо учесть насколько библиотеки умеют в регулярки. А то "совместимость по самим правилам, хотя бы на базовом уровне" и "[...] поддерживают сокращенный набор элементов regexp" выглядит несколько расплывчато. Есть общепринятые "стандарты" языка регулярок: например Basic (BRE), Extended (ERE), Perl-совместимый (PCRE). Хорошо бы сравнивать не только скорость, но и реализованные в библиотеке фичи самих регулярок. Такой обзор был бы более полезен. Какой толк с очень быстрой библиотеки, которая реализует урезанный базовый уровень? А кому-то в своём приложении может и такого уровня хватит.
И ещё, какие лицензии у тестируемых библиотек? Это тоже немаловажно, если использовать в других проектах.
Странно, что между boost и stdlib такой разрыв, потому что «The Boost Regex library provides regular expression support for C++, this library is the ancestor to std::regex and still goes beyond and offers some advantages to, the standard version.».
Согласен. Это повод поразбираться.
Хотя, чисто формально, это в порядке вещей, ибо boost не стоит на месте.
А каким компилятором и соответственно стандартной библиотекой пользовались во время теста? Может есть смысл сравнить большую тройку компиляторов?
P.S. Нашёл в логах что GCC 11.4.0
Формально, при сборке тестовых приложений, компилятор жестко не задан - используется переменная CXX, но по факту, при сборке на виртуалке в GitHub Actions, используется gcc из пакета build-essential из ubuntu-latest.
В соревнованиях главное обеспечить равные условия, хотя зависимость от компилятора была бы интересна.
AFAIK, стандарт описывает интерфейс, но не описывает имплементацию. Соответственно в gcc libc++, clang libc++ и msvc libc++, например, могут быть совершенно разные по скорости движки для регулярных выражений. То же самое касается и других алгоритмов, например алгоритмов сортировки. Для них, стандарт, вроде бы описывает только ограничение по O большому и все.
cmake -DCMAKE_CXX_STANDARD=17 -DCMAKE_POSITION_INDEPENDENT_CODE=ON .. && cmake --build
Верно я понимаю, что по умолчанию собираем и запускаем конфигурацию Debug без оптимизаций компилятора?
Судя по коду, в hyperscan как раз и выполняется компиляция регулярок, поэтому повторные прогоны должны быть быстрыми - его имеет смысл сравнивать только с jit
Проверки проводились с параметрами: NR=10, IR=20'000, ND=5, ID=10. Общее количество проверок для одного участника SUM=10'000'000
Меня смущает IR=20'000. Скажем, если в библиотеке реализовано кэширование на каком-либо уровне, она получит значительное преимущество.
Под кэшированием я понимаю что угодно, что ускоряет повторные прогоны: можно запоминать N последних результатов, можно кэшировать результат преобразования регулярного выражения из строки в более подходящую структуру данных, можно регулярное выражение представить в виде конечного автомата и запомнить его, можно скомпилировать регулярное выражение и сохранить результат компиляции.
Я не считаю такие оптимизации "нечестным преимуществом", кэширование и компиляция - отличные подходы. Но методология тестирования не учитывает, что скорость сопоставления строк с регулярными выражениями может драматически меняться в зависимости от того, повторяются ли регулярные выражения в процессе выполнения теста.
Как эти библиотеки справляются с патологическими регулярками типа (a?)^na^n? (пример для n=5 — /a?a?a?a?a?aaaaa/ ~ "aaaaa")
Смысл существования re2 как раз в отсутствии патологий бектрекинга (https://swtch.com/~rsc/regexp/regexp1.html)
Почему stdlib настолько медленная? И за счёт чего достигается скорость?
Я думаю что основных причин две:
Надо поддерживать все-все фичи описанные в стандарте. И во всех возможных комбинациях. При чем фичи не только для самих регулярных выражений, но и для строк, например.
Разработчики stdlib - не разработчики движков регулярных выражений. Взять готовый чаще всего не позволит лицензия, а пилить с нуля - это еще та работа.
regexp — большие гонки