"Если компьютеры станут слишком мощными, мы можем организовать их в комитеты. Это их прикончит" (с) неизвестный автор
Введение
Так или иначе сталкиваться с регулярными выражениями приходилось большинству разработчиков. Мое первое знакомство произошло с реализацией regexp в STL std::regexp. Чаще всего регулярки используются в проверке входных данных, что-то вроде проверки корректности введенного пользователем URL, адреса IPv4, адреса IPv6, телефонного номера и при этом скорость выполнения операции regex не сильно влияет на время отклика от приложения. Но, что если вам приходится проверять сотни, тысячи или даже десятки тысяч правил и все это на постоянно меняющихся наборах входных данных в реальном времени? В этой ситуации вам не просто нужен быстрый алгоритм, вам понадобится лучший из них, вам понадобится чемпион!
Выбираем участников соревнований
Критерии отбора участников довольно просты:
наличие исходных кодов
совместимость по самим правилам, хотя бы на базовом уровне
код написан на С/С++
Hidden text
Да, я фанат С++, поэтому regexp на языках отличных от C/C++ не рассматриваю, сорян
Итак, погуглив пояндексив немного находим следующих претендентов:
Присвоенное имя |
Язык |
Ссылка на репозиторий |
stdlib |
C++ |
- |
tiny-regex-c |
C |
|
ximtech |
C |
|
boost |
C++ |
|
hyperscan |
С |
|
google-re2 |
C++ |
Методология
Теперь нужно определиться как будем проверять участников.
Есть заранее составленный список регулярных выражений одинаковый для всех участников.
Есть заранее составленный список наборов данных одинаковый для всех участников.
Для выравнивания замеров времени будем итеративно проверять каждое (из
NR) правилоIRраз наIDитерациях наборов данных (изND), т.е. количество проверок для каждого участника будет:SUM = IR * NR * ID * NDДля снижения взаимного влияния участников друг на друга будем собирать отдельные приложения для каждого участника.
Для сохранения актуальности проекта, исходный код участника клонируется из его репозитория, из ветки master или толерантного main.
Если участник - это библиотека, то проводится его сборка.
Непосредственно код который осуществляет проверку состоит из класса c двумя абстрактными методами - один для подготовки правил (в том числи для их компиляции) и один для непосредственной проверки скомпилированных правил на наборе данных.
Запускать гонки будем на виртуальной машине в облаке
Большая гонка
Код представлен в репозитории https://github.com/shvit/regexp_checker
Для желающих самостоятельно провести гонку на своем компьютере, потребуется установить зависимости. Для Ubuntu 20.04 (подходит также и для ubuntu-latest):
sudo apt install build-essential cmake ragel git libboost-all-dev
git clone https://github.com/abseil/abseil-cpp abseil-cpp && cd abseil-cpp && mkdir -p bin && cd bin && cmake -DCMAKE_CXX_STANDARD=17 -DCMAKE_POSITION_INDEPENDENT_CODE=ON .. && cmake --build . && sudo cmake --install .
теперь клонируем гонку себе на комп и запускаем
git clone https://github.com/shvit/regexp_checker
cd regexp_checker
make check
Проще, конечно же, воспользоваться готовым результатом запуска на виртуалке в GitHub Actions:
В качестве проверки, вместо юнит тестов - все участники выдали одинаковое количество совпадений - по 2'800'000.
Проверки проводились с параметрами: NR=10, IR=20'000, ND=5, ID=10. Общее количество проверок для одного участника SUM=10'000'000.
Заключение
При текущем составе участников бесспорным чемпионом является проект hyperscan, но также порадовал участник занявший второе место - boost.
Также необходимо отметить, что проекты tiny-regex-c и ximtech поддерживают сокращенный набор элементов regexp, из-за чего пришлось существенно сократить список правил. Проект ximtech является развитием проекта tiny-regex-c. Также в проекте tiny-regex-c есть баги и также он не позволяет компилировать более одного правила из-за своей архитектуры.
Для использования проекта google-re2 потребуется установка библиотек Abseil и также потребуется не тривиальная линковка готового проекта.
В заключение, хочется отметить наличие у проекта hyperscan возможности применения правил на потоках (streams), что в некоторых случаях может быть решающим.
Если кто-то знает других потенциальных участников гонки - предлагайте в комментариях.
Комментарии (26)
Wesha
07.05.2024 15:39+2проверки корректности введенного пользователем URL, адреса IPv4, адреса IPv6, телефонного номера и
(расслабляясь и выдыхая) Ну хоть кто-то не считает, что он может регулярками проверить емейл-адреса.
cranium256
07.05.2024 15:39+6Ещё бы в тестировании хорошо учесть насколько библиотеки умеют в регулярки. А то "совместимость по самим правилам, хотя бы на базовом уровне" и "[...] поддерживают сокращенный набор элементов regexp" выглядит несколько расплывчато. Есть общепринятые "стандарты" языка регулярок: например Basic (BRE), Extended (ERE), Perl-совместимый (PCRE). Хорошо бы сравнивать не только скорость, но и реализованные в библиотеке фичи самих регулярок. Такой обзор был бы более полезен. Какой толк с очень быстрой библиотеки, которая реализует урезанный базовый уровень? А кому-то в своём приложении может и такого уровня хватит.
И ещё, какие лицензии у тестируемых библиотек? Это тоже немаловажно, если использовать в других проектах.
sh_vit Автор
07.05.2024 15:39Спасибо за отзыв! Наверно, продолжение надо сделать с учетом общепринятых "стандартов", т.е. либо без примитивных реализаций, либо с разделением на лиги (любительская/профессиональная), ну, и с учетом вновь заявленных участников соревнований.
Про лицензии думал уже, надо будет добавить.
R0bur
07.05.2024 15:39Странно, что между 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.».
sh_vit Автор
07.05.2024 15:39Согласен. Это повод поразбираться.
Хотя, чисто формально, это в порядке вещей, ибо boost не стоит на месте.
OMR_Kiruha
07.05.2024 15:39А каким компилятором и соответственно стандартной библиотекой пользовались во время теста? Может есть смысл сравнить большую тройку компиляторов?
P.S. Нашёл в логах что GCC 11.4.0
sh_vit Автор
07.05.2024 15:39+1Формально, при сборке тестовых приложений, компилятор жестко не задан - используется переменная
CXX, но по факту, при сборке на виртуалке в GitHub Actions, используетсяgccиз пакетаbuild-essentialизubuntu-latest.
В соревнованиях главное обеспечить равные условия, хотя зависимость от компилятора была бы интересна.
lorc
07.05.2024 15:39+1AFAIK, стандарт описывает интерфейс, но не описывает имплементацию. Соответственно в gcc libc++, clang libc++ и msvc libc++, например, могут быть совершенно разные по скорости движки для регулярных выражений. То же самое касается и других алгоритмов, например алгоритмов сортировки. Для них, стандарт, вроде бы описывает только ограничение по O большому и все.
sergio_nsk
07.05.2024 15:39+5cmake -DCMAKE_CXX_STANDARD=17 -DCMAKE_POSITION_INDEPENDENT_CODE=ON .. && cmake --buildВерно я понимаю, что по умолчанию собираем и запускаем конфигурацию Debug без оптимизаций компилятора?
sunnybear
07.05.2024 15:39Судя по коду, в hyperscan как раз и выполняется компиляция регулярок, поэтому повторные прогоны должны быть быстрыми - его имеет смысл сравнивать только с jit
sh_vit Автор
07.05.2024 15:39+1Добавление участника pcre2 - в планах. Спасибо за комментарий!
Если есть на примете другие - предлагайте.
Razoomnick
07.05.2024 15:39Проверки проводились с параметрами: NR=10, IR=20'000, ND=5, ID=10. Общее количество проверок для одного участника SUM=10'000'000
Меня смущает IR=20'000. Скажем, если в библиотеке реализовано кэширование на каком-либо уровне, она получит значительное преимущество.
Под кэшированием я понимаю что угодно, что ускоряет повторные прогоны: можно запоминать N последних результатов, можно кэшировать результат преобразования регулярного выражения из строки в более подходящую структуру данных, можно регулярное выражение представить в виде конечного автомата и запомнить его, можно скомпилировать регулярное выражение и сохранить результат компиляции.
Я не считаю такие оптимизации "нечестным преимуществом", кэширование и компиляция - отличные подходы. Но методология тестирования не учитывает, что скорость сопоставления строк с регулярными выражениями может драматически меняться в зависимости от того, повторяются ли регулярные выражения в процессе выполнения теста.
voldemar_d
07.05.2024 15:39Драматически - это от английского dramatically?
Razoomnick
07.05.2024 15:39Вероятно, да, я не знаю. Я употребил слово не задумываясь именно в таком значении, и мне казалось это значение естественным для русского языка. Возможно, это неправильно.
galaxy
07.05.2024 15:39Как эти библиотеки справляются с патологическими регулярками типа
(a?)^na^n? (пример для n=5 —/a?a?a?a?a?aaaaa/ ~ "aaaaa")Смысл существования re2 как раз в отсутствии патологий бектрекинга (https://swtch.com/~rsc/regexp/regexp1.html)
Tomas245
Неплохая статья, я ещё слышал про ctre https://github.com/hanickadot/compile-time-regular-expressions, может также себя неплохо покажет)
sh_vit Автор
Спасибо, за наводку!