"Если компьютеры станут слишком мощными, мы можем организовать их в комитеты. Это их прикончит" (с) неизвестный автор
![Большие гонки regexp Большие гонки regexp](https://habrastorage.org/getpro/habr/upload_files/65f/855/d9c/65f855d9c72982ec6d278e0fd7f466dd.jpg)
Введение
Так или иначе сталкиваться с регулярными выражениями приходилось большинству разработчиков. Мое первое знакомство произошло с реализацией 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), что в некоторых случаях может быть решающим.
Если кто-то знает других потенциальных участников гонки - предлагайте в комментариях.